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:

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:


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.

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.

Posted in Uncategorized | Leave a comment

Summer 2017 schools on algorithms, combinatorics, learning, optimization, and other relevant #orms topics

While some summer schools have not been officially announced yet, many are very close to their deadlines already. Repeating what I did for Summer 2016 and Winter 2017, I will keep this post as an updated list of schools and workshops for the upcoming break. Suggestions are always welcome. I am also interested in recurrent schools with past deadlines since they may be relevant for those reading this post in the future.

Workshop-School on Agents, Environments, and Applications (WESAAC) 2017
May 4-6     (deadline was February 9)
Sao Paulo, Brazil

International School on Mathematics “Guido Stampacchia”: Graph Theory, Algorithms and Applications 4th Edition
May 5-13     (deadline: February 28)
Erice, Italy

Optimization Days 2017
May 8-10     (early registration deadline: April 3)
Montréal, Canada
* Included on March 17 by suggestion of Leandro C. Coelho

1st Canadian Healthcare Optimization Workshop
May 10-11     (early registration deadline: April 3)
Montréal, Canada
* Included on February 21 by suggestion of L.-M. Rousseau

Recent Advances in Algorithms International Computer Science Student School
May 22-26     (deadline was February 10)
St. Petersburg, Russia

Athens Summer School: Techniques in Random Discrete Structures
May 22-27     (deadline not posted)
Athens, Greece
* Included on March 17

BGSMath Monthly Program Random Discrete Structures and Beyond
May 22 – June 16     (early registration deadline: May 15)
Barcelona, Spain
* Included on March 17

Eötvös Loránd University Summer School in Mathematics: Higher mathematics through problem solving
June 6-10     (deadline: May 31)
Budapest, Hungary

ATOM 2017: Multiobjective Optimization Summer School
June 12-16     (early registration deadline: April 30)
Villeneuve d’Ascq, France
* Included on February 20 by suggestion of Sarah Fores

Summer Institute in Computational Social Science
June 18 – July 1     (deadline: February 24)
Princeton, United States

The Machine Learning Summer School
June 19-30     (deadline was February 10)
Tübingen, Germany

Integer Programming and Combinatorial Optimization (IPCO) 2017 Summer School
June 24-25     (deadline not posted)
Waterloo, Canada

The First Israeli Modelling Week
July 2-6     (deadline not posted)
Nahariya, Israel
* Included on March 17

Summer School on Optimization, Big Data and Applications (OBA)
July 2-8     (deadline: March 15)
Veroli, Italy
* Included on February 20 by suggestion of Sarah Fores

ACM Special Interest Group on Genetic and Evolutionary Computation (SIGEVO) Summer School
July 14, 20-21     (deadline not posted)
Berlin, Germany

Swedish Summer School in Computer Science 2017: Boolean Circuit Complexity; Algorithms and Lower Bounds
July 16-22     (deadline not posted)
Stockholm, Sweden

International Summer School on Deep Learning
July 17-21    (deadline: February 24)
Bilbao, Spain

Healthcare Operations Research Summer School
July 21-25     (deadline: March 31)
Enschede, The Netherlands
* Included on February 20 by suggestion of Sarah Fores

7th PhD Summer School in Discrete Mathematics
July 23-29     (deadline: April 30)
Rogla, Slovenia

Argonne Training Program on Extreme-Scale Computing
July 30 – August 11     (deadline: March 10)
St. Charles, IL, United States

Eight Montreal Industrial Problem Solving Workshop
August 7-10     (deadline not posted)
Montreal, Canada

The Jyväskylä Summer Schools (several courses, including Data-driven optimization via search heuristics and Online Social Media Analytics)
August 7-18     (deadline: April 30)
Jyväskylä, Finland
* Included on February 20 by suggestion of Sarah Fores

Graph Limits, Groups and Stochastic Processes Summer School
August 28 – September 2     (deadline: March 18)
Budapest, Hungary

Autumn School: Optimization in Machine Learning and Data Science
August 28-31     (deadline not posted)
Trier, Germany
* Included on February 20 by suggestion of Sarah Fores

ALGO 2017 Parameterized Complexity Summer School
September (dates not posted yet)
Vienna, Austria

130th European Study Group with Industry
September 4-8     (deadline not posted)
Coventry, United Kingdom

Association for Constraint Programming (ACP) Summer School: Hybridization of Constraint Programming and Operational Research
September 18-22     (deadline not posted)
Porquerolles, France
* Included on February 21 by suggestion of L.-M. Rousseau

Posted in Uncategorized | 1 Comment

The State of CMU INFORMS in 2016

