The rational fear of irrational coefficients: Talking about IP on PI day

One of the central elements of (Mixed-) Integer Linear Programming is the polyhedral approach. The feasible set of a Linear Program is a polyhedron, where a vertex (if there is one) is optimal for any linear objective function where an optimal solution exists. In the case of MILPs, however, the integrality constraint on some variables breaks down the feasible set S into disjoint polyhedra. Nevertheless, the first reasonable attempt at solving any MILP consists of replacing S with the linear relaxation P defined by the linear constraints of the formulation alone. Then we can run the “wish-me-luck” algorithm:

The wish-me-luck algorithm:
1.     Ignore the integrality constraints and solve the MILP as an LP.
2.     If the integrality constraints are satisfied, we are done!
3.     Otherwise, we are (temporarily) doomed!

DSC09669bSometimes the gamble is guaranteed. If we can find a polyhedron Q corresponding to the convex hull of the feasible set S, i.e. Q = conv(S), then we can solve the MILP as if it were an LP by optimizing over Q because all vertices belong to S. We say that an MILP formulation is perfect if P and Q coincide, like in network flow problems with integer coefficients. In the vast amount of cases where that does not happen, the quest illustrated in Schrijver’s book cover begins: we want to start from a good P (in white) and hopefully find an optimal solution by getting closer to Q (in red).

For a good P, we may compare different formulations for their strength. For example, by showing that the linear relaxation of one formulation is a proper subset of another, even if  the variables are different. We can show that by proving that a function maps each solution of the linear relaxation of one formulation to that of another whereas the converse is not true. To strengthen this formulation towards something like Q, at least around the optimal solution, we may add cutting planes. A cutting plane is an inequality that removes a region of the linear relaxation not in S, which is often around an optimal solution of the linear relaxation, in the hope that “wish-me-luck” works next time!

We take for granted that the convex hull is polyhedral, but is it? The following result is adapted from the recent book by Conforti, Cornuéjols, and Zambelli:

The Fundamental Theorem of Integer Programming (Meyer, 1974):
Given rational matrices A, G and a rational vector b, let P := { (x, y) : Ax + Gy ≤ b } and let S := { (x, y) ∈ P : x integral }. Then there exist rational matrices A’, G’ and a rational vector b’ such that conv(S) = { (x, y) : A’ x + G’ y ≤ b’ }.

The fact that the coefficients of the formulation should be rational is often overlooked. In practice, since these problems are solved with finite precision, this becomes irrelevant. However, the convex hull of some MILPs is not polyhedral. The following example is adapted from an exercise in the book above and includes “pi” as a special guest.

If P := { (x, y) : 0 ≤ y ≤ π x } and S := { (x, y) ∈ P : x, y integral },
then conv(S) = { (0, 0) } ∪ { (x, y) : 0 ≤ y < π x }, which is not polyhedral.

pi

The proof for this example is quite simple (in comparison to the example in CCZ’s book). First, no point besides (0, 0) in the line y = π x belongs to S, and by consequence to conv(S). Suppose for contradiction that such a point (x’, y’) exits. Then y’ / x’ is a rational representation of π, a contradiction.  Second, any other point (x, y) for which 0 ≤ y < π x belongs to conv(S). Since x > 0, there is a rational number p / q such that y / x < p / q < π  and thus (x, y) is inside a cone rooted at (0, 0) with rays (1, 0) and (p, q).

Hence, when it comes to integer programming, you should better be rational…

Using the CPLEX solver through COIN-OR’s Open Solver Interface

Today I could not find a single web search result for this:

OsiCpxSolverInterface.hpp: No such file or directory

If you come across this error, you are likely trying to compile code that uses COIN-OR software but that, ultimately, relies on CPLEX to solve optimization problems. In my case, that software was CBC and I reinstalled it (i.e., ./configure; make; make install) with the path to CPLEX libraries and headers on my computer. There is a good explanation for configure options in COIN-OR’s website, but I also needed to add some additional library compiler flags to make it work. So here is my configure command in the end:

./configure –with-cplex-lib=”-L/opt/ibm/ILOG/CPLEX_Studio1263/cplex/lib/x86-64_linux/static_pic/ -lcplex -lpthread -lm” -with-cplex-incdir=”/opt/ibm/ILOG/CPLEX_Studio1263/cplex/include/ilcplex”

