26
votes
Accepted
How to write if else statement in Linear programming?
This can not be formulated as a linear programming problem. We need extra binary variables and end up with a MIP.
First we do:
$$ a > b \Longleftrightarrow \delta = 1$$
This can be formulated as:...
- 4,377
6
votes
Linearize optimization problem with absolute value
For each $y_i$, introduce nonnegative variable $z_i$ to replace $|y_i|$, and impose linear constraints $-z_i \le y_i \le z_i$.
- 52.5k
5
votes
Accepted
Convert fractional to quadratic integer programming
Yes, one way is to introduce two new variables $t_1$and $t_2$ and maximize $t_1+t_2$with the constraints $f_1(x,y) \geq t_1$ and $f_2(x,z) \geq t_2$. Now multiply with denominators and you will have ...
- 9,787
5
votes
Accepted
How to linearize the product of a non-binary discrete variable and a continuous variable?
If you can bound $y_j$ by some (not too large) positive integer $Y$, so that $y_j\in \{0,1,\dots,Y\}$, you can introduce binary variables $z_0, z_1,\dots,z_Y$ and add the following constraints:$$\sum_{...
- 5,488
5
votes
Accepted
Doing a Charnes-Cooper transformation with matrices and an zero-one constraint
The shape of the decision variables (matrix versus vector) does not matter. Yes, $\alpha=\beta=0$ in your case. The idea of the transformation is that you multiply both numerator and denominator by a ...
- 52.5k
5
votes
Accepted
Any nice/good way to allow an "or" option in a linear program?
You can enforce $f \le K \lor g \le M$ by introducing a binary decision variable $x$ and linear "big-M" constraints:
\begin{align}
f - K &\le M_1 x \tag1 \\
g - M &\le M_2(1-x) \tag2
...
- 52.5k
5
votes
Accepted
Resources to learn about modeling within the scope of Linear/Integer programming?
There are a number of books, including "Model Building in Mathematical Programming" by H. P. Williams and "Applications of Optimization with XpressMP" by Guéret et al., that ...
- 5,488
5
votes
How do I transform the following set of conditions into inequalities?
I guess: $2x+y+z\geq 2$.
For $x=0$ you need to have $y=z=1$ to satisfy this. If $x=1$ then it is true independently of what $y,z\in\{0,1\}$ are.
- 2,172
5
votes
Accepted
Problem-Heavy References in Linear/Integer/etc. Programming and Operations Research
I recommend Model Building in Mathematical Programming by H. Paul Williams. Formulations, SAS code, and output for all 29 examples are included in the SAS documentation here.
- 52.5k
5
votes
Accepted
Can I linearize this piecewise function so it can be used in an objective function for my LP optimization model?
Your piecewise-linear function is concave and so cannot be linearized without introducing a binary variable. If it were instead convex, you could use linear programming.
- 52.5k
4
votes
Accepted
Convex constraint in a Mixed-Integer Program
Yes, from the generic $x^TR^TRx \leq c^Tc+b$ being SOCP representable as $\left|\left|\begin{matrix}2Rx\\1-(c^Tx+b)\end{matrix}\right|\right|\leq 1+c^Tx+b$
- 9,787
4
votes
Accepted
What is the fastest mixed-integer convex programming software?
CVXGEN only addresses LPs and convex QPs. So I am guessing you are interested in convex Mixed Integer QPs (MIQPs), or perhaps MILPs. Those are addressed, by among others, GUROBI, CPLEX, and MOSEK, ...
- 4,656
4
votes
Accepted
Forming the Laplacian Form of the Max Cut Problem
Simple case & intuitive explanation
The elements of the (simple -- i.e., weights $0$ or $1$) graph Laplacian are given by (from Wikipedia):
$$
L_{ij}:=
\begin{cases}
\deg(v_i),& \text{if } ...
- 635
4
votes
Accepted
Division in linear program
You have $x\leq c$ when $y=0$ and $x + \frac{1}{g(x)} \leq c$ when $y=1$.
Let $U$ be an upper bound on $z$. Introduce $U+1$ binaries $\delta_i$ to represent which value $z$ has, $z = \sum_{i = 0}^U \...
- 9,787
4
votes
Accepted
When is the polyhedron associated with a mixed-integer program different from the polyhedron associated with its LP-relaxation?
Consider the MIP with one variable $x$ and constraints $-\frac12\leq x\leq \frac12,\ x\in\mathbb{Z}$. Then $P_{IP}=\{0\}$ and $P_{LP}=[-\frac12,\frac12]$.
You always have $P_{IP}\subseteq P_{LP}$ but ...
- 4,210
4
votes
Accepted
Linear/Integer Programming: Scheduling task with regular intervals
Yes, integer programming is a natural choice. You can link $x$ and $y$ via
$$\sum_j j x_{i,j,k} = y_{i,k}$$
An alternative formulation is to use network flow in a time-space network with a node $(i,...
- 52.5k
4
votes
Accepted
MIP modelling of piecewise linear function
Introduce a binary variable $z_i$ for each segment and impose the following linear constraints:
\begin{align}
z_1 + z_2 + z_3 &= 1 \\
0z_1 + 5z_2 + 10z_3 \le x &\le 5z_1 + 10z_2 + 20z_3 \\
L_1(...
- 52.5k
4
votes
Conditional constraint activated by binary variable
You have the bilinear equality constraint $T_i(t+1) = z_t T_c(t) +(1-z_t)T_i(t)$. In this, you can linearize the binary times continuous expression using a standard big-M model.
https://or....
- 9,787
4
votes
Accepted
Reformulate indicator function using mixed integer program
Let $\epsilon>0$ be a small constant tolerance,
introduce binary variables $y_i$ to represent the indicator, and impose linear constraints
\begin{align}
\sum_i y_i &\le m \tag1 \\
b - a_i x + \...
- 52.5k
4
votes
Accepted
Mixed Integer Programming - variable that equals the sign of an expression
Let $\epsilon>0$ be a small constant tolerance and impose
$$Ly + \epsilon(1-y) \le x - \text{th} \le 0y + U(1-y)$$
Then $y = 1 \implies L \le x-\text{th} \le 0$, and $y = 0 \implies \epsilon \le x -...
- 52.5k
4
votes
Accepted
Shortest palindromic Egyptian representation for reciprocal integers
I wrote this Java code to do a systematic search for representations as follows. To find representations of length $l$, for the first $l-2$ denominators I tried all palindromic integers up to and ...
- 243k
4
votes
Accepted
Indicator constraint in optimization
You want to enforce two implications:
\begin{align}
x \le c &\implies y = 1 \\
x > c &\implies y = 0
\end{align}
Equivalently, you want to enforce their contrapositives:
\begin{align}
y = ...
- 52.5k
4
votes
Accepted
Tractable formulation of a mixed integer program
You can linearize the problem as follows. Introduce nonnegative decision variables $y_i$ to represent $|c_i A_1 x_i|$, change the objective to minimizing $\sum_i y_i$, let $M_i$ be a small constant ...
- 52.5k
4
votes
LP relaxation leads to exponential Branch & Bound
This example was constructed by Jeroslow in 1974, and you can find a proof in this paper:
Jeroslow, Robert G. "Trivial integer programs unsolvable by
branch-and-bound." Mathematical ...
- 52.5k
3
votes
Accepted
MILP constraints with truth table
$$\begin{align} & 350 \cdot \delta \le x \le 349.99 + \delta\cdot (U-349.99)\\
&\delta \in \{0,1\}\\
& 0 \le x \le U
\end{align} $$
- 4,377
3
votes
Accepted
Cycle elimination constraint in a directed graph
The key is that $W$ is a possible set of all "parents" (sources linked to) $u$. So the "parent sets" of nodes 1 through 4 are, respectively, {4, 5} (parents of 1), {1, 6}, {2, 7}, and {3, 8}. For the ...
- 5,488
3
votes
Accepted
Linear Programming: "at most k out of n variables nonzero" constraint
Internally, a solver is probably going to treat each of your SOS1 constraints a lot like a binary variable -- basically, branch on $w_i$ and, in the $w_i = 1$ branch, force $v_i = 0$. The good news is ...
- 5,488
3
votes
Accepted
MILP: Minimizing $|Ax-b|$ with at most 5 x variables being non-zero
With the MATLAB Toolbox YALMIP (disclaimer, developed by me), it would be
...
- 9,787
3
votes
What is the answer linear programming?
When I implemented the model (using AMPL/CPLEX), I got the same results as you did.
However, note that the given solution is not feasible for the given model. E.g., for the first constraint ($gt_1+...
- 295
Only top scored, non community-wiki answers of a minimum length are eligible