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?
$\begingroup$
$\endgroup$
1
asked Jun 2, 2019 at 2:19
-
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 GohJun 2, 2019 at 5:18
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
answered Jun 2, 2019 at 2:19
-
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$– bassenJun 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
-