Formulating ilp problems
Formulating ILP Problems
Formulating ILP problems means translating indivisible and yes/no decisions into linear constraints with integer or binary variables.
Step 1: Identify Variable Types
Classify each decision:
- continuous: fractional values allowed
- integer: whole numbers required
- binary: yes/no decision
This is the first difference between LP and ILP modeling.
Step 2: Write the Linear Objective
The objective is still linear:
\[\max \sum_j p_jx_j\]or:
\[\min \sum_j c_jx_j.\]Do not multiply decision variables together. Products such as $x_jy_j$ are not linear.
Step 3: Add Resource Constraints
Resource constraints usually keep the same LP form:
\[\sum_j a_{ij}x_j\le b_i.\]The difference is that some $x_j$ may now be integer or binary.
Step 4: Add Logical Constraints
Common logical constraints include:
At most one choice:
\[y_1+y_2+\cdots+y_k\le 1.\]At least one choice:
\[y_1+y_2+\cdots+y_k\ge 1.\]Exactly one choice:
\[y_1+y_2+\cdots+y_k=1.\]Step 5: Link Binary and Continuous Variables
If $x$ can be positive only when $y=1$, use:
\[x\le My,\]where $M$ is a valid upper bound on $x$.
Choose $M$ carefully. It should be large enough to be correct but not unnecessarily huge.
Example: Hiring Researchers
Let:
\[x_1,x_2,x_3=\text{number of researchers of levels }1,2,3.\]Because these are counts:
\[x_1,x_2,x_3\in\mathbb{Z}_+.\]If the goal is to maximize total hires:
\[\max x_1+x_2+x_3.\]Salary budget and legal rules become linear constraints.
Checklist
For every ILP formulation, check:
- which variables must be integer
- which variables are binary
- all constraints are linear
- logical implications are correctly modeled
- bounds are included
- the answer is not obtained by simply rounding an LP solution
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.