Algorithms / Integer Programs
Least You Need to Know: Integer Programs, Binary Variables, and LP Relaxation Bounds
Integer-programming questions are mostly about modeling discrete choices cleanly. Binary variables encode include/exclude decisions, linear constraints express feasibility, and LP relaxations often provide lower or upper bounds that help with approximation or branch-and-bound reasoning.
The least you need to know
- A 0-1 variable can encode a yes/no decision such as selecting an item, edge, or set.
- Constraints translate the combinatorial feasibility rules into linear inequalities.
- The objective can minimize cost or maximize value over the chosen variables.
- Dropping integrality gives an LP relaxation that is easier to solve.
- The relaxation value is a bound on the integer optimum, and the gap between them is the integrality gap.
Key notation
x_i in {0,1}
binary decision variable
LP relaxation
replace integrality constraints by real intervals such as `0 <= x_i <= 1`
integrality gap
worst-case ratio between integer optimum and relaxed optimum
Tiny worked example
- In **Set Cover**, let `x_i = 1` if set `i` is chosen and `0` otherwise.
- For each element `e`, add a constraint that the chosen sets covering `e` have total at least `1`.
- Minimizing the weighted sum of chosen sets gives an integer program.
- Replacing `x_i in {0,1}` by `0 <= x_i <= 1` yields the LP relaxation.
Common mistakes
- Students often write a good objective but forget the constraints that force feasibility.
- An LP relaxation may have fractional solutions that are not valid integer solutions.
- The relaxation bound direction depends on whether the objective is minimization or maximization.
How to recognize this kind of problem
- The prompt asks you to model yes/no choices with equations or inequalities.
- A combinatorial problem is rephrased using decision variables and coverage/capacity constraints.
- The solution method mentions LP relaxation, rounding, or branch and bound.