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.
3Worked Example β why you cannot just round the LP answer
The LP below has the optimal solution Xβ = 3, Xβ = 1.5 with Z = 21. If both variables must be whole numbers, is it enough to round the answer? Show what actually happens.
Max Z = 5Xβ + 4Xβ s.t. 6Xβ + 4Xβ β€ 24 Xβ + 2Xβ β€ 6 Xβ, Xβ β₯ 0 and integer- Step 1 β Try rounding UP: (3, 2) Constraint 1 : 6(3) + 4(2) = 18 + 8 = 26 But the limit is 24, and 26 > 24 βΉ (3, 2) is INFEASIBLE β rounding up broke a constraint
- Step 2 β Try rounding DOWN: (3, 1) Constraint 1 : 6(3) + 4(1) = 22 β€ 24 β Constraint 2 : 3 + 2(1) = 5 β€ 6 β Z = 5(3) + 4(1) = 15 + 4 = 19 βΉ feasible, and it gives Z = 19
- Step 3 β But is 19 actually the best integer answer? Enumerate.
Xβ Largest feasible Xβ Z = 5Xβ + 4Xβ 0 6Xβ β€ 24 β Xβ = 4 20 + 0 = 20 1 6Xβ β€ 20 β Xβ = 3 15 + 4 = 19 2 Xβ + 4 β€ 6 β Xβ = 2 10 + 8 = 18 3 Xβ + 6 β€ 6 β Xβ = 0 0 + 12 = 12 - Step 4 β The point of the exercise
LP optimum : (3, 1.5) with Z = 21
Rounded down : (3, 1) with Z = 19
TRUE integer optimum: (4, 0) with Z = 20
Rounding the LP answer gave 19, but the real integer best is 20 at a completely different point β and rounding up was infeasible altogether. You cannot obtain the integer optimum by rounding; the problem must be modelled and solved as an ILP. That sentence is the answer to "why do we need integer programming".
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.2Worked Example β turn four English rules into constraints
A firm is choosing among four marketing channels with a budget of βΉ80 lakh. Costs are TV βΉ35 lakh, Radio βΉ25 lakh, Digital βΉ30 lakh, Print βΉ20 lakh; expected reach is 90, 55, 75 and 40 (lakh impressions). The rules are:
- At least two channels must be used.
- TV and Radio cannot both be used.
- If Digital is used, Print must also be used.
Formulate an ILP to maximise reach.
- Step 1 β Decide the variable type
Each channel is used or not used β there is no "0.4 of a TV campaign".
Let Xβ, Xβ, Xβ, Xβ = 1 if TV / Radio / Digital / Print is used, 0 otherwise - Step 2 β Objective function Max Z = 90Xβ + 55Xβ + 75Xβ + 40Xβ β total reach
- Step 3 β Budget constraint 35Xβ + 25Xβ + 30Xβ + 20Xβ β€ 80 β βΉ lakh
- Step 4 β Translate rule 1: "at least two channels" Count the channels used and require at least 2: Xβ + Xβ + Xβ + Xβ β₯ 2
- Step 5 β Translate rule 2: "TV and Radio not both"
If both were used the sum would be 2, so cap the sum at 1:
Xβ + Xβ β€ 1 β mutual exclusion
This permits neither, or exactly one β which is what "cannot both" means. Use
= 1only if the question says exactly one must be chosen. - Step 6 β Translate rule 3: "if Digital then Print" Digital used (Xβ = 1) must force Print (Xβ = 1): Xβ β€ Xβ β prerequisite / contingent decision Check Xβ = 1 : 1 β€ Xβ forces Xβ = 1 β Check Xβ = 0 : 0 β€ Xβ leaves Xβ free β
- Step 7 β The binary condition
Xβ, Xβ, Xβ, Xβ are binary (0, 1)
Without this line the model is an LP, and the whole question falls apart. It is worth a full mark on its own in the synoptic key.
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 β