Integer Programming

An integer program is a linear program where some or all decision variables are restricted to integer values.

• Pure integer program
  All decision variables are integers.
• Mixed integer program
  Some decision variables are integers, others continuous.
• Binary integer program
  Decision variables restricted to $0$ or $1$.

Linear Programming Relaxation

The linear programming relaxation drops the integer restriction and solves as an ordinary linear program.

• The relaxation optimum bounds the integer optimum. Upper bound for maximization, lower bound for minimization.
• An integer-valued relaxation optimum solves the integer program directly.

Cutting Plane Algorithm

Adds constraints that cut off fractional solutions without removing integer feasible points.

Branch and Bound Algorithm

Splits the feasible region on a fractional variable, solving relaxations of each subproblem to find the integer optimum.

• Incumbent
  The best integer feasible solution found so far. Updated whenever a subproblem’s relaxation is integer valued and better.
• Optimality
  The incumbent is optimal once no unpruned subproblem remains.