Unit 02 β Integer Linear Programming
When fractional answers are meaningless. Pure, mixed and binary ILP, the logical constraints that make binary models powerful, and the seven formulation patterns the paper draws from.
One 5-mark question, in both papers, with an identical shape: a project-selection table plus one logical restriction ("C and E cannot be undertaken together" / "B and D cannot be executed together"), and the instruction "Formulate an ILP model". You are never asked to solve it. Final Q4B QP p. 4, Re-Exam Q4A QP p. 3. Both solved β
1. What Is Integer Linear Programming? Core syllabus concept
1Understand the Concept
Ordinary LP lets decision variables take any real value that satisfies the constraints. In many real situations a fractional answer is nonsense Deck p. 2:
- You cannot make 2.5 cars.
- A project is either selected (1) or not selected (0) β there is no 0.4 of a project.
- You cannot assign 0.3 of a worker to a job.
In those cases you add an integrality restriction and the model becomes an Integer Linear Programming problem. Everything else β objective function, constraints, non-negativity β is written exactly as in Unit 1. ILP is LP plus one extra line.
2The three types β know which one you are writing
| Type | Restriction | Typical example | Last line of your answer |
|---|---|---|---|
| Pure ILP | All decision variables must be integers. | Number of buses, number of workers per shift. | Xβ, Xβ, Xβ β₯ 0 and are integers |
| Mixed ILP (MILP) | Some variables integer, others continuous. | Integer number of machines + continuous production quantity. | Xβ, Xβ β₯ 0 and Xβ is an integer |
| Binary / 0β1 ILP | Variables may only be 0 or 1. | Selecting projects, opening a warehouse, yes/no decisions. | Xα΅’ are binary (0, 1) |
An ILP answer that is identical to an LP answer earns LP marks. The integrality/binary statement is the whole point of the question β write it as its own labelled line at the end, never buried in the non-negativity line.
2. Logical Constraints β the Binary Toolkit Core syllabus concept
1Understand the Concept
Binary variables are powerful because ordinary algebra can express logical conditions. Every exam ILP question hides one of these. Learn the table and you can translate any English restriction into a constraint on sight.
| English in the question | Constraint to write | Why it works |
|---|---|---|
| "C and E cannot be undertaken together" (mutually exclusive) | X_C + X_E β€ 1 |
Both = 1 would give 2 > 1. Allows neither, or exactly one. |
| "Exactly one of P3 or P4 must be chosen, but not both" | Xβ + Xβ = 1 |
Forces the sum to exactly one β one is chosen, one is not. |
| "P1 must be done if P2 is selected" (contingent / prerequisite) | Xβ β€ Xβ |
If Xβ = 1 then Xβ must be 1. If Xβ = 0, Xβ is free. |
| "At least 3 projects should be chosen" | Xβ + Xβ + Xβ + Xβ β₯ 3 |
Direct count. |
| "At most 2 projects may be chosen" | Xβ + Xβ + Xβ + Xβ β€ 2 |
Direct count, other direction. |
| "A warehouse can supply up to 80 units only if it is opened" (linking / fixed-charge) | X_{i1} + X_{i2} + X_{i3} β 80Yα΅’ = 0 |
If Yα΅’ = 0 the whole shipment is forced to zero; if Yα΅’ = 1 capacity is 80. |
| "Tables must be produced in multiples of 10" | Define XΜβ = 10Xβ and require Xβ integer |
Batching β the class notes' Mixed ILP example Note 2 p. 20. |
X_i + X_j β€ 1 as a separate, labelled constraint. Write "Incompatibility constraint:" beside it so it cannot be missed.Practice G1βG5 β prerequisite, batching, fixed-charge, either-or β
3. The Seven Formulation Patterns Core syllabus concept
Every ILP question in the notes and the papers is one of these seven. Read them as a catalogue β recognise the pattern, then write the matching template.
1Pattern A β simple production ILP (Pure)
Dolls give βΉ3 profit and need 1 hour labour; cars give βΉ4 and need 2 hours. 6 labour hours available. Formulate an ILP.
2Pattern B β project selection under a budget (Binary)
3Pattern C β shift / workforce allocation (Pure)
At least 5 workers in morning, 3 in afternoon, 4 at night. A worker works exactly one shift. 10 workers available. Productivity 8, 6, 7 units respectively.
Note the class notes write the total as = 10 rather than β€ 10, on the reading that every available worker is assigned. Either is defensible provided you state your assumption β the paper's instruction "assume suitable data if necessary" explicitly permits this.
4Pattern D β cutting stock / trim loss (Pure)
Orders: 10 rolls of 1 m, 8 rolls of 2 m, 6 rolls of 3 m. Minimise the number of big rolls used. The trick is that the decision variable is the cutting pattern, not the product.
5Pattern E β multi-resource project selection with a minimum (Binary)
6Pattern F β fixed-charge / facility location (Mixed binary)
Fixed costs A = 100, B = 120, C = 150 (βΉ lakh). Each warehouse supplies up to 80 units only if opened. Demands Rβ = 50, Rβ = 60, Rβ = 40.
This is the hardest pattern in the unit β it mixes a transportation structure (Unit 3) with binary open/close decisions. The linking constraint is what makes it work: it is impossible to ship from a warehouse you did not open.
7Pattern G β projects with logical dependencies (Binary)
The deck prints the budget line as = 100; a budget is a ceiling, so β€ 100 is the defensible reading and is what you should write. Flag the assumption in one line if you do.
- Omitting the integrality/binary line. The single most costly omission in this unit.
- Defining Xα΅’ as a quantity when it should be a yes/no. If the question says "which projects should be selected", Xα΅’ is binary β not "number of projects".
- Forgetting to write out what the binary means. "Let Xα΅’ = 1 if project i is selected, else 0" is a marked line.
- Missing the logical constraint entirely. It is deliberately buried in one sentence near the end of the question stem. Read the last two lines of every ILP question twice.
Practice G2 β mixed ILP with batch production β