# Tag Info

18

Here is the advice in the IBM CPLEX documentation. So this pertains to CPLEX. I don't know to what extent it applies to other solvers. First of all, indicator constraints may not be available in all situations: Indicator Constraints in Optimization The constraint must be linear; a quadratic constraint is not allowed to have an indicator constraint. ...

15

For Gurobi there seems to be a dual advantage of using general constraints (http://www.gurobi.com/documentation/8.1/refman/constraints.html#subsubsection:GeneralConstraints): Benefit number one - models are easier to create and can be interpreted easily: If a model contains general constraints, then Gurobi adds the respective MIP formulations for those ...

13

To the best of my knowledge the indicator constraints are just syntactic sugar for the user. Internally these indicator constraints are reformulated using computed big-M formulations or SOS constraints (special ordered set constraints). It might be that you are better at computing the value of the big-M using additional knowledge that the solver does not ...

10

Question by me at the IBM CPLEX Forum: Are indicator constraints immune to trickle flow or other numerics-induced logic "errors"? Are indicator constraints immune to trickle flow or other numerics-induced logic "errors"? As discussed at IBM Technote: Why does a binary or integer variable take on a noninteger value in the solution?, depending on ...

8

You want to enforce $$\left(\bigwedge_{i \in I} \lnot x_i\right) \implies \sum_{j \in J} x_j = n.$$ Introduce a new binary variable $y$ and enforce $$\left(\bigwedge_{i \in I} \lnot x_i\right) \implies y$$ and $$y \implies \sum_{j \in J} x_j = n.$$ For the first implication, conjunctive normal form yields \begin{align} \left(\bigwedge_{i \in I} \lnot x_i\...

7

First question: Yes, your algebraic formulation is correct. Second question: I would lean toward using the algebraic formulation, for two reasons. First, it is not solver-specific. Second, a reader not familiar with indicator constraints will find interpreting the algebraic formulation a bit easier, while a reader familiar with indicators is not likely to ...

7

Answers to the linked question mention both big-M constraints and semicontinuous variables. To speed up the big-M approach, you might consider introducing the constraints dynamically only as they are violated ("row generation" or "cut generation"). Explicitly: Omit all big-M constraints and the associated binary variables. Solve the ...

7

Introduce binary variable $y_0$ and linear constraints: \begin{align} y_0 + y_1 + y_2 &= 1\\ 1y_0 + 2y_1 + 3y_2 &= x \end{align} Equivalently, eliminating $y_0$: \begin{align} y_1 + y_2 &\le 1\\ 1 + y_1 + 2y_2 &= x \end{align}

7

Introduce a binary variable $y_{i,j}$ and linear constraints \begin{align} x_{i,j} &\le M y_{i,j} \tag1 \\ y_{i,j} + y_{j,i} &\le 1 \tag2 \end{align} Constraint $(1)$ enforces $x_{i,j} > 0 \implies y_{i,j} = 1$. Constraint $(2)$ enforces $y_{i,j} = 1 \implies y_{j,i} = 0$. Constraint $(1)$ (with the roles of $i$ and $j$ interchanged) enforces $y_{... 7 Without using a small epsilon, you can’t enforce strict inequality. Here’s one approach that allows ambiguity at the endpoints of each interval, as your proposed constraint does: $$x+y+z=1\\ 0x+\frac{1}{3}y+\frac{2}{3}z \le \text{cond} \le \frac{1}{3}x+\frac{2}{3}y+1z$$ 6$a \geq M_1xa \leq M_2 - (M_2+eps)xb = K_1 + (K_2-K_1)xM_1 < 0$bigM for the lower bound on$aM_2 > 0$bigM for the upper bound on$ax$binary variable equal to$1$if$a < 0$,$0$otherwise (i.e.$a \geq 0$)$eps$tolerance 6 You can have a look at SCIP's implementation in cons_indicator. They say that: An indicator constraint is given by a binary variable$z$and an inequality$ax \le b$. It states that if$z=1$then$ax \le b$holds. This constraint is handled by adding a slack variable$s: ax−s \le b$with$s \le 0$. The constraint is enforced by fixing$s$to$0$if$z=1$. ... 5 Here's a big-M formulation that does not depend on the objective. (Minimization with positive objective coefficients for$u$and$d$could be exploited, but you don't have that here.) Let$\epsilon > 0$be a small tolerance for positivity of$c$. Let$\underline{c}$and$\overline{c}$be bounds for$c$, with similar notation for$w$,$u$, and$d$. Let ... 5 I assume that$w_i$is a continuous variable with$0 \le w_i \le 1$and$w_i^\text{start}$is a constant with$0 \le w_i^\text{start} \le 1$. You want to enforce $$|w_i-w_i^\text{start}| > 0 \implies |w_i-w_i^\text{start}| \ge 0.02.$$ You can introduce binary variables$y_i^+$and$y_i^-and linear big-M constraints: \begin{align} 0.02 y_i^+ \le w_i - ... 5 LetM_i$be an upper bound on$Q_i$, and impose linear big-M constraints$0 \le Q_i \le M_i x_i$. 5 in OPL CPLEX you could directly use logical constraints and write int m=7; range r=1..m; int n=2; {int} I={i | i in r : i mod 2==1}; {int} J={i | i in r : i mod 2==0}; assert card(I inter J)==0; dvar boolean x[r]; subject to { (sum(i in I) x[i]==0) => (sum(j in J) x[j]==n); } 5 If$M$is a (small) upper bound on$x$, introduce a binary variable$z$and big-M constraint$x \le M z$. The idea is that$x>0$implies$z=1$. Now use$B z$in the objective. 5 Consider the following tiny example. You have two factories, one warehouse and two product. Factory 1 can produce both goods in sufficient quantity to meet demand but has a very large cost coefficient. Factory 2 only produces the second product, with adequate capacity and a small cost coefficient. The optimal solution to the original problem is to ship ... 4 To get the second largest variable when all are nonnegative and at most two can be nonzero, just take the sum of all of them and subtract the largest. 4 $$x \le z + M(1-\beta) \\ x \ge z - M(1-\beta) \\ x' \le z + M\beta \\ x' \ge z - M\beta \\$$ If$\beta=1$, we have $$x \le z \\ x \ge z \\ x' \le z + M \\ x' \ge z - M \\$$ which leads to$x=z$and$x'$unconstrained. And likewise if$\beta=0$. 4 I would like to remind that CPLEX can handle "if then" directly through logical constraints. In OPL for example: int nbKids=300; float costBus40=500; float costBus30=400; dvar int+ nbBus40; dvar int+ nbBus30; minimize costBus40*nbBus40 +nbBus30*costBus30; subject to { 40*nbBus40+nbBus30*30>=nbKids; // with if nb buses 40 more than 3 then nb ... 4 You can introduce a binary variable$x_kand linear constraints \begin{align} \sum_k x_k &\ge N\tag1\\ -t_k+T_k&\le M_k(1-x_k) &&\text{fork\in K}\tag2 \end{align} Here, the “big-M” constantM_k$is a small upper bound on$-t_k+T_k$. Because$t_k\ge 0$, you can take$M_k=T_k$, and the constraint simplifies to$t_k\ge T_k x_k$. Constraint$...

4

I'm only aware of a mechanism that works if there is an upper bound for the continuous variable. \begin{align}x_{t, \max}\cdot b_t &\geq x_t\\ m\cdot x_t &\geq b_t\end{align} I used this in answering this question. I'm not aware of a way to solve it for unbounded $x_t$, unless the solver handles floating points infinities correctly. This would need ...

4

Enforcing $b_t$ to take value $1$ when $x_t$ is positive is done with $x_t \le b_t$, assuming $x_t \le 1$. For the second part, quoting @MarkL.Stone: You will have to choose a tolerance as to how close to zero should be considered zero Let $\epsilon$ be this tolerance. So you want to enforce $$x_t < \epsilon\implies b_t = 0$$ Now referring to this ...

3

The answer to the first part is yes, provided that you are using a solver that supports indicator constraints. As far as I know, there is no "standard" notation for it. Something like $$a_1 x_1 \le b \implies x_2 = 0$$would seem reasonable to me. The "else" part is tricky, since it deals with the case $a_1 x_1 > b$ and strict inequalities are a no-no. You ...

3

It sounds like you want to enforce the following logical proposition: $$\bigvee_{i=6}^{10} (x_i>0) \implies \bigwedge_{j=1}^{5} (x_j=1)$$ You can model this by introducing a binary variable $y$ and linear constraints: \begin{align} x_i &\le y&&\text{for $i\in\{6,\dots,10\}$}\\ y&\le x_j &&\text{for $j\in\{1,\dots,5\}$}\\ \end{...

3

You can use conjunctive normal form to derive the desired constraints. The first one is: $$a \ge b \implies a\ge c\\ (b \implies a) \implies (c \implies a)\\ \lnot(\lnot b \lor a) \lor (\lnot c \lor a)\\ (b \land \lnot a) \lor (\lnot c \lor a)\\ (b \lor \lnot c \lor a) \land (\lnot a \lor \lnot c \lor a)\\ (b \lor \lnot c \lor a)\\ b+ 1- c +a \ge 1\\ a+b \... 3 To enforce x = 1 \implies y = 1 for binary variables x and y, impose linear constraint x \le y. You can derive this constraint via conjunctive normal form:$$ x \implies y \\ \lnot x \lor y \\ (1 - x) + y \ge 1 \\ x \le y $$3 Let y be a binary variable and let f be a linear function bounded above by some constant M. The standard approach to enforce y=1 \implies f\le 0 is to impose linear big-M constraint$$f\le M(1-y)\tag1. All four of your implications are of this form. For the first one, take $y=\beta$ and $f=z-x$ in $(1)$, yielding $z-x\le M(1-\beta)$. For the ...

3

This type of constraint is called a complementarity constraint, and there are several ways of modeling it, two of them you already mentioned. There is no silver-bullet formulation: some will work better than others depending on your instance, your solver, etc. Some solvers support complementarity constraints directly, for instance Knitro or PATH. If you ...

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