Integer Programming is Smart

I’ve just read a funny post from Michael Trick about the sexiness of Integer Programming. He made some points about how good IP modeling is not as straightforward as one might think.

I would like to add a few things about modeling and optimality.

The day I felt “cheated” by an IP solver

Some years ago, I was modeling a scheduling problem that aimed to minimize setup costs in a production line. Surprisingly, it was solved way too fast and with a solution of zero cost, what was simply impossible.

Then I found the “cheat”: as I’ve stated that a setup happens only if you change the product for the next day, the optimal solution was to stop producing for one day between consecutive products in the line, since no setup would happen in that case.

It was my fault not to state that the production line should not stop, but such simpler constraints are the first to be forgotten sometimes.

Missing the real model

Conscious or not, most people embed problem domain knowledge in the search algorithm rather than in the model. It is just when you switch to a technique in which modeling plays an important role that you realize how tricky the modeling task can be.

Sometimes, you might discover that the problem you are tackling is full of tacit constraints that will be discovered only when your client dislikes what you delivered.

Modeling for optimality

If feasibility is under doubt, what about optimality? One does not need to use IP to present an optimality bound, but few people design their own algorithms to estimate optimality gaps when not using IP.

Moreover, IP modeling is not meant to be precise in the whole domain but rather in the optimal solutions. If you can model an integer decision variable as real because it is always integer in any optimal solution, you’ve just won the day. The same happens with the constraint set: you do not have to be worried about constraints that are not tight in the optimal solutions.

Feeling the magic of optimal solvers

Being trapped by your own solver teaches you a lot. You became a better modeler and a better interviewer for your next project.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: