18
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:...
- 3,892
5
votes
Accepted
Binary integer variables in linear programming
Note that
$$\begin{array}{rl} x_1 = 0 \lor x_1 \geq 10 &\equiv (x_1 \geq 0 \land x_1 \leq 0) \lor x_1 \geq 10\\\\ &\equiv x_1 \geq 0 \land (x_1 \leq 0 \lor x_1 \geq 10)\end{array}$$
We can ...
- 19.1k
5
votes
Binary integer variables in linear programming
Using an extra binary variable $\delta$ we can write:
\begin{align} & 10 \delta \le x_1 \le 300 \delta \\
&\delta \in \{0,1\}
\end{align}
$x_1$ is called a semi-continuous ...
- 3,892
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,062
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 ...
- 34.8k
5
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$.
- 34.8k
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,201
4
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_{...
- 4,020
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,062
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 ...
- 3,732
4
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
...
- 34.8k
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,062
4
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 ...
- 4,020
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 -...
- 34.8k
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 ...
- 4,020
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 ...
- 4,020
3
votes
Accepted
Mixed-Integer Bilinear Program (MIBLP) with linear constraints
Here are some hints:
Linearize $z_{i,j}=x_i y_j$ and you can solve this as a standard MIP (Mixed Integer Programming) problem.
If the problem is convex use a standard MIQP (Mixed Integer Quadratic ...
- 3,892
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} $$
- 3,892
3
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,062
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
3
votes
Accepted
Technique to improve MIP solve time
I gave that talk. The term "slice" for iterating over a subset of indicies based on an outer set of indicies was originally invented by Robert Fourer for AMPL (AFAIK). I believe this term appears in ...
- 146
3
votes
Accepted
mixed integer programming formulation for n jobs on m machines with preceding constraints
Your problem is called $P\mid\text{prec}\mid C_\text{max}$ in the notation of Graham et al. (1979). You can find MIP models and some computational results in Wang, Parallel machine scheduling with ...
- 393
3
votes
Accepted
Mixed-integer LP formulation with equality indicator functions in constraints
$w_i$ larger than $K_2$ or $0$ is called semi-continuous, and is a logic supported natively in some solvers. To model it manually with a big-M strategy, you would do $-M\delta_i \leq w_i \leq M\...
- 9,062
3
votes
Accepted
Algorithms to optimize over an interval union a singleton.
These are called semicontinuous variables. Because $x_i$ has an implied finite upper bound of $B$, you can model this situation by introducing a binary variable $y_i$ and linear constraints:
$$c_i ...
- 34.8k
3
votes
Accepted
Problem with big-M logical constraints
You were on the right track with two additional binary variables and two big-M constraints. For the implication $y_1=1 \implies u_1>0$, you can enforce instead $y_1=1 \implies u_1\ge \epsilon$ for ...
- 34.8k
3
votes
Accepted
Formulating Constraints into Mixed-Integer Linear Programming
Introduce a small constant tolerance $\epsilon > 0$, binary decision variables $y_i^1$ and $y_i^2$, and linear constraints
\begin{align}
y_i^1 + y_i^2 &\le 1 &&\text{for all $i$} \tag1\\...
- 34.8k
3
votes
Linearize objective function for intlinprog
Every time you have an objective of the form
$$\mathrm{minimize} \sum_i p_i|u_i|$$
where $u_i$ are some variables or linear expressions of other variables, and $p_i$ are nonnegative constants, you can ...
- 3,732
3
votes
Accepted
Multilevel integer programming
One way to restrict $x$ to a discrete set $\lbrace a_1,\dots,a_n\rbrace$ is to create $n$ binary variables $z_1,\dots,z_n$ and add the constraints $$x=\sum_{i=1}^n a_i z_i$$ and $$\sum_{i=1}^n z_i =1.$...
- 4,020
3
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,...
- 34.8k
3
votes
Accepted
Mathematical formulation of an optimization problem
You can solve the problem via integer linear programming as follows. For each pair $(i,j)$ with $1 \le i \le j \le n$, let binary decision variable $x_{i,j}$ indicate whether part $\{a_i,\dots,a_j\}$ ...
- 34.8k
Only top scored, non community-wiki answers of a minimum length are eligible