Questions tagged [mixed-integer-programming]
For questions about optimizations where some of the input variables are constrained to be integers.
55 questions
1
vote
2
answers
129
views
Solving integer equation
I need to find an approximate solution (in the least-squares sense) to the system of linear equations $Ax = y$, where $A$ is a $3\times3$ matrix, and elements of $A$, $x$ and $y$ are all 32-bit ...
- 677
1
vote
1
answer
83
views
Algorithm to find all integer solutions in a bounded domain
I am not sure if this question has been already addressed but I could not find it.
Given a set of positive integer bounds $m_1,m_2,...,m_n$, a set $p_1,p_2,...,p_n$ of values such that $p_i\in\mathbb{...
- 111
1
vote
1
answer
135
views
Is there existing code for solving a Lagrangian Dual problem using the subgradient method?
I know there is a generic code for solving the lagrangian relaxation of an LP. However, for an integer program, sometimes you want some constraints relaxed, but not all. For example, I want the ...
- 11
3
votes
0
answers
113
views
Iterative Solvers for Linear Least Squares with Integer Constraints
The classical linear least squares problem reads $\min_{x\in\mathbb{R}^n}\|Ax-b\|^2_2$ and its solutions satisfy the normal equations $A^{\top}Ax = A^{\top}b$. A standard approach to solve the latter ...
- 3,021
1
vote
2
answers
117
views
Counting solutions to mixed integer linear programs
Say I have a mixed integer linear program in variables $x \in \mathbb{Z}^a, y \in \mathbb{Z}^b, z \in \mathbb{R}^c$ together with linear constraints on $(x,y,z)$. I want to count the number of values ...
- 3,999
2
votes
3
answers
327
views
In linear programming, how can I specify a lower bound for the positive entries in the decision vector
For decision vector $x$, I have a constraint that either $x\leq0$ or $x\geq5$, that is, all positive entries must be at least 5.
Is there a way to cast this under LP? The problem is already a mixed-...
- 492
0
votes
1
answer
174
views
MIP - Large Piecewise Linear Constraints Over Continuous Intervals
I'm currently trying to run a MIP (have access to both Gurobi and CBC) with a piecewise linear function having ~200 intervals for each of the ~30 x values I have. I am using the standard decomposition ...
2
votes
1
answer
192
views
Numerical Simulation of a Quadratic MIP with a highly rational term
I am interested in solving the following minimization problem:
$$
\begin{array}{cl}
\displaystyle\min_{x,y}&\displaystyle\frac{1}{K}\sum_{i=1}^{K}\left(\frac{x_{i}}{y_{i}}-\frac{X}{Y}\right)^{2} \\...
- 169
0
votes
0
answers
29
views
Toggling Constraints in Mixed Integer Programming
Are there MIP solvers that allow certain constraints to be toggled based on the value of a binary variable? My current situation is that I'm approximating the desired behavior by using constraints of ...
- 1
1
vote
0
answers
77
views
Package Assignment problem to maximize profit
Problem description
We have a graph $G=(V,E)$. $V$ is the set of nodes. $c_{ij}$ is the profit of traveling through edge $(i,j)$. $T=\{1,2,3,...\}$ is the set of discrete time steps.
At each time step,...
- 11
0
votes
0
answers
327
views
Complexity of Branch-and-cut algorithm in terms of "Big O"
How can I compute the Big O complexity of the Branch and cut algorithm?
I am solving an integer linear program using MOSEK that includes $M$ binary variables, but I do not know how to calculate the ...
- 11
2
votes
1
answer
202
views
Linearize problem with absolute value
Is there any method to linearize the following optimization problem?
\begin{align}
min_{x,y} &~~ c~[x; y] \\
st &~~ \sum x\leq \alpha_1 \\
&~~ \sum |y|\leq \alpha_2 \\
&~~ \sum y= 0 \\
...
- 121
0
votes
0
answers
42
views
'Items in a bucket' optimizaiton problem?
Sorry for question's silly tittle. I don't quite know how to name my problem, that's why I'm here.
Imagine you wish do add the collumns of you data ('1','2','3'...'30k' etc.) in such a way as to ...
- 109
1
vote
0
answers
142
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 ...
- 11
2
votes
0
answers
149
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 ...
- 21