Set constraint mip

Question

I am programming a MIP problem. There are two continuous variables but only one can have a value and the other must then be zero. How do I give this as a constraint?

score 8 · Accepted Answer · answered Sep 19 '22 at 16:15

8

Let $x_1$ and $x_2$ denote your continuous variables. Introduce binary variables $y_1$ and $y_2$ and impose the following constraints:

$x_1 > 0 \; \Longrightarrow \; y_1 = 1$: $$ x_1 \le My_1 $$
$x_2 > 0 \; \Longrightarrow \; y_2 = 1$: $$ x_2 \le My_2 $$
$y_1$ and $y_2$ cannot be active simultaneously: $$ y_1 +y_2 \le 1 $$

$M$ is an upper bound on your variables. If you have different upper bounds for $x_1$ and $y_2$, use two different values of $M$.

answered Sep 19 '22 at 16:15

Kuifje

13,324
1
23
56

Thank you. Your answer was exactly what I was looking for. Now it works like a charm – kc27 Sep 19 '22 at 18:59
"M is an upper bound on your variables. If you have different upper bounds for x1 and y2, use two different values of M" This sentence is not necessary. If M1 is an upper bound on x1 and M2 is an upper bound on x2, then M = max(M1,M2) is an upper bound on both x1 and x2. – Stef Sep 20 '22 at 12:48
True, but for numerical purposes, it is better to have the tighest bound possible for each constraint. – Kuifje Sep 20 '22 at 12:51

score 3 · Answer 2 · answered Sep 20 '22 at 07:45

With many MIP solvers, you can use SOS constraints. (SOS Type 1 is a set of variables where at most one variable may be nonzero.)

SOS1 example with cplex docplex python api: from docplex.mp.model import Model

mdl = Model(name='buses')
nbbus40 = mdl.integer_var(name='nbBus40')
nbbus30 = mdl.integer_var(name='nbBus30')
mdl.add_constraint(nbbus40*40 + nbbus30*30 >= 300, 'kids')
mdl.minimize(nbbus40*500 + nbbus30*400)
mdl.solve()
for v in mdl.iter_integer_vars():
    print(v," = ",v.solution_value)
print("and with SOS1")
mdl.add_sos1([nbbus40,nbbus30])
mdl.solve()
for v in mdl.iter_integer_vars():
    print(v," = ",v.solution_value)

Or you can also write your SOS1 with logical constraints. For instance, in OPL

int nbKids=300;
float costBus40=500;
float costBus30=400;
dvar int+ nbBus40;
dvar int+ nbBus30;
minimize
 costBus40nbBus40  +nbBus30costBus30;
subject to
{
 40nbBus40+nbBus3030>=nbKids;
// SOS1
 (nbBus40>=1)+(nbBus30>=1)<=1;
}

Set constraint mip

2 Answers2