(Originally posted at the CMU INFORMS website).

A lot of great things happened in 2016 at CMU INFORMS. Since we already compiled all of that for the annual report to INFORMS, we are sharing it publicly in the hope that other chapters find it useful and share back with us, just like we did with 2015 activities.


We launched the seminar series Industry Leaders in Analytics in partnership with the MBA Data Analytics club, which sponsored receptions after the talks. We first brought Steve Sashihara through the INFORMS Speakers Program and later Sebastian Ceria.

Princeton Consultants CEO Steve Sashihara came in April to present “The Executive’s Guide to Optimization”.


Axioma CEO and CMU PhD alumnus Sebastian Ceria came in September to present “What’s in a Name? In the Case of Smart Beta, It’s Hard to Tell”.


Both talks were preceded by an informal gathering with PhD students and followed by a happy hour with all attendees.

We also launched the academic seminar series Research & Analytics @ CMU with the goal of presenting research done at CMU in an accessible language to undergraduate students, thanks to input from our undergraduate officer Michael Rosenberg. Our first speaker was Prof. Mor Harchol-Balter (School of Computer Science) in September.


We also invited Prof. John Birge (The University of Chicago) for an academic seminar through the INFORMS Speakers Program in November. Prof. Birge met with PhD students for dinner on the night before and to talk about research after his seminar.


The publication of our 2015 review ignited an amazing exchange of ideas among INFORMS chapters. Similar reviews were later published by the chapters from University of Massachussets-Amherst and University of Michigan. We also were approached by officers of other chapters at the Annual Meeting that found helpful advice in our posts. These exchanges also made us realized how much we could benefit from the Speakers Program.

While many conversations happened in the halls, INFORMS helped us connect too. Here is a picture of the student chapter officers meeting after the chapters and fora breakfast:


These breakfasts and meetings happen every year on Tuesday mornings. If you are an officer attending the next Annual Meeting in Houston, show up and take a seat!

At that meeting in Nashville, our chapter was awarded the Summa Cum Laude Award for our activities in 2015, the highest distinction granted by INFORMS to student chapters.


We also had a short piece on our student-led seminars in the most recent issue of ORMS Tomorrow. Other chapters have also implemented this program recently: University of Michigan launched theirs in September 2016 and University of Illinois at Urbana-Champaign in January 2017.


We extended our most successful initiatives from 2015. We held another 2 joint happy hours with the INFORMS chapter at the University of Pittsburgh. Interestingly, the attendance at these happy hours is growing exponentially: from about 10 people in Fall 2015, we got 20 in Spring 2016 and 40 in Fall 2016. The latest one had a better venue and improved organization thanks to our new officer Neda Mirzaeian.

It is not clear at this point if the exponential trend will persist, but we can always hope!

We also increased the number of student-led discussion dinners in 15%. That was only possible thanks to the continuous effort of Siddharth Singh. Here are the list of talks:

02/01 – Yang Jiao: Student question posets
02/08 – Thiago Serra: Sound decision diagrams: a .zip file of near-optimal solutions
02/15 – Dabeen Lee: On some polytopes contained in the 0,1 hypercube that have a small Chvatal rank
02/22 – Nam Ho-Nguyen: Second-order Conic Formulation of the Trust Region Subproblem
02/29 – Stelios Despotakis: Attribution models in marketing
03/21 – Tarek Elgindy: Topics in AC optimal power flow
04/04 – Gerdus Benade: Formulating a branching dual
04/11 – Aleksandr Kazachkov: Small representations for large kidney exchange graphs
04/25 – Thiago Serra: Reformulating the Disjunctive Cut Generating Linear Program
05/09 – Siddharth Singh: Net Metering Policies for PV solar electricity
05/16 – Dabeen Lee: Optimizing over the Chvatal Closure of a 0,1 Polytope is NP-Hard
05/23 – Bo Yang, Franco Berbeglia, and Mehmet Aydemir: Summer paper proposals
08/15 – Thiago Serra and Siddharth Singh: MOPTA practice talks
09/14 – Arash Hadadan, Gerdus Benade, and Nam HO-Nguyen: OR summer paper practice talks 1
09/19 – Bo Yang, Franco Berbeglia, and Mehmet Berat Aydemir: OM summer paper practice talks
09/28 – Amin Hosseini, Dabeen Lee, and Ryo Kimura: OR summer paper practice talks 2
10/10 – Thiago Serra and Siddharth Singh: Summer internship experiences 1
10/19 – Jeremy Karp, Ryo Kimura, and Yang Jiao: Summer internship experiences 2
10/31 – Siddharth Singh: That’s not fair – Tariff structures for electricity markets with rooftop solar
11/07 – Abhinav Maurya, Siddarth Singh, and Thiago Serra: INFORMS practice talks 1
11/09 – Gerdus Benade, Amin Hosseini, and Leela Nageswaran: INFORMS practice talks 2
11/30 – Siddarth Singh, and Thiago Serra: INFORMS Combined Colloquia
12/05 – Ahmad Abdi (U. Waterloo): Ideal clutters that do not pack

