# Single reference for Mixed Integer Programming formulations to linearize, handle logical constraints and disjunctive constraints, do Big M, etc?

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?

• 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 May 31 '19 at 13:25
• 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. May 31 '19 at 13:26
• 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. May 31 '19 at 13:38
• 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.. Jun 1 '19 at 2:54
• 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. Jun 8 '19 at 12:17

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.

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

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

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.

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.htmlstrong text

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 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 which 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" 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.

• 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; ... May 31 '19 at 18:59
• Yes, those are all good references. Thanks. May 31 '19 at 19:00
• Note that instead of the series of + you can use ----- which sets up a nicer break line. Jun 1 '19 at 19:28
• I took the liberty and changed your YALMIP link to a new page which is much more general (still under development) Jun 26 '19 at 18:03
• Writing the title was quick, then it took 3 years of procrastination.. Jun 27 '19 at 13:03

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.

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

• +1 But unfortunately, not freely available to the general public. Jun 26 '19 at 19:45