How problematic are your Big M constraints? an experiment [primal]

This post investigates whether it is still relevant to be careful about the coefficients used in so-called Big M constraints when formulating mixed-integer programming (MIP) models. I make some experiments with two-echelon supply chain design models to show that using too large values often cause the models to be harder to solve. The impact is much greater […]

A relevant #orms resolution for 2017: Update your solvers!

Making resolutions during the New Year has become something of a tradition. Some are followed, many are not. Here is one resolution I took years ago that has been pretty relevant. I would encourage you to use it as well : Update your solvers whenever a new version is released. Like, every time. It’s worth […]

The recommendation game [primal]

People who teach or supervise students have a tremendous influence on what solvers get adopted by the operations research / industrial engineering community. Once they finish their studies, many students will continue to use the tools they have learned in school, for many reasons. First, it is simply the most efficient strategy to adopt. Also, […]

Facility location : not so difficult (with the proper tools)

In a previous post, I generated a few capacitated facility location instances (CFLP) and I ran these through MIP solvers. The instances were solved pretty quickly overall. In a comment, professor Matteo Fischetti suggested I compare my results with some instances from the literature, which I did. Overall, the results are quite fast; CPLEX takes only 21 […]

Seeds and parallel MIP solvers, extended edition

In a previous post, I showed that changing the random seed on a given problem yielded varies solution times by between 20% to 40% on average, depending on the solver and the setting. I decided to push that experiment a little further and sample the distribution of run times based on the variation in random seeds. […]

Seeds and Parallel MIP solvers, part I

Over recent years, mixed-integer programming (MIP) solver developers worked really hard to provide parallel codes that are both fast and quite stable. A few years ago, using a parallel code resulted in huge variations in run times: successive runs of the same model on the same machine could result in drastically different run times. This behavior […]

LP file format: uses and intricacies

LP is one of the most popular formats for explicit description of an optimization model (the other contender being MPS). It uses an algebraic format where you enter the problem’s objective function and constraints line by line. For the last few years I’ve been using that format quite regularly, and I’d say I both hate […]

Open question: tuning for hard instances

This is a rather short post on an open question, one I’ve been thinking about for some time. Automated tuning tools for MIP solvers have been around for the last few years. During that time, I have used these tools – and sometimes seen them used – to reduce run times for various types of […]

Solving sets of similar instances, Part I

In an industrial application, one has often to solve similar instances of the same mixed-integer linear programming (MIP) model. Furthermore, from one model to another, a large proportion of the data is similar. Because of the heuristic nature of MIP computation, these very similar instances could behave quite differently when one tries to solve them. […]

Closing the (MIP) Gap – Part II

Day #2 of the MIP 2013 Workshop reminded me that despite the numerous research efforts invested in mixed-integer programming in the last 60 years or so, much remains to be done. A lot of MIP models are still very difficult to solve. In MIP extensions such as nonlinear, multi-objective or multi-level programming, most large-sized problems […]