We have also increased the number of review sessions in anticipation of important talks:

01/21 – Laci Babai (The University of Chicago)
01/29 – Nina Balcan (CMU)
02/05 – Javier Pena (CMU)
02/26 – Yanjun Li (Purdue University)
03/04 – Andrea Lodi (Polytechnique Montreal)
04/08 – Rakesh Vohra (University of Pennsylvania)
12/09 – John Birge (The University of Chicago)


We found good sources of funding. We successfully pitched the doctoral program for $1,500 and obtained another $1,000 from student government funding.

Our MBA officers have contributed to make the chapter more professional in a variety of ways. Former secretary David Sandora led the reformulation of our bylaws and helped us develop a mission, vision, goals, and more tangible roles for the officer positions prior to the 2016 elections. His slides are available here. Chris Boccio is serving his second term as treasurer and first as secretary. He has working on proving the maturity of our organization before CMU to obtain more funding from the student government in the next academic years. Since April, Lauren Wilson has joined the team with her marketing expertise and is helping to reshape how the chapter is seen at CMU and outside.


Bidding for an Omega Rho chapter at CMU: We are supporting the application of a group of undergraduate students from a variety of departments at CMU for a Carnegie Mellon chapter of the Omega Rho International Honor Society. Fingers crossed for their success!


Keeping Moore’s Law going with happy hours: We cannot keep doubling happy hour attendance for long, but for sure we can double the number of happy hours. We are considering another joint happy hour with the Chemical Engineering department.

MDD #50: We are likely to reach our 50th student-led discussion at some point in Spring 2017. We are still discussing how to make it a special happening to celebrate the consolidation of this great initiative started by Tarek Elgindy in 2015.

Big Data Challenge: CMU INFORMS was invited by the Texas A&M chapter to participate in their traditional big data challenge. Details to follow.


We are grateful for the support of faculty and staff from the Tepper School of Business: our faculty advisor Fatma Kilinc-Karzan; the Associate Director for the PhD Program Lawrence Rapp; the heads of the PhD Program Alan Scheller-Wolf, Gerard Cornuejols, Nicola Secomandi; the Associate Dean Michael Trick; and many others in the OR and OM programs. We are also thankful to all our speakers, volunteers, officers (listed on the website), members of the MBA clubs that partnered with us, faculty of other schools at CMU. And thank you INFORMS for all the help, recognition, and support since 2014!

Posted in Uncategorized | Tagged , | Leave a comment

11 types of tweets for #ics2017

With the 2017 INFORMS Computing Society Conference in Austin around the corner, I was looking for useful way to make a binary joke and decided to write about tweeting.

For a long time I used Twitter as I would use Linkedin (that is, if Linkedin worked): for networking and letting people know about something going on where I was. This type of tweet, which I now call “Look what you are missing”, is quite useful.

I still use Twitter in that way, particularly when I am busy keeping session time (like above) or trying to understand something that is new to me. However, I started paying attention to other people’s tweets and decided to use it in a more productive way for me and others: taking notes of what seem to be the takeaway message or good to know.


But there is another – more entertaining – way of using Twitter in conferences…

I still have to figure how to tweet while giving a talk. Talk would entail 100 types of tweets!

Posted in Uncategorized | 1 Comment

Realize what you have lost; come back the next year!

(Originally posted in the 2016 INFORMS blog).

INFORMS meetings: you are not doing it right if you don’t realize that there was something cool that you missed by the end of the conference. Perhaps that does not hold for fellows, but for sure it does for those with, say, less than a dozen meetings.

This is my list of “missed things” so far:

  • Charlotte 2011: found out about the meeting and followed it through the conference blog; decided that I would attend the next year and be a blogger.
  • Phoenix 2012: met great people from academia; decided to leave industry to pursue a PhD, joined CMU the next year, and did not attend Minneapolis 2013 to focus on my courses instead.
  • San Francisco 2014: heard about the great time that some people had at the doctoral students colloquium; then applied and attended the next year (and also attended the teaching effectiveness colloquium this year).
  • Philadelphia 2015: discovered about the poster competition; submitted my poster this year and had a great time presenting it.

