15
$\begingroup$

Is there a single crisp and accessible reference which covers how to generate Mixed Integer Programming formulations to linearize products, handle logical constraints and disjunctive constraints, do Big M, et. in optimization problems?

Are there any pitfalls to beware of when using Big M to accomplish any of these?

$\endgroup$
28
  • 1
    $\begingroup$ There is a discussion on meta about whether FAQs and wikis are appropriate at this point. All current answers suggest to wait. If you disagree, please consider participating in the discussion $\endgroup$ Commented May 31, 2019 at 13:25
  • 7
    $\begingroup$ I disagree with this approach for two reasons: (1) I think these questions should be separate, not grouped into a large FAQ. It is easier to search for and find a question and answer if the Q&A are narrow and specific. Moreover, separate Q&As give new users opportunities to vote, as well as to earn reputation points, which beta sites need. (2) I don't like the approach of having a bunch of links in the answer. If it's going to be an FAQ, then the answers should be self-contained. $\endgroup$ Commented May 31, 2019 at 13:26
  • 1
    $\begingroup$ The overwhelming majority of noobies are NOT going to be reading META before posting questions on main. Anyhow, I think FAQs which are technical on topic of the site, belong on main, not META. $\endgroup$ Commented May 31, 2019 at 13:38
  • 1
    $\begingroup$ Given that I produced an answer which covers it all, it is not too broad. I am not of the analysis by the pound school, nor do I think it a bad thing if one question and answer can knock out a broad swath of questions people have. I think that;s much better than cluttering up with questions on every little thing which can be handled at once. I think one stop shopping is good if it delivers. Anyhow, i am in the minority of active people here, so have at it.. $\endgroup$ Commented Jun 1, 2019 at 2:54
  • 1
    $\begingroup$ Oh I agree there is a value to tutorial-style resources for people trying to start a new topic. I just don’t think that’s the best way to answer narrow, specific questions; e.g., if someone wants to know how to linearize a constraint, this Q&A will be more useful than a much longer, more general post with many different topics. $\endgroup$ Commented Jun 8, 2019 at 12:17

4 Answers 4

17
$\begingroup$

Here is a nice, succinct, and easy to understand reference for how to do all this and more. Answers to many future questions can be handled by referencing the appropriate section number in this document and then addressing any particular difficulties or concerns the questioner may have.

FICO MIP formulations and linearizations Quick reference at https://www.msi-jp.com/xpress/learning/square/10-mipformref.pdf


Introductory references which are more tutorial but less comprehensive, which may help people better understand the previously listed reference.

  1. https://ocw.mit.edu/courses/sloan-school-of-management/15-053-optimization-methods-in-management-science-spring-2013/lecture-notes/MIT15_053S13_lec11.pdf

  2. https://ocw.mit.edu/courses/sloan-school-of-management/15-053-optimization-methods-in-management-science-spring-2013/tutorials/MIT15_053S13_tut09.pdf

  3. Logics and integer-programming representations - YALMIP background on how common mixed-integer representable functions and logic can be modeled, which is helpful even if YALMIP is not used. Includes all the usual stuff, plus general integer, sort, number of non-zeros, and much more.


Many of these formulations can be handled under the hood by modern optimization modeling systems.

For instance, indicator constraints in CPLEX.

See:

  1. https://www.ibm.com/support/knowledgecenter/SSSA5P_12.7.0/ilog.odms.cplex.help/CPLEX/UsrMan/topics/discr_optim/indicator_constr/01_indicators_title_synopsis.html

  2. https://www.ibm.com/support/knowledgecenter/SSSA5P_12.7.0/ilog.odms.cplex.help/CPLEX/UsrMan/topics/discr_optim/indicator_constr/07_best_prac.html ,

Note that per https://www.ibm.com/support/knowledgecenter/SSSA5P_12.7.0/ilog.odms.cplex.help/CPLEX/UsrMan/topics/discr_optim/indicator_constr/06_restrictions.html in CPLEX, "The constraint must be linear; a quadratic constraint is not allowed to have an indicator constraint."

Note that per my updated answer at When to use indicator constraints versus big-M approaches in solving (mixed-)integer programs, Indicator Constraints in CPLEX are immune from the big M trickle flow issue mentioned later in this answer under "Be careful with choice of Big M, and its relation to solver integrality tolerance"

