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
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 nonnegative. 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 nonnegative 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 NPhard (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 polynomialtime 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 twodimensional 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). 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.
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 linearprogram relaxation.
The basic paradigm:

Model your problem as an integer linear program.

Solve its linear program relaxation.

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 socalled randomized rounding scheme.
Rounding a relaxation is one of two standard ways to use linearprogramming relaxations to design approximation algorithms. (The other way is the primaldual method.)