16
$\begingroup$

I’ve seen the "big-$M$ method" referred to in different ways. What is the "big-$M$ method" and why does it seem to mean two different things?

$\endgroup$
1
  • 3
    $\begingroup$ just a suggestion to improve the post, perhaps it would be better to include examples where they seems to mean different things? $\endgroup$ – Siong Thye Goh Jun 2 '19 at 5:18
21
$\begingroup$

People do use the term "big-$M$ method" to mean two different things. In both cases, the name refers to the use of a large constant, often denoted $M$.

The first use of the term refers to a method for finding an initial feasible solution for the simplex method. (Another common method for doing this is the two-phase method.)

Sometimes people also use the term "big-$M$ method" to refer to the use of big-$M$ parameters in logical constraints in (mixed-)integer programming problems. For example: if $x$ is a continuous variable and $y$ is a binary variable, then the constraint $$x \le My$$ says that if $y=0$, then $x$ must equal 0, and if $y=1$, then the constraint places no restrictions on $x$. Note that in this case, it’s important not to choose a value of $M$ that is too large.

Aside: I highly recommend @prubin's excellent blog post on big-$M$ in all its forms.

$\endgroup$
3
  • 2
    $\begingroup$ Most common might be dependent on background: As an OR researcher coming from a CS background, the MIP usage was the only one I ever saw. I only saw the LP meaning when I read Winston's book in preparation for teaching an OR optimization class. $\endgroup$ – bassen Jun 2 '19 at 13:13
  • $\begingroup$ I think Winston is the only person who refers giving a huge infeasibility penalty in the simplex method as the "big-M" method. But I could be wrong. $\endgroup$ – Jeff Linderoth Aug 15 '19 at 19:40
  • $\begingroup$ Hillier and Lieberman do too. So does Wikipedia. $\endgroup$ – LarrySnyder610 Aug 15 '19 at 23:35

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.