# Questions tagged [mixed-integer-programming]

The tag has no usage guidance.

43 questions
Filter by
Sorted by
Tagged with
24k views

### What's the fastest software(open source) to solve mixed integer programming problem

I have a mixed integer programming problem. And I am current using GLPK as my solver. But I found that GLPK is good for Linear Programming problem, but for Mixed Integer programming, it requires much ...
2k views

### Ways to speed up solving an LP with Google's ortools

I'm having an issue solving an LP of the form: $$\min z = c^Tx$$ $$\text{s.t.}$$ $$Ax \geq b$$ $$x\geq p$$ $1 \leq a_{ij} \ll b_i$, $p \leq 0$, and $c \geq 0$ The specific problems I'm running into ...
306 views

### Closest interior point on integer grid to a vertex of a convex polyhedron

I have a 3 dimensional convex polyhedron whose vertex coordinates are rational. For one of these vertices, I would like to find the nearest integer grid point (under the Euclidean metric) that is ...
102 views

### What is the name for this type of constraint?

I have what would be a straightforward mixed-integer linear programming problem, except for the fact that some of the constraints are of the form $f(x_1,x_2,x_3,\ldots,x_n) < c$, where $f$ is 'take ...
235 views

### What is a suitable algorithm for solving a large mixed-integer quadratic program?

I am interested in the solutions of a very large quadratic programming (QP) problem \begin{align} \min_{x \in \mathbb{R}^n} & x^T Q x\\ \mathrm{subject\ to} & A x = b\\ & x \in \{0,1\}^n \...
98 views

### $L_2$ projection with integer constraints and prescribed sum

Suppose I am given a vector $v^0\in\mathbb{R}^n$ and integers $k,\ell\in\mathbb{Z}$. Assuming $k$ is close to zero (e.g. $0\leq k\leq5$), is there an algorithm for solving the following integer ...
313 views

### Should I include integral constraints in a integer linear program with a totally unimodular constaint matrix?

I have formulated an integer linear program (ILP). The constraint matrix for the ILP is totally unimodular. Should I solve it as an LP without the integral constraints, or should I keep the integral ...
508 views

### Sum of Inverse of Variables in an Optimization Problem

I have the following optimization problem: $$\begin{array}{ll} \text{Minimize} & \frac{1}{x_1} + \frac{1}{x_2} + \ldots + \frac{1}{d_n} \\ \text{Subject to} & A x \leq b \end{array}$$ where ...
187 views

### Optimization algorithm selection for 3 variable integer

I have a cost function: $f(x,y,z) \rightarrow \mathbb{R}$ it is very expensive to evaluate $x,y,z \in \mathbb{Z}$ 0 < x < 10 0 < y < 30 0 < z < 100 I thought it was convex, not sure ...
660 views

### Solver for a MIQP with an indefinite coefficient matrix

Do CPLEX or Gurobi handle MIQPs with indefinite coefficient matrices? The problem I am dealing with has quadratic terms in which one variable is binary and the other variable is continuous. The ...
71 views

### How to model a pump behavior using MILP?

The behavior of a pump is the following: If $h \geq h_{start}$, then pumped flow is a constant $Q_p$. The pump works as long as $h > h_{stop}$ If $h \leq h_{stop}$, then pumped flow is 0. The pump ...
1k views

### Cplex C++ Interface: How to add many constraints quickly?

I noticed that adding constraints to an IloModel one by one can be prohibitively slow. (I am referring to the construction of the model, not the optimization.) ...
242 views

### optimal SAT solver with weighted variables

I have $n$ boolean variables $x_1,\ldots,x_n$ with associated real-valued costs $c_1,\ldots,c_n$, respectively, and a boolean function $(x_1,\ldots,x_n)\mapsto\Phi(x_1,\ldots,x_n)$ in conjunctive ...
150 views

### Constrained System / Combinatorial Problem

Let $x\in \mathbb{R}^{n}$, $Y\in \mathbb{R}^{mxn}$. We can then define: $row_{i}(Y)=$ $i^{th}$ row of $Y$ $column_{i}(Y)=$ $i^{th}$ column of $Y$ $x_{i}=i^{th}$ element of $x$ $sum(x)=$ sum of ...
68 views

### Relaxing a variable in MIP

I have this MIP optimization problem, with couple of binary variables; however when I relax one of the binary variables the optimal solution of the objective does not change. But the solving time ...
44 views

### Constraints 'exactly/at most one non-zero element' without binary variables

