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.

Optimizing Public Policies for Urban Planning

Another possible title would be “Marrying an urban planner up to her research problems”.

It all happened when I started hearing my fiancée explaining the problems of Brazilian housing policy and ended up with an interesting model for sustainable housing subsidy that she presented at the Latin American Real Estate Society meeting of 2009.

The problem: Housing policy in Brazil 

The main housing subsidy for low-income families in Brazil is based on a federal program roughly called “My House, My Life”, in which public subsidy consists of an amount of money for each constructed housing unit that varies solely according to the city.

In a place like São Paulo, the unavoidable consequence of such policy is to further sprawl low-income families towards suburban areas.
Most of them already spend much more than two hours per day to go to work.
Moreover, great distances prevent them from going to work on foot or bicycle, what raises public transportation demand and decreases their purchasing power.


São Paulo in 2009: Job offer vs. low-income settlement (source: SEMPLA).

What we did: A model for variable subsidy

We started looking for the main problems of distant placement of such families:

  • Bad life quality due to the time wasted for displacing. 
  • More pollution due to the large displacements. 
  • Public expenditures to support the public transportation system.

    Instead of creating a complex multi-criteria model to tackle that, we just considered that people must be placed at most one hour apart from 50% of the jobs in the city (seems fair, right?) and considered the criteria in which anything is actually done: money!

    After all, how much does it cost to the government if families are so far from their jobs?

    • If the place is too far, one must account the per-family cost on bringing adequate public transportation infrastructure up to there. 
    • Depending on the modal of transportation, there must be public subsidies and also the carbon footprint cost, which were accounted for two people per family to work for one generation (25 years).

      Thus, if you have a 20K subsidy to place a house or apartment anywhere in the city, it would be fair to raise that in places where nothing else must be done. For instance, we realized that extending a subway line costs about 20K per family, that is, government actually spends the double to bring adequate infrastructure, if not more.


      São Paulo’s downtown: A very good infrastructure and many abandoned buildings.

      What’s next?

      To what concern the O.R. community, it is not a challenging problem in terms of algorithms but there is a lot of room to improve modeling.
      Unfortunately, we did not apply our model completely due to the lack of data, but we hope to do that someday.
      However, it is already possible to devise the possibilities of reducing public expenditures, and forthcoming approaches would provide integrated decision models for housing subsidy and infrastructure investments.

      Talking about multidisciplinary: O.R. at the Public Sector

      A multidisciplinary approach might start at your own home, and it may point out interesting challenges that academia might not have been devised so far.
      In Brazil, where public sector decisions are all but technical, there are big opportunities yet to be explored.

      About the paper

      We were glad to have had support from Prof. J.C.S. Gonçalves, which previously was Sabrina’s advisor at FAU-USP and also coauthored this paper.

      S. Harris, T. Serra, J.C.S. Gonçalves: Critical Analysis of Brazilian Housing Policy and Proposal of Subsidy Calculation Model Based on Transportation Sustainability Criteria.
      In: Proceedings of LARES Conference 2009, São Paulo, Brazil.