17

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?

LarrySnyder610
  • 13,141
  • 3
  • 41
  • 105
  • 3
    just a suggestion to improve the post, perhaps it would be better to include examples where they seems to mean different things? – Siong Thye Goh Jun 02 '19 at 05:18

1 Answers1

25

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.

LarrySnyder610
  • 13,141
  • 3
  • 41
  • 105
  • 2
    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. – bassen Jun 02 '19 at 13:13
  • 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. – Jeff Linderoth Aug 15 '19 at 19:40
  • Hillier and Lieberman do too. So does Wikipedia. – LarrySnyder610 Aug 15 '19 at 23:35