8
$\begingroup$

Suppose we have the constraint $$a_1x_1 + ... + a_nx_n \gtreqless b,$$ where $a_i$ and $b$ are constants and $x_i$ are decision variables. Suppose also that we want the constraint to hold if $y=1$ (where $y$ is a binary decision variable), and we don’t care whether it holds if $y=0$.

How can we accomplish this?

$\endgroup$
  • 1
    $\begingroup$ Here's another question that I keep answering on other SE sites. $\endgroup$ – LarrySnyder610 May 31 at 15:33
  • 1
    $\begingroup$ You could just refer them to or.stackexchange.com/questions/57/… .And then only answer beyond that if they need additional help. Despite taking a while to formulate, I saved a lot of time answering questions at the CVX Forum with my thread ask.cvxr.com/t/… $\endgroup$ – Mark L. Stone May 31 at 17:12
11
$\begingroup$

These are know as "indicator constraints" or "on/off" constraints. The best formulation is the convex-hull one, it includes the optimal big-M value plus additional non-redundant constraints, here's a note characterizing this formulation: http://www.optimization-online.org/DB_FILE/2014/04/4309.pdf. There's also a generalization for convex nonlinear "on/off" constraints here and recent extensions here.

$\endgroup$
  • 2
    $\begingroup$ Lots of times, "casual" OR users (students taking OR classes, people building small models for a business setting, etc.) want an approach that is easy to code, even if it's not the most efficient computationally. OTOH, people writing production code, solving large problems, writing academic papers, etc. want an approach that is the most efficient computationally, even if it's not the easiest to code. Is it fair to say that the approach you outline here might be most appropriate for the latter type, while the approach I outline in my answer might be most appropriate for the former? $\endgroup$ – LarrySnyder610 Jun 3 at 13:10
  • $\begingroup$ Agreed. Thanks! $\endgroup$ – Hassan Jun 6 at 21:51
9
$\begingroup$

Let $M$ be a new parameter (constant) that equals a large number.

Greater-than-or-equal-to constraints:

The constraint is $a_1x_1 + ... + a_nx_n \ge b$. Rewrite it as $$a_1x_1 + ... + a_nx_n \ge b - M(1-y).$$ Then, if $y = 1$, the constraint is active, and if $y=0$, it has no effect since the right-hand side is very negative.

(If all of the $a_i$ are nonnegative, you can instead use $$a_1x_1 + ... + a_nx_n \ge b(1-y),$$ which is tighter.)

Less-than-or-equal-to constraints:

The constraint is $a_1x_1 + ... + a_nx_n \le b$. Rewrite it as $$a_1x_1 + ... + a_nx_n \le b + M(1-y).$$ Then, if $y=1$, the constraint is active, and if $y=0$, it has no effect since the RHS is very large.

Equality constraints:

The constraint is $a_1x_1 + ... + a_nx_n = b$.. Rewrite it as $$\begin{align*} a_1x_1 + ... + a_nx_n & \le b + M(1-y) \\ a_1x_1 + ... + a_nx_n & \ge b - M(1-y) \end{align*}$$ Then, if $y=1$, the equality constraint is active, and if $y=0$, the constraints have no effect.

Note: If your model is relatively large, i.e., it takes a non-negligible amount of time to solve, then you need to be careful with big-$M$-type formulations. In particular, you want $M$ to be as small as possible while still enforcing the logic of the constraints above.

Related: In an integer program, how I can force a binary variable to equal 1 if some condition holds?

$\endgroup$
  • 1
    $\begingroup$ Even if your model is small, you have to be careful if M is too large relative to the solver integrality tolerance. That point is addressed at the end of my answer in the mega-downvoted thread or.stackexchange.com/questions/57/… . $\endgroup$ – Mark L. Stone May 31 at 17:10
  • 1
    $\begingroup$ @MarkL.Stone I think it would be very helpful to have a standalone Q&A about big-M formulations. Will you write one? I know you prefer the FAQ-type approach, but since it seems the preference of the community is to have multiple, narrower questions, it would be good to have one on big-M. (Plus then you can just link directly to it without having to say "at the end of my answer in..." :) ) $\endgroup$ – LarrySnyder610 May 31 at 19:27
  • $\begingroup$ I will leave the writing to someone else. Mine would probably just get downvoted into oblivion. Someone can take that part of my post and expand and spruce it up. $\endgroup$ – Mark L. Stone May 31 at 20:05

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.