7
$\begingroup$

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?

$\endgroup$

2 Answers 2

8
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ Thank you. Your answer was exactly what I was looking for. Now it works like a charm $\endgroup$
    – kc27
    Commented Sep 19, 2022 at 18:59
  • $\begingroup$ "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. $\endgroup$
    – Stef
    Commented Sep 20, 2022 at 12:48
  • $\begingroup$ True, but for numerical purposes, it is better to have the tighest bound possible for each constraint. $\endgroup$
    – Kuifje
    Commented Sep 20, 2022 at 12:51
3
$\begingroup$

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
 costBus40*nbBus40  +nbBus30*costBus30;
 
subject to
{
 40*nbBus40+nbBus30*30>=nbKids;
 
 // SOS1
 (nbBus40>=1)+(nbBus30>=1)<=1;
} 
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.