If you came here with the same problem, I hope this post saves you some time  🙂

Summer 2018 schools on algorithms, combinatorics, data science, machine learning, optimization, and other relevant #orms topics

If you know of other schools that are not listed here, please let me know. Like in previous posts (Summer 2016, Winter 2017, Summer 2017, and Winter 2018), I may add schools with past deadlines as reference for readers looking for schools in the next years.

NATCOR Heuristics & Approximation Algorithms
April 9-13     (deadline not posted)
Nottingham, England

International Spring School on High Performance Computing
April 23-27     (deadline: February 12)
San Sebastián, Spain
* Included on January 29

Optimal Transport: Numerical Methods and Applications
May 7-11     (deadline: March 10)
Como, Italy

International Spring School on Integrated Operational Problems
May 14-16     (deadline: March 31)
Troyes, France

Complex Networks: Theory, Methods, and Applications
May 14-18     (deadline: February 18)
Como, Italy
* Included on February 19

Summer School on Mathematics in Imaging Science
May 28 – June 1     (deadline: February 14)
Bologna, Italy

1st International Summer School on Artificial Intelligence and Games
May 28 – June 1     (deadline: January 31 for early registration)
Chania, Greece
* Included on January 29

VeRoLog PhD School on Vehicle Routing Problems
June 1-2     (deadline: January 31)
Cagliari, Italy

NATCOR Convex Optimization
June 4-8     (deadline not posted)
Edinburgh, Scotland

Association for Constraint Programming (ACP) Summer School 2018
June 4-8     (deadline not posted)
Jackson, WY, USA
* Included on February 19 by suggestion of Serdar Kadioglu

School on Graph Theory
June 11-15     (deadline: May 4 for early registration)
Sète, France
* Included on March 5

8th Lisbon Machine Learning School
June 14-21     (deadline: March 16)
Lisbon, Portugal

Summer Institute in Computational Social Science
June 17-30     (deadline: February 19)
Durham, North Carolina, USA

2018 Gene Golub SIAM Summer School on Inverse Problems: Systematic Integration of Data with Models under Uncertainty
June 17-30     (deadline: February 1)
Breckenridge, Colorado, USA

2nd International Workshop on Bilevel Programming (including mini-courses)
June 18-22     (deadline: April 15 for early registration)
Lille, France

Machine Learning Summer School
June 18-30     (deadline: February 20)
Buenos Aires, Argentina

The Data Incubator Data Science Fellowship
June 18 – August 10     (deadline not posted)
New York / San Francisco Bay Area / Seattle / Boston / Washington DC, USA, or online
* Included on January 29 by suggestion of Heitor H. Arakawa

International Conference on Automated Planning and Scheduling (ICAPS) Summer School
June 24-29     (deadline: March 23)
Delft, The Netherlands

DTU CEE Summer School 2018: Modern Optimization in Energy
June 24-29     (deadline: March 18)
Copenhagen, Denmark
* Included on February 2 by suggestion of Nicola Secomandi

Eötvös Loránd University Summer School in Mathematics: Introduction to Graph Limits
June 25-29     (deadline: April 30 for early registration)
Budapest, Hungary

2018 Summer School on “Operations Research and Machine Learning”
June 25-29     (registrations closed)
Fréjus, France

Summer School on Hyperbolic Polynomials, Sums of Squares and Optimization
June 25-29     (deadline: April 1)
Atlanta, GA, USA
* Included on February 19

15th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR) Master Class
June 26     (deadline not posted)
Delft, The Netherlands
* Included on January 29 by suggestion of Willem-Jan van Hoeve

The Second Annual JuMP-dev Workshop
June 27-29     (deadline not posted)
Bordeaux, France
* Included on February 5

2nd School on Foundations of Programming and Software Systems: Logic and Learning
July 1-6     (deadline: April 15 for early registration)
Oxford, UK
* Included on March 22

EURO PhD School on Sustainable Supply Chains 2018 (preannouncement link)
July 1-7     (deadline not posted)
Wageningen & Amsterdam, The Netherlands

8th PhD School in Discrete Mathematics
July 1-7     (deadline: June 10)
Rogla, Slovenia
* Included on February 28

NATCOR System Dynamics
July 2-4     (deadline not posted)
Coventry, England

