7
$\begingroup$

There are two non-negative integer variables $q$ and $p$, where only one of them can take a positive value. To impose this relation, I write: \begin{align} q &\leq M(1 - y) \tag1 \\ p &\leq M(y) \tag2 \end{align}

where $y$ is binary and $M$ is a large number.

Is there a better way to model this relation, possibly without binary and/or big-M?

$\endgroup$
10
$\begingroup$

The big-M values need not be the same. You should choose $M_1$ in $(1)$ to be a small upper bound on $q$ and $M_2$ in $(2)$ to be a small upper bound on $p$.

An alternative formulation is $p q = 0$, but that is nonlinear.

If your solver supports indicator constraints, you can write the desired implications directly, without specifying big-M: \begin{align} y = 1 &\implies q = 0 \\ y = 0 &\implies p = 0 \end{align} But the solver might just introduce the big-M constraints on your behalf.

If your solver supports SOS1 constraints, you can use those, but again these might be automatically converted to big-M constraints.

$\endgroup$
3
  • 2
    $\begingroup$ Is it correct to say that it’s impossible to do this using only continuous variables and a linear formulation? $\endgroup$ – LarrySnyder610 Jan 19 at 14:19
  • 4
    $\begingroup$ Yes, because the L-shaped feasible region (union of two nonnegative axes) is nonconvex. $\endgroup$ – RobPratt Jan 19 at 14:54
  • $\begingroup$ OK, I figured there was a nice compact explanation. :) $\endgroup$ – LarrySnyder610 Jan 19 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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