In fact, the poster competition was much more intense than any other talk that I gave at INFORMS before: by the final round all judges came to talk to each poster presenter, many of which with a good understanding of the general area that I work on (cutting planes for integer programming). I had many more questions and met a lot more people than I would if I had presented the same thing on a regular talk, given how many parallel sessions there are.

Have you found your missed thing yet? If not, ask around what people liked the most so far. It won’t take long to find something you wished you had done too!

Posted in Uncategorized | Leave a comment

INFORMS on day -1: Teaching Effectiveness Colloquium

(Originally posted in the 2016 INFORMS blog).

A lot happens before the conference officially starts. Among those things, there is the combined colloquia, which are currently 3: for doctoral students, for young faculty, and on teaching effectiveness. I had such a great time last year at the doctoral students colloquium that I came back for the teaching effectiveness one this time.

Attendees of all colloquia are invited for a dinner on Friday, day -2. I had a great time talking to a cohort of PhD students and young faculty from US, Italy, Israel, and Hong Kong:

This morning, Jeffrey Camm was the first TEC speaker. He made interesting considerations about teaching students to explain why a solution is optimal to their clients. He also made the case for sub-optimal solutions, which sometimes are preferable because their worse value is more than compensated if they disrupt less how things are currently done.


Fredrik Odegaard talked about his experience using and creating analytics-related cases. He mentioned good resources for cases and explained how we works with them through his 80-minute lectures.



Matt Bailey was next. He pitched for ambiguity and unstructured problem solving, which is what will truly prepare students for real situations. That requires discipline not to delve in the data without a goal in mind. He worked out the probability for an, apparently, unusual case: a waitress at a small town in Ohio was given her stolen ID by an underage customer trying to buy alcohol.



Prakash Mirchandani discussed active learning and counterposed case-based lectures with games, which he prefers. He discussed when and for how to long to use different types of games along a course.

The next speaker was Amy Cohn, whom I have been following on Twitter for a while and seen her enthusiasm when talking about the Center for Healthcare Engineering and Patient Safety (CHEPS) at the University of Michigan. Her enthusiasm seems even bigger in person! She gave some interesting examples of engaging students by letting them choose project topics that they care about, and by replacing those tons of blending problems from linear programming textbooks with the real-world problems that she is currently solving.


Finally, James Cochran gave a whole lecture on engaging bits that can make students interested in the class. The most memorable part was when he explained how to use legos to explain linear programming and how to smash them when you want to explain shadow prices. He also run his version of “Who wants to be a millionaire”!


Kudos to Mihai Banciu for curating such an inspiring crowd of lecturers. The best way to teach is by showing, which all of them did!

Posted in Uncategorized | Leave a comment

Winter 2017 schools on algorithms, optimization, scheduling, and other relevant #orms topics

There is not so much going on this Winter as in the past Summer, but there is still some cool stuff coming up. From doing a similar list of Summer 2016 schools and getting some feedback on things that I have missed, I hope that this list keeps growing as more people read this post and reach out to me. Like last time, I may also post schools with past deadlines as reference for future readers looking for schools in 2017 onwards.

SESO 2016 Winter School on Numerical Methods for Multistage Stochastic Optimization
November 2-7     (deadline: October 23)
Champs-sur-Marne, France
* Included on October 5

Brazilian Summer School in Machine Learning
December 8-9     (deadline: December 2)
Sao Paulo, Brazil
* Included on November 29

3rd Summer School on Discrete Math
January 3-6     (deadline: October 19 for international applicants)
Valparaiso, Chile

Winter School on Optimization and Operations Research: Big Data and Optimization
January 15-20     (deadline: December 15 for early registration)
Zinal, Switzerland
* Included on October 5 by suggestion of Shabbir Ahmed

Winter School in Stochastic programming with applications in energy, logistics and finance
January 15-21     (no deadline: first come, first served registration)
Passo del Tonale, Italy
* Included on October 20

6th Winter School on Network Optimization (netopt2017)
January 16-20     (deadline: October 31)
Estoril, Portugal

3rd International Winter School on Big Data
February 13-17     (deadline: October 21)
Bari, Italy
* Included on October 5

Recent trends in the study of expanders and high dimensional expanders
February 12-16     (deadline not posted)
Rehovot, Israel
* Included on January 2

2017 EURO Winter Institute on “Methods and Models in Transportation Problems”
February 14-23     (deadline was October 15)
Bressanone, Italy
* Included on October 25

Operations Research Summer School for Young Latin American Schoolars (ELAVIO)
February 24  – March 4     (deadline not posted)
Buenos Aires and Miramar, Argentina

Posted in Uncategorized | Leave a comment