Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [mixed-integer-programming]

2
votes
1answer
25 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: ...
4
votes
1answer
117 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 ...
6
votes
1answer
81 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 ...
4
votes
0answers
46 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 ...
1
vote
0answers
43 views

Help formulating/finding the general class of this problem

Imagine a bus serving a line with N stations. Each station, $i, i=1,…N$, has $s_{ij}$ passengers that want to board the bus to go to $j$, $\forall j \neq i$. (one direction). So there are $\sum_j s_{...
0
votes
1answer
251 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 ...
1
vote
0answers
135 views

Very long running time for Haase and Muller (2014) coded in Python + Gurobi

I have read the paper of Haase and Muller (2014) where they present the linear reformulations of the multinomial logit choice probabilities and compare different approaches. I have tried for an ...
3
votes
1answer
114 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 ...
3
votes
1answer
31 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 ...
4
votes
1answer
198 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 ...
1
vote
2answers
166 views

Breaking symmetries in a (binary) integer program

I want to solve a integer programming problem with binary variables $x_1,\ldots,x_n.$ I have a permutation group $G \leq S_n$ such that for every $f \in G$ the vector $\overline{x}_1,\ldots,\...
1
vote
1answer
191 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 ...
1
vote
1answer
171 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 ...
0
votes
1answer
186 views

Is there general algorithms to solve such 3D cutting problems?

Suppose a cuboid $\mathbb{A}$ has $L$,$M$ and $N$ as its length, width and height respectively, where $L\ge{M}\ge{N}>0$; Now we want to cut $\mathbb{A}$ into smaller cuboids with length $x$, width $...
2
votes
0answers
89 views

Resources for large-scale MILP optimization

With the advent of "big data" applications, different algorithms have to be used to efficiently solve optimization problems, even in the convex case (e.g. the recent success of stochastic gradient ...
1
vote
1answer
217 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 ...
1
vote
3answers
345 views

C++ mixed integer nonlinear programming (MINLP) solver

Doing research project in material involving (mixed integer nonlinear programming) MINLP problem, we want to implement MINLP based on C++, because the majority of our project is based on C++. What ...
0
votes
2answers
246 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} \; \...
1
vote
1answer
104 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 ...
1
vote
1answer
373 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. ...
0
votes
1answer
187 views

prove optimality only by cutting without branching (gurobi)

I have a MIP which I know the solution almost for certain. I want to use gurobi to prove that the true solution (even if it is not the one i provide) shall not lie more than 0.5% deviated from the ...
2
votes
1answer
148 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 ...
1
vote
0answers
112 views

learning Gurobi for MIP calculation [closed]

I am a new learner of Unix, python and Gurobi for MIP calculation. I basically finish reading the quick start guide in Gurobi website but still feel that I need more training to use this combination ...
3
votes
1answer
134 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 ...
2
votes
2answers
175 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: ...
8
votes
4answers
12k 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 ...
3
votes
1answer
60 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 ...
1
vote
0answers
155 views

Good approximate solutions for a MILP problem

The company I work for has been developing an application for real-time control of sewer networks. Every 5 minutes, a MILP problem is built or updated, then solved using Gurobi. For mid-sized cities, ...
4
votes
2answers
171 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 ...
2
votes
1answer
889 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.) ...
3
votes
2answers
568 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 ...
5
votes
3answers
271 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 ...
2
votes
2answers
535 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 ...
4
votes
1answer
260 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 ...
5
votes
2answers
199 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 \...