Linear and Integer Programming
We specialize in developing Linear and integer programming-based techniques that can help us find the best or optimal solution from a large number of potential solutions.
Consider the following situation. A person needs to tour 5 cities (A, B, C, D and E) and wants to know the sequence in which he should visit them so that the length of the entire tour is as small as possible. If we want to find the shortest tour, then we will have to calculate the lengths of all possible arrangements of cities (such as BCAED, ABCDE, etc.) and then pick the smallest. This can be done easily since the total number of arrangements here is only 120 or 5! or 5x4x3x2x1. However, if we have a set of 100 or 1000 cities, the number of arrangements will be too large to be considered individually. For example, 100 factorial is 10 raised to a power of 157, which is a number larger than the number of atoms in the universe, which is of the order of 10 raised to a power of 100.
Combinatorial Optimization deals with solving problems like the one above, which is known as the Traveling Salesman Problem. These problems arise in many different contexts and solving them optimally can provide real financial benefits. Linear and Integer Programming gives us techniques that allow us to get the optimal solution without evaluating all the possible solutions. If you wish to know more about how these techniques, you can look at the toy problems below.
The advantage of these techniques is that they not only provide a solution but also a guarantee on how close it is to the best solution. Therefore, these techniques are useful for planning problems in which getting an optimal solution is more important than the solution time. For problems requiring a real-time response, machine learning-based models are more suitable, which provide a quick solution but do not provide any information on how far that solution is from the optimal solution.
Sample Linear Program
Consider the following situation. A manufacturing company makes two products P1 and P2 using machines M1 and M2. One unit of P1 needs 4 hours on M1 and 2 hours on M2 whereas one unit of P2 needs 3 hours on M1 and 1 hour on M2.
Further, a unit of P1 yields a revenue of $7 and a unit of P2 yields a revenue of $5. Given that the total available time on machines M1 and M2 is 240 hours and 100 hours, how many products of each type should the company make so as to maximize its total revenue.
Click on the link below to see how one could model this problem as a linear program.
Sample Integer Program
A media company has five spots (S1, S2, S3, S4 and S5) that it wants to assign to three breaks (B1, B2 and B3). The company knows the estimated impressions for each spot and break combination.
How can the company find and assign a subset of spots to breaks so as to maximize the total number of impressions while ensuring that (a) each break has no more than one spot, and (b) at least one spot must be picked from the group {S1, S2}.
Click on the link below to see how one could model this problem as an integer program.