12
$\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$
  • 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 May 31 '19 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 May 31 '19 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 May 31 '19 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 Jun 1 '19 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 Jun 8 '19 at 12:17
15
$\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.

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.

See 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

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

| improve this answer | |
$\endgroup$
  • 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 May 31 '19 at 18:59
  • $\begingroup$ Yes, those are all good references. Thanks. $\endgroup$ – Mark L. Stone May 31 '19 at 19:00
  • $\begingroup$ Note that instead of the series of + you can use ----- which sets up a nicer break line. $\endgroup$ – TheSimpliFire Jun 1 '19 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 Jun 26 '19 at 18:03
  • 1
    $\begingroup$ Writing the title was quick, then it took 3 years of procrastination.. $\endgroup$ – Johan Löfberg Jun 27 '19 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$
  • $\begingroup$ +1 But unfortunately, not freely available to the general public. $\endgroup$ – Mark L. Stone Jun 26 '19 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 Jun 26 '19 at 19:58
  • 3
    $\begingroup$ It should be publicly available via dspace dspace.mit.edu/handle/1721.1/96480. $\endgroup$ – Ryan Cory-Wright Jun 26 '19 at 20:08
  • 2
    $\begingroup$ Thanks @RyanCory-Wright ! I just updated the link. $\endgroup$ – rocarvaj Jun 26 '19 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 Jun 26 '19 at 20:33
6
$\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, privacy policy and cookie policy

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