Integer Programming

Unlike most analytics-based companies, which build descriptive models that create reports that describe the state of affairs within a system, we build prescriptive models using techniques such as Integer Programming that provide the mathematically optimal or best state of affairs that is possible.

Optimality Gap

Integer Programming (IP) provides not only a solution to a given problem but also the optimality gap, which is the difference between the current solution and the best possible solution. Let us imagine that we use the Vehicle Routing Model to find the minimum no. of vehicles necessary for moving goods between a set of origin-destination pairs and the model gives a routing solution with say 10 vehicles. The information on optimality gap could be something like the following:

• The solution with 10 vehicles is mathematically the best and a better solution does not exist.

• The solution with 10 vehicles is the best that the model could find within the current time-limit but the model can mathematically confirm that the best solution will need at least 9 vehicles. This means that we are within 10% of the best solution.

This information can be very useful when we need to make expensive capital allocation decisions.

IP versus ML/AI

Machine Learning /Artificial Learning-based (ML/AI-based) models can provide a quick solution but do not provide any information on how far that solution is from the best solution.

Since Integer Programming-based models provide the gap information, the time taken to solve a given problem will generally be more than that taken by ML/AI-based models.

Integer Programming-based models are useful in the planning phase when solution quality is more important than solution time. ML/AI-based models are useful in the execution phase when quick decisions have to be made in a rapidly changing environment.

For example, an IP-model can be used to find the minimum number of (expensive) trucks needed to move goods between a set of origin-destination pairs over a period of time. An ML/AI model can then be used for making the actual routing decisions on a given day based on real-time traffic conditions.