Linear programming and integer linear programming

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

A feasible solution is any vector $x$x satisfying the constraints $x\in {\mathbb R}_+^ m$x\in {\mathbb R}_+^ m and $Ax \ge b$Ax \ge b, and the objective function (or cost) is $c\cdot x = \sum _ j c_ j x_ j$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\} .$ \max \{ c\cdot x ~ |~ x\in {\mathbb R}_+^ m, ~ Ax \le b\} .

Integer Linear Programming adds an additional constraint $x\in {\mathbb Z}_+^ m$x\in {\mathbb Z}_+^ m — the variables should be assigned integer values. For example, given $(A,b,c)$(A,b,c) as above, find $\min \{ c\cdot x ~ |~ x\in {\mathbb Z}_+^ m, ~ Ax \ge b\} .$ \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\}$\max \{ c\cdot x ~ |~ A x \le b, x \ge 0\} where every entry in $A$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\}$\min \{ c\cdot x ~ |~ A x \ge b, x \ge 0\} , and $A$A has only non-negative entries.

Linear Programming is efficiently solvable — there are algorithms that, given any linear program, are guaranteed to find an optimal solution 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$\max x+y subject to $x+2y\le 10$x+2y\le 10, $5x+3y \le 20$5x+3y \le 20, and $x,y\ge 0$x,y\ge 0 is illustrated in the two-dimensional plane below.

The feasible region is the white area in the positive quadrant. The dashed vector points in the direction of increasing cost ($x+y$x+y). The optimal feasible solution is $(1\frac{3}{7},4\frac{2}{7})$(1\frac{3}{7},4\frac{2}{7}) (marked by “*”), of cost $5\frac{5}{7}$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$5. The solution $(2,2)$(2,2) of cost $4$4 is a $1\frac{1}{4}$1\frac{1}{4}-approximate solution to the integer linear program and a $1\frac{3}{7}$1\frac{3}{7}-approximate solution to the linear program.

Additional notes related to linear programming

Wikipedia

• linear programming

• covering and packing