Course
Integer Programming
Decision variables that must take integer or binary values: what integrality does to a linear program, how to express logical conditions such as at-most-one and only-if with binary variables, and what the bound from the linear relaxation establishes. Requires formulation and outcome classification, not the simplex method.
Finishing this course means you have demonstrated the required skills with the level of support this course currently assesses.
- Modules
- 1
- Lessons
- 3
- Skills
- 3
- Starting here
- Assumes 3 prior topics
The route
Module 1: Integer programming
Integrality as one extra line in the program and a different problem underneath. The relaxation is where the central idea and the most common error both live.
- Given a described situation or a stated program, the learner can say which variables require integrality and which do not, classify the program as pure integer, mixed-integer or binary, describe the feasible set integrality produces, and state which results about linear programs cease to apply.
- Given a situation containing yes-or-no decisions and conditions relating them, the learner can define binary variables with stated meanings, write linear constraints expressing selection counts, implications and links between decisions and quantities, choose a defensible bound for a linking constraint, and verify that each constraint forbids what it is meant to forbid.
- Given an integer program, the learner can form its linear relaxation, state the direction of the bound its optimum provides, use the bound to judge how far a candidate integer solution can be from optimal, draw the inferences an infeasible or integral relaxation licenses, and explain why rounding is not a solution method.
What finishing means
Finishing this course means you have demonstrated the required skills with the level of support this course currently assesses.
3 required skills. If you reach a lesson without the background it assumes, you are pointed at the prerequisite first, and returned here afterwards.
How progress is measured
Progress is inferred from evidence you produce, not from pages you have opened. Each required skill moves through states as evidence accumulates: met, practicing with help, performed unassisted, then performed again after a delay.
This course counts a skill as finished atguided. Where the system cannot admit evidence for a stronger claim — for instance when the only available scoring is your own judgment of your written answer — the skill stays at the state the evidence supports, and the reason is shown rather than hidden.