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:...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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$.
user avatar
  • 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, ...
user avatar
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_{...
user avatar
  • 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 \...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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....
user avatar
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 ...
user avatar
  • 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 -...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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} $$
user avatar
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$
user avatar
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+...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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\...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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\\...
user avatar
  • 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 ...
user avatar
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.$...
user avatar
  • 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,...
user avatar
  • 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\}$ ...
user avatar
  • 34.8k

Only top scored, non community-wiki answers of a minimum length are eligible