Home / research areas / LIP
Linear and Integer Programming
Linear programming provides a method to mathematically represent and address optimization problems. We are typically given a set of continuous variables that are associated with costs or profits, and we wish to minimize the total cost or maximize the total profit. The solution must satisfy a set of linear inequalities which model the specific restrictions of each problem.
Consider the following example. A farmer has a truck that can carry up to $24m^3$ of grain. His farm produced $4t$ of grain of type $A$ and $3t$ of type $B$. One tonne of type $A$ occupies $7m^3$ and sells for $\$500$. One tonne of type $B$ occupies $5m^3$ and sells for $\$300$. How much grain of each type should he take in the truck to maximize his profit after a single trip?
This problem can be addressed with linear programming. Let $x$ and $y$ be the amount of grain (in tonnes) that the farmer carries of types $A$ and $B$, respectively. The total profit is $500x + 300y$. The total volume should be at most $24m^3$, so $7x + 5u \le 24$. Both variables must be non-negative and are limited by the total amount of grain produced of each type. This gives the linear program:
The optimal solution for this problem is to load the truck solely with type $A$, yielding $(x, y) = (3.43, 0)$, with profit $\$1714.29$.
Efficient algorithms exist to solve linear programs with thousands of variables and constraints. The best known is perhaps the Simplex method, which was developed by George B. Dantzig in 1947.
Imagine, now, that instead of grain, we wish to transport machine parts. It makes no sense to take fractional amounts of parts, so we must restrict the variables to be integers. Note that it does not suffice to simply round the original solution. In our example, rounding gives $(x, y) = (3, 0)$, with profit $\$1500.00$. However, the optimal solution is $(x, y) = (2, 2)$, with profit $\$1600.00$.
It turns out that integrality constraints make the problem significantly harder and no polynomial time algorithm is known for the general case. The research area that studies methods to solve such problems is known as Integer programming.
Many real-world problems can be addressed with linear/integer programs. In particular, any problem from NP can be formulated as an integer program. As a consequence, this area is of great interest to both academia and industry.
Problems:
- Traveling salesman
- Knapsack
- Independent set
- Vehicle routing
- Production planning
- Facility location
- Cutting and Packing
References:
- M. S. Bazaraa, J. J. Jarvis, and H. D. Sherali. Linear Programming and Network Flows. Wiley, 4nd edition, 2009. Amazon
- G. L. Nemhauser and L. A. Wolsey. Integer and Combinatorial Optimization. John Wiley and Sons, New York, 1999. Amazon
- L. A. Wolsey. Integer programming. John Wiley and Sons, 1998. Amazon