Summer School on Algorithms and Lower Bounds 2018
July 6-9     (deadline: April 15)
Prague, Czech Republic
* Included on February 2

ACM Special Interest Group on Genetic and Evolutionary Computation (SIGEVO) Summer School (website under construction)
July 13-19     (deadline not posted)
Kyoto, Japan

Prague School on Discrete Mathematics 2018
July 16-20     (deadline: March 30)
Prague, Czech Republic

Metaheuristics Summer School
July 21-25     (deadline: April 15)
Taormina, Italy

2nd International Summer School on Deep Learning 2018
July 23-27     (first deadline: February 14)
Genova, Italy
* Included on January 29

EURO PhD Summer School on MCDA/M (Multiple Criteria Decision Aiding / Making)
July 23 – August 3     (deadline: January 31)
Chania, Greece

8th Summer School on Imprecise Probabilities: Theory and Applications
July 24-28     (deadline: March 31)
Oviedo, Spain

Fundamentals of Data Analysis TRIPODS Madison Summer School 2018
July 24-28     (deadline not posted)
Madison, WI, USA
* Included on March 10

Deep Learning and Reinforcement Learning Summer School 2018
July 25 – August 3     (deadline not posted)
Toronto, ON, Canada
* Included on February 19

Argonne Training Program on Extreme-Scale Computing
July 29 – August 10     (deadline: February 28)
St. Charles, IL, United States

4th Algorithmic and Enumerative Combinatorics Summer School 2018
July 30 – August 3     (deadline: June 15)
Hagenberg, Austria

The Cornell, Maryland, Max Planck Pre-doctoral Research School 2018: “Emerging Trends in Computer Science”
August 7-12     (deadline: February 7)
Saarbrücken, Germany

Uncertainty Quantification Summer School
August 8-10     (deadline not posted)
Los Angeles, CA, USA
* Included on May 15

DIMACS/TRIPODS/MOPTA Summer School
August 10-12     (registration closed)
Bethlehem, PA, USA
* Included on May 15

ALOP Summer School on Mixed-Integer Nonlinear Programming
August 13-16     (deadline: May 30 for travel support application)
Trier, Germany
* Included on May 15

Hausdorff School on Combinatorial Optimization
August 20-24     (deadline: April 30)
Bonn, Germany

Network Modeling for Epidemics
August 20-24     (deadline: May 1)
Seattle, WA, USA
* Included on March 12 by suggestion of Emily Tucker

SYNERGY Summer School on Efficient Multi-Objective Optimisation
August 27-31     (deadline: May 31 for early registration)
Ljubljana, Slovenia

Summer School on Statistical Relational Artificial Intelligence
August 27-31     (deadline not posted)
Ferrara, Italy
* Included on April 13

Data Science Summer School
August 28 – September 1     (deadline: April 20)
Paris, France

CPSE Summer School 2018: Optimisation Under Uncertainty
September 3-7     (deadline: July 31 for early registration)
London, England
* Included on May 18

NATCOR Forecasting & Predictive Analytics
September 24-26     (deadline not posted)
Lancaster, England

How can INFORMS help with your educational needs?

(Originally posted in the INFORMS 2017 blog).

Jill Wilson, the VP for Education, lead the first meeting of the newly created Education Strategy Committe this morning. The goal of this committe is to oversee the activities of the other education committes and think strategically about how our efforts are supporting INFORMS goals.

Do you have any ideas about information or resources that INFORMS could help develop or centralize? 

Do you have suggestions for initiatives that INFORMS could support in order to promote better educational practices in Operations Research, Management Science, and Advanced Analytics?

Is there anything that we currently do, but that could be done better somehow?

I am serving as the student member of the committe and I am looking forward to know what other students think on the topic. As TAs, first-time instructors, and potentially future faculty, our input is crucial for better educating the next generation of analytics professionals.

Teaching Colloquium: The Brave 16

(Originally posted in the INFORMS 2017 blog).

In the words of one of the combined colloquia organizers, I was one of the “brave 16” yesterday. The teaching colloquium is often the smallest in attendance numbers, but also the only one that you can attend more than once. If you enjoyed attending other colloquia in the past, and deep inside you know that you have fun teaching, consider joining us next year!

