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:...
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 ...
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 ...
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 ...
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 ...
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$.
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
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
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 \...
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
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
...
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....
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
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 -...
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 ...
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 ...
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
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
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$
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+...
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 ...
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 ...
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\...
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 ...
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 ...
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\\...
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
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.$...
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,...
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\}$ ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
mixed-integer-programming × 345optimization × 174
linear-programming × 173
integer-programming × 105
nonlinear-optimization × 34
operations-research × 33
convex-optimization × 25
mathematical-modeling × 24
discrete-optimization × 24
constraints × 24
binary-programming × 21
linearization × 17
linear-algebra × 11
constraint-programming × 8
combinatorics × 7
graph-theory × 7
algorithms × 7
quadratic-programming × 7
non-convex-optimization × 7
discrete-mathematics × 4
logic × 4
least-squares × 4
relaxations × 4
inequality × 3
reference-request × 3