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