17
$\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$ Jun 2, 2019 at 5:18

1 Answer 1

24
$\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, 2019 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$ Aug 15, 2019 at 19:40
  • $\begingroup$ Hillier and Lieberman do too. So does Wikipedia. $\endgroup$ Aug 15, 2019 at 23:35

Your Answer

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

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