In a much larger MINLP problem, I have set of variables $\{a_{ij}\}_{m,n}$, such that $0 \leq a_{ij} \leq 1$ for all $i$, $j$, which I could think of as a matrix, for which I have two requirements: ...
41 views

### Capturing the order of certain objects in an MILP

I have a certain convex optimization problem which depends on the order of a set of $N$ objects. Meaning, for every possible ordering, I get a different convex optimization problem. My ultimate goal ...
190 views

### Solve chemical formula (number of molecules in reaction)

In order to balance atom count in chemical equation: a O2 + b C12H24O11 → c CO2 + d H2O I make linear equation: ...
563 views

### Binary Integer Programming Problem Subject to a Set of First-Order DEs

Recently, I came across an optimization problem with binary decision variables which was constrained with a set of first-order differential equations (resulting from a continuous-time Markov chain ...
116 views

### Using MILP to place a set of primers along a genome

Define variables $p_i,u_i\in\{0,1\}^G$, for $i=1,\ldots,8$ and $G=30000$. Let $v$ be a constant vector also in $\{0,1\}^G$, with approximately 25% of its entries equal to $1$ (randomly located). Let ...
173 views

### enhancing a MIP formulation of Ising model [closed]

I want to construct a MIP formulation for Ising model. For simplicity, I will only include terms involving nearest-neighbor pairs and triangular terms. I propose one formulation and ask whether there ...
71 views

### Efficient solver of a Integer programming

I am solving an Integer programming using MATLAB, yet the efficiency is low. Here is the problem: Suppose $v$ is a $N \times 1$ vector. For $v_i \in v$, $v_i \in \{0,1\}$. $D$ is a 0-1 matrix, which ...
50 views

328 views

### Converting linear BIP constraints into convex hull

Given a linear BIP $$\text{Minimize}\;\;\;c^Tx$$ $$\hspace{6.5mm}\text{Subject to}\;\;\;Ax\leq b$$ $$\hspace{38mm}x\in\{0,1\}^n$$ We can in theory convert the constraints to the convex hull ...
366 views

### Solving nested MILP problems

I want to solve a family of MILP problems (indexed by $k \geq 0$) of the following type: \begin{align} \max \; c^Tx \;\; s.t. \\ Ax \leq b \\ d^Tx \leq k \end{align} In other words, the ...
505 views

### Mixed-integer quadratic programming, state of art [closed]

I used Gurobi with a MIQP with 26 binary variables and 26*4 interaction term without any other constraint. The speed is very slow already.... I want to ask what is the state of art of MIQP solvers. ...
453 views

### How to formulate variance minimization as a mixed integer quadratic program

I have a mixed integer quadratic problem and my objective function is as follows $$\arg \min \operatorname{Var}(f(x),g(x)) + \operatorname{Var}(c(x),d(x)) + \cdots$$ where $f$, $g$, $c$ $d$ are ...
119 views

### Comparison of the time efficiency of an optimization problem formulated as a Network Flow model and Mixed Integer Programming

In combinatorial optimization, there are many problems that can be formulated as either Network Flow model or Mixed Integer Programming (MIP), e.g. supply chains, transportation, and graph-base ...
68 views

### Binarization for optimization problems

I have a nonlinear mixed-integer optimization problem, and because of very high complexity when solving it using methods like Branch and Bound, I resorted to solve it using alternating method and ...
92 views

### How to speed up the Mixed-Integer Quadratic Program process?

Currently, I am solving a problem in the format: M is an integer as well. The problem that troubles me is that X is a vector in {0,1} with a size of 7000. I use the solver in https://github.com/...
47 views

317 views

### Nonlinear integer program with linear constraints

I'm trying to perform inference over a subset of the latent variables of a hierarchical hidden Markov model I built. I've derived the relevant optimization problem, but it's a pretty nasty piece of ...
334 views

### MILP formulation and optimization

For $i=1, \dotsc, K$, we have $n_i$ ordered real numbers: $$x_i(1) \leq x_i(2) \leq \dotsc \leq x_i(n_i)$$ I want to solve the following optimization problem: \begin{align} \mathrm{maximize} \; \...
35 views

### How to solve a system of linear equations with binary variables mod 2 with a constraint that is not mod 2?

I am trying to solve a system of $H \leq 4^n$ polynomial equations of degree $H$, where the variables $(x_1, x_2, \ldots, x_{2n}) \in \mathbb{Z}_2^{2n}$ are binary. The problem was that these ...