Linear programming

Notes on Linear Programming and Integer Linear Programming.

Linear programming and integer linear programming

An instance of Linear Programming requires finding a vector x that optimizes a linear objective function subject to linear constraints. For example, given a matrix A\in {\mathbb R}^{n\times m} and vectors b\in {\mathbb R}^ n, c\in {\mathbb R}^ m, find

\[ \min _ x \{ c\cdot x ~ |~ x\in {\mathbb R}_+^ m, ~ Ax \ge b\} . \]

A feasible solution is any vector x satisfying the constraints x\in {\mathbb R}_+^ m and Ax \ge b, and the objective function (or cost) is c\cdot x = \sum _ j c_ j x_ j. Linear programs may take other forms, for example \max \{ c\cdot x ~ |~ x\in {\mathbb R}_+^ m, ~ Ax \le b\} .

Integer Linear Programming adds an additional constraint x\in {\mathbb Z}_+^ m — the variables should be assigned integer values. For example, given (A,b,c) as above, find \min \{ c\cdot x ~ |~ x\in {\mathbb Z}_+^ m, ~ Ax \ge b\} . (The feasible solutions are constrained to have integer values.)

A linear program (or integer linear program) is a packing problem provided it is of the form \max \{ c\cdot x ~ |~ A x \le b, x \ge 0\} where every note in A is non-negative. Likewise, a linear program is a covering problem if it is of the form \min \{ c\cdot x ~ |~ A x \ge b, x \ge 0\} , and A has only non-negative entries.

Linear Programming is efficiently solvable — there are algorithms that, given any linear program, are guaranteed to find optimal solutions and to run in time polynomial in the size of the input. No such algorithms are known for Integer Linear Programming. Integer Linear Programming is NP-hard (constraining variables to take integer values allows small systems of linear constraints to represent computationally intractable combinatorial problems). That is, Integer Linear Programming does not have a polynomial-time algorithm unless P=NP. Integer Linear Programming is still a very useful abstraction for designing approximation algorithms.

Example

The packing problem \max x+y subject to x+2y\le 10, 5x+3y \le 20, and x,y\ge 0 is illustrated in the two-dimensional plane below.

\includegraphics[type=pdf,ext=.pdf,read=.pdf,width=3.75in]{shared/graphics/linear_program}

The feasible region is the white area in the positive quadrant. The dashed vector points in the direction of increasing cost (x+y). The optimal feasible solution is (1\frac{3}{7},4\frac{2}{7}) (marked by “*”), of cost 5\frac{5}{7}. The feasible integer solutions (feasible solutions of the corresponding integer linear program) are marked with black dots. Three of these have maximum cost 5. The solution (2,2) of cost 4 is a 1\frac{1}{4}-approximate solution to the integer linear program and a 1\frac{3}{7}-approximate solution to the linear program.

Additional notes related to linear programming

modeling Set Cover and Multicommodity Flow

Set Cover and Multicommodity flow as (integer) linear programs.
Modeling a problem as a linear program or integer linear program is a basic skill. Here are two examples.

rounding an LP relaxation

A simple example of computing an approximate solution by rounding the solution to a linear-program relaxation.

The basic paradigm:

  1. Model your problem as an integer linear program.

  2. Solve its linear program relaxation.

  3. Somehow round the solution x^* of the relaxed problem to get a solution \tilde x of the original problem.

The rounding step is typically most easily done with a so-called randomized rounding scheme.

Rounding a relaxation is one of two standard ways to use linear-programming relaxations to design approximation algorithms. (The other way is the primal-dual method.)

MathJax is loading, equations are not yet displayed...