Gurobi General Constraints: https://www.gurobi.com/documentation/8.1/refman/constraints.html

YALMIP "implies" automates modeling of some logical constraints: https://yalmip.github.io/command/implies/ Explicit finite lower and upper bounds on all involved variables are required so that a Big M formulation can be derived under the hood by YALMIP to handle the implies.


Be careful with the choice of Big M, and its relation to solver integrality tolerance.

Keep in mind, as the YALMIP developer Johan Lofberg has stated, that Big M is misnamed. It should be called just big enough M. Excessively large M can result in weak formulations which degrade (slow down) the solution process. In extreme cases (but not uncommon for "amateurs"), as a result of solver constraint satisfaction tolerance, an excessively large value of M can cause the solver to produce a solution that violates the logic constraint as intended. That is because integer (including binary) constraints are only satisfied to within an integrality tolerance, which typically is 1e-5 or 1e-6.

Further details are provided by @prubin at https://orinanobworld.blogspot.com/2018/04/big-m-and-integrality-tolerance.html. IBM CPLEX documentation refers to this as "trickle flow" here: https://www-01.ibm.com/support/docview.wss?uid=swg21399984

If M needs to be so big that it would cause the logic constraint to not be satisfied as intended, the integrality tolerance should be made smaller, and verified to be small enough. Proper scaling of the problem can in many cases ameliorate such difficulties and allow for a not very large M.

$\endgroup$
8
  • 9
    $\begingroup$ Some further references, off the top of my head, in no particular order: [1] "Model Building in Mathematical Programming" by H. Paul Williams; [2] Chapter 7 of AIMMS' Optimization Modeling Guide; [3] Chapter 9 of MOSEK's Modeling Cookbook; ... $\endgroup$
    – fbahr
    Commented May 31, 2019 at 18:59
  • $\begingroup$ Yes, those are all good references. Thanks. $\endgroup$ Commented May 31, 2019 at 19:00
  • $\begingroup$ Note that instead of the series of + you can use ----- which sets up a nicer break line. $\endgroup$
    – TheSimpliFire
    Commented Jun 1, 2019 at 19:28
  • 1
    $\begingroup$ I took the liberty and changed your YALMIP link to a new page which is much more general (still under development) $\endgroup$ Commented Jun 26, 2019 at 18:03
  • 1
    $\begingroup$ Writing the title was quick, then it took 3 years of procrastination.. $\endgroup$ Commented Jun 27, 2019 at 13:03
11
$\begingroup$

I recommend Formulating Integer Linear Programs: A Rogues' Gallery:

The article[1] is very accessible, clear, and has multiple examples of using binary variables to achieve logical constraints. Full citation below.

[1] Gerald G. Brown, Robert F. Dell, (2007) Formulating Integer Linear Programs: A Rogues' Gallery. INFORMS Transactions on Education. 7(2):153–159. http://dx.doi.org/10.1287/ited.7.2.153. Also available from https://faculty.nps.edu/gbrown/docs/Rogues_Gallery.pdf.

$\endgroup$
9
$\begingroup$

What about Mixed Integer Linear Programming Formulation Techniques, J.P. Vielma, SIAM Rev., 57(1), 3–57, 2015?

$\endgroup$
5
  • $\begingroup$ +1 But unfortunately, not freely available to the general public. $\endgroup$ Commented Jun 26, 2019 at 19:45
  • $\begingroup$ My bad :( Maybe you could specify that in your original question. If you need this reference, please contact me. $\endgroup$
    – rocarvaj
    Commented Jun 26, 2019 at 19:58
  • 4
    $\begingroup$ It should be publicly available via dspace dspace.mit.edu/handle/1721.1/96480. $\endgroup$ Commented Jun 26, 2019 at 20:08
  • 2
    $\begingroup$ Thanks @RyanCory-Wright ! I just updated the link. $\endgroup$
    – rocarvaj
    Commented Jun 26, 2019 at 20:22
  • 1
    $\begingroup$ @Ryan Cory-Wright I have the hard copy from SIAM membership. I'm an MIT alum and I didn't even know about DSpace before - thanks. $\endgroup$ Commented Jun 26, 2019 at 20:33
7
$\begingroup$

Another resource is "Strategies for “Not Linear” Optimization" from the AMPL group.

$\endgroup$

Your Answer

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

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