Flashcards
Answer
Integer Linear Programming
Integer linear programming is linear programming with integrality restrictions on some or all decision variables.
The objective and constraints remain linear, but some variables must take integer values.
Definition
A general integer linear programming problem has the form:
\[\min c^Tx\]subject to:
\[Ax\le b,\] \[x_j\in\mathbb{Z}\]for some variables $j$.
If all variables must be integer, the problem is a pure ILP. If only some variables must be integer, it is a mixed-integer linear program.
Why Integrality Matters
Some quantities cannot be fractional:
- number of vehicles
- number of workers
- yes/no decisions
- selected projects
- opened facilities
- bought units
A solution with $x=3.7$ trucks may be feasible for the LP relaxation but meaningless for the original problem.
Binary Variables
A binary variable is restricted to:
\[y\in\{0,1\}.\]It usually represents a yes/no decision:
\[y=1 \Rightarrow \text{choose/open/use/do it}\] \[y=0 \Rightarrow \text{do not choose/open/use/do it}.\]LP Relaxation
The LP relaxation removes integrality restrictions.
For example:
\[y\in\{0,1\}\]becomes:
\[0\le y\le 1.\]The relaxed problem is easier to solve, but its solution may not be integer.
Important Warning
Solving the LP relaxation and rounding the answer is not generally valid.
Rounding can:
- violate constraints
- produce a worse solution
- miss the true integer optimum
- change the meaning of binary decisions
Map of the Section
- Integer Variables: variables restricted to integer values.
- Binary Variables: $0/1$ variables for decisions.
- Knapsack Problem: a classic ILP model.
- LP Relaxation: continuous approximation of an ILP.
- Formulating ILP Problems: modeling patterns with integer and binary variables.
See Also
Exam checkpoint
For ILP questions, state clearly which variables are integer or binary. Do not use the LP relaxation answer as the integer answer unless it is already integral.