16
$\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?

Improve this question
$\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$
    – Michael Feldmeier
    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$
    – LarrySnyder610
    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$
    – Mark L. Stone
    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$
    – Mark L. Stone
    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$
    – LarrySnyder610
    Commented Jun 8, 2019 at 12:17

4 Answers 4

Reset to default
18
$\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.

Improve this answer
$\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$
    – Mark L. Stone
    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$
    – Johan Löfberg
    Commented Jun 26, 2019 at 18:03
  • 1
    $\begingroup$ Writing the title was quick, then it took 3 years of procrastination.. $\endgroup$
    – Johan Löfberg
    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.

Improve this answer
$\endgroup$
9
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ +1 But unfortunately, not freely available to the general public. $\endgroup$
    – Mark L. Stone
    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$
    – Ryan Cory-Wright
    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$
    – Mark L. Stone
    Commented Jun 26, 2019 at 20:33
7
$\begingroup$

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

Improve this answer
$\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.