# 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 that optimizes a linear objective function subject to linear constraints. For example, given a matrix and vectors , , find

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

A feasible solution is any vector satisfying the constraints and , and the objective function (or cost) is . Linear programs may take other forms, for example

Integer Linear Programming adds an additional constraint — the variables should be assigned integer values. For example, given as above, find (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 where every entry in is non-negative. Likewise, a linear program is a covering problem if it is of the form , and 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 subject to , , and 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 (). The optimal feasible solution is (marked by “*”), of cost . The feasible integer solutions (feasible solutions of the corresponding integer linear program) are marked with black dots. Three of these have maximum cost . The solution of cost is a -approximate solution to the integer linear program and a -approximate solution to the linear program.

# 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.