You can find my longer post about what happens at the teaching colloquium in the 2016’s blog.

Winter 2018 schools on big data, data science, discrete math, optimization, and other relevant #orms topics

If you know of other schools that are not listed here, please reach out to me. Like in previous posts (Summer 2016, Winter 2017, and Summer 2017), I may add schools with past deadlines as reference for readers looking for schools in the next years.

SESO 2017 Winter School “Data, Uncertainty and Optimization”
November 28-30     (deadline: October 20)
Luminy, France

Recent Advances ​in Parameterized Complexity
December 3-7     (deadline: October 15)
Tel Aviv, Israel
* Included on October 11

13th Summer School on Discrete Math
January 8-12     (deadline: October 27)
Valparaiso, Chile

Winter School on Optimization and Operations Research: Data Science and Optimization
January 14-19     (deadline: December 16 for early registration)
Zinal, Switzerland

Data61 6th International Optimisation Summer School
January 14-19     (no deadline: first come, first served registration)
Kioloa, Australia

7th Winter School on Network Optimization
January 15-19     (deadline: November 30 for early registration)
Estoril, Portugal

4th International Winter School on Big Data
January 22-26     (deadline: October 19)
Timişoara, Romania

International Research School on Graph Limits
January 22-26     (deadline not posted)
Lyon, France
* Included on November 27

2018 School on Column Generation
February 26 – March 2     (deadline: December 15)
Paris, France
* Included on October 17

2018 Operations Research Summer School for Young Latin American Schoolars (ELAVIO) March 5-9     (deadline not posted)
Marbella Resort, Chile

2018 EURO Winter Institute on Lot Sizing and Related Topics
March 5-16     (deadline: October 31)
Frankfurt an der Oder, Germany

Intensive Research Program in Discrete, Combinatorial and Computational Geometry
April 16 – June 8     (deadline: February 28 for early registration)
Barcelona, Spain

ISCO 2018 Spring School “Advanced MIP Formulations and Computations”
April 9-10     (deadline: January 10)
Marrakesh, Morocco
* Included on November 1

Big M: good in practice, bad in theory, and ugly numerically!

If you have seen or modeled enough optimization problems, you probably came across or felt the need for some big Ms: very large coefficients used as a proxy for infinity. Most often, a big M is used along with a binary variable to turn constraints on or off.

In scheduling, for example, you may use a binary variable y to decide if a job i ends before another job j (ei ≤ sj) when y=1 or vice-versa (ej ≤ si) when y=0. We use M to make the right-hand side of the inactive constraint so large that it becomes irrelevant:

ei ≤ sj + M (1-y)
ej ≤ si + M y

You may like it or not, but no one can be indifferent to big Ms. In fact, many regular attendees and some speakers of the upcoming 2017 MIP workshop have written about it:

Now…
How bad are the bounds of a linear relaxation with big M constraints?

The. Worst.

You can think of a mixed-integer linear program as a disjunctive program: the union of all linear programs corresponding to fixing the integer variables to every possible value. Ideally, you want the linear relaxation of mixed-integer linear program to be as close as possible to the convex hull of such a union of polyhedra. However, disjunctions represented via big M constraints are as good as nothing for the linear relaxation:

BigM

We can see that with a numerical example describing the figure above:

x + y ≤ 1       or       x + y ≥ 5
0 ≤ x ≤ 3
0 ≤ y ≤ 3

We can formulate the disjunction as

x + y ≤ 1 + M z
x + y ≥ 5 – M (1-z)
z ∈ {0, 1}

In this case, M=5 is the smallest valid value for the domains of x and y. However, here is what happens if we project out the binary variable z by Fourier-Motzkin elimination:

(x+y-1)/5 ≤ z
(x+y)/5 ≥ z


(x+y)/5 ≥ (x+y-1)/5

The big M constraints vanish in the projection and we are left with the bounds of x and y.

Now…
Is there a way around it?

Yes! And no…

In theory, you can describe the convex hull by lifting the formulation to a much larger space, where we explicitly combine points from different polyhedra. However, the size of the formulation quickly explodes: if you could represent your terms by switching through n pairs of big M constraints, this tighter relaxation will be 2n times larger.

Update: After this post was published, Hassan Hijazi pointed out to his recent work on representing the convex hull in the space of the original variables.