Assignment 10 — Integer Linear Programming
Two fixed-charge facility-location models (mixed ILP) and two capital-budgeting models with logical conditions — formulated in full, then solved, including one model whose conditions cannot all be met and one with a misprinted condition.
- Pick the variable type: yes/no decisions (open a centre, select a project) ⟹ binary yᵢ ∈ {0, 1}; quantities shipped ⟹ continuous xᵢⱼ ≥ 0. Both together ⟹ mixed ILP (MILP).
- Objective: fixed costs × y + variable costs × x (facility problems); profit × y (project selection). Put every term in the same unit.
- Link x to y with a capacity constraint: Σⱼ xᵢⱼ ≤ capacity × yᵢ — a closed centre (y = 0) can ship nothing.
- Logical conditions become linear constraints (table below), plus the budget.
- State the variable restrictions: yᵢ ∈ {0, 1}, xᵢⱼ ≥ 0.
| Condition | Constraint |
|---|---|
| If A is selected, B must be selected | x_A ≤ x_B |
| Either A or B, but not both (exactly one) | x_A + x_B = 1 |
| At most one of A and B | x_A + x_B ≤ 1 |
| At least k projects | Σ xᵢ ≥ k |
| A and B together or not at all | x_A = x_B |
Theory and the exam versions: Unit 2 · Integer Linear Programming.
- Units trap: fixed costs in lakh, transport per unit in rupees. Convert (100 lakh = ₹1,00,00,000) or the objective adds apples to oranges.
- "If A then B" is x_A ≤ x_B — never x_B ≤ x_A. Test it: A = 1 forces B = 1 ✓; A = 0 leaves B free ✓.
- Always test feasibility of a project-selection model by listing the few combinations that satisfy the logic — it catches contradictory conditions, as in Q3.
Q1 — Which distribution centres to open (MILP)
Three possible distribution centres — A Jaipur, B Lucknow, C Bhopal — each with capacity 120 units if opened. Fixed costs (₹ lakh): 100, 85, 115. Per-unit costs (₹): A → 4, 7, 6; B → 6, 3, 5; C → 7, 5, 4. Demand: H1 50, H2 80, H3 70. Formulate the MILP: decision variables, objective, constraints.
Assignment 10 p. 1
- Step 1 — Decision variables yᵢ = 1 if site i is opened, 0 otherwise (i = A, B, C) xᵢⱼ = units supplied from site i to hospital j (j = 1, 2, 3)
- Step 2 — Objective (in rupees: 1 lakh = 1,00,000) Min Z = 1,00,00,000yA + 85,00,000yB + 1,15,00,000yC + ΣᵢΣⱼ cᵢⱼxᵢⱼΣΣ cᵢⱼxᵢⱼ = 4xA1 + 7xA2 + 6xA3 + 6xB1 + 3xB2 + 5xB3 + 7xC1 + 5xC2 + 4xC3
- Step 3 — Constraints xA1 + xA2 + xA3 ≤ 120yA ← capacity of Jaipur, only if opened xB1 + xB2 + xB3 ≤ 120yB ← capacity of Lucknow, only if opened xC1 + xC2 + xC3 ≤ 120yC ← capacity of Bhopal, only if opened xA1 + xB1 + xC1 = 50 ← demand of H1 xA2 + xB2 + xC2 = 80 ← demand of H2 xA3 + xB3 + xC3 = 70 ← demand of H3 yᵢ ∈ {0, 1}; xᵢⱼ ≥ 0
- Going further — the optimum
Total demand 200 > one site's capacity 120 ⟹ at least two sites must open
Open A Jaipur and B Lucknow: A→H1 50; A→H3 30; B→H2 80; B→H3 40 — total ₹1,85,00,820Open Fixed (₹ lakh) Best transport cost Total A + B 185 ₹820 ₹1,85,00,820 ← min B + C 200 ₹830 ₹2,00,00,830 A + C 215 ₹940 ₹2,15,00,940 A + B + C 300 ₹720 ₹3,00,00,720 The fixed costs dwarf the transport costs, so the cheapest pair of sites that can cover demand wins; the transport plan only fine-tunes it.
Q2 — Which charging hubs to open (MILP)
Three possible charging hubs — A Thane, B Nashik, C Sambhajinagar — each with capacity 150 sessions if opened. Fixed costs (₹ lakh): 140, 105, 120. Per-unit costs (₹): A → 5, 6, 8; B → 7, 4, 5; C → 6, 7, 3. Demand: Z1 60, Z2 90, Z3 80. Formulate the MILP: decision variables, objective, constraints.
Assignment 10 p. 1
- Step 1 — Decision variables yᵢ = 1 if site i is opened, 0 otherwise (i = A, B, C) xᵢⱼ = sessions supplied from site i to zone j (j = 1, 2, 3)
- Step 2 — Objective (in rupees: 1 lakh = 1,00,000) Min Z = 1,40,00,000yA + 1,05,00,000yB + 1,20,00,000yC + ΣᵢΣⱼ cᵢⱼxᵢⱼΣΣ cᵢⱼxᵢⱼ = 5xA1 + 6xA2 + 8xA3 + 7xB1 + 4xB2 + 5xB3 + 6xC1 + 7xC2 + 3xC3
- Step 3 — Constraints xA1 + xA2 + xA3 ≤ 150yA ← capacity of Thane, only if opened xB1 + xB2 + xB3 ≤ 150yB ← capacity of Nashik, only if opened xC1 + xC2 + xC3 ≤ 150yC ← capacity of Sambhajinagar, only if opened xA1 + xB1 + xC1 = 60 ← demand of Z1 xA2 + xB2 + xC2 = 90 ← demand of Z2 xA3 + xB3 + xC3 = 80 ← demand of Z3 yᵢ ∈ {0, 1}; xᵢⱼ ≥ 0
- Going further — the optimum
Total demand 230 > one site's capacity 150 ⟹ at least two sites must open
Open B Nashik and C Sambhajinagar: B→Z2 90; C→Z1 60; C→Z3 80 — total ₹2,25,00,960Open Fixed (₹ lakh) Best transport cost Total B + C 225 ₹960 ₹2,25,00,960 ← min A + B 245 ₹1100 ₹2,45,01,100 A + C 260 ₹1080 ₹2,60,01,080 A + B + C 365 ₹900 ₹3,65,00,900 The fixed costs dwarf the transport costs, so the cheapest pair of sites that can cover demand wins; the transport plan only fine-tunes it.
Q3 — Renewable energy projects — logical conditions
| Project | Investment (₹ lakh) | Expected return (₹ lakh) |
|---|---|---|
| P1 Solar farm | 30 | 70 |
| P2 Wind park | 40 | 90 |
| P3 Battery storage | 50 | 110 |
| P4 Green hydrogen | 60 | 130 |
Budget ₹120 lakh. (1) If P2 is selected, P1 must be. (2) Exactly one of P3 and P4. (3) At most one of P2 and P3. (4) At least three projects. Formulate the ILP.
Assignment 10 p. 1
- Step 1 — Variables xⱼ = 1 if project Pj is selected, 0 otherwise (j = 1…4)
- Step 2 — Objective Max Z = 70x₁ + 90x₂ + 110x₃ + 130x₄
- Step 3 — Constraints 30x₁ + 40x₂ + 50x₃ + 60x₄ ≤ 120 ← budget x₂ ≤ x₁ ← (1) P2 needs P1 x₃ + x₄ = 1 ← (2) P3 or P4, not both x₂ + x₃ ≤ 1 ← (3) at most one of P2, P3 x₁ + x₂ + x₃ + x₄ ≥ 3 ← (4) at least three xⱼ ∈ {0, 1}
- Going further — test the model
Conditions (2) and (4) leave only {P1, P2, P3} or {P1, P2, P4}. The first breaks (3); the second costs 30 + 40 + 60 = ₹130 lakh > 120. So the model as printed has no feasible solution — QM for Windows would report it infeasible. The formulation above is still exactly what is asked; in the exam, add one line noting the conflict. With a ₹130 lakh budget the answer would be {P1, P2, P4}, return ₹290 lakh; relaxing (4) to "at least two" gives {P1, P4}, return ₹200 lakh.
Q4 — Consumer electronics projects — and a misprinted condition
| Project | Development cost (₹ lakh) | Expected profit (₹ lakh) |
|---|---|---|
| P1 Smartwatch | 35 | 75 |
| P2 Wireless earbuds | 45 | 85 |
| P3 Smart home hub | 55 | 105 |
| P4 Portable projector | 65 | 125 |
Budget ₹150 lakh. (1) If P3 is selected, P2 must be. (2) Exactly one of P1 and P4. (3) "At most one of P2 and P2" — misprinted. (4) At least two projects. Formulate the ILP. (The handout table reuses Q3's project names; the costs and profits are Q4's.)
Assignment 10 p. 2
- Step 1 — Variables and objective xⱼ = 1 if Pj is selected, 0 otherwise Max Z = 75x₁ + 85x₂ + 105x₃ + 125x₄
- Step 2 — Constraints 35x₁ + 45x₂ + 55x₃ + 65x₄ ≤ 150 ← budget x₃ ≤ x₂ ← (1) P3 needs P2 x₁ + x₄ = 1 ← (2) P1 or P4, not both x_a + x_b ≤ 1 ← (3) at most one of the intended pair x₁ + x₂ + x₃ + x₄ ≥ 2 ← (4) at least two xⱼ ∈ {0, 1}
- Step 3 — Handling the misprint
State the pair you assume. The optimum under each reasonable reading:
Reading of (3) Best selection Cost Profit x₂ + x₃ ≤ 1 {P2, P4} ₹110 lakh ₹210 lakh x₂ + x₄ ≤ 1 {P1, P2, P3} ₹135 lakh ₹265 lakh x₃ + x₄ ≤ 1 {P1, P2, P3} ₹135 lakh ₹265 lakh If (3) means P2 and P3, it clashes with (1) — P3 could then never be chosen — which suggests a different pair was intended. Writing "assuming (3) refers to P3 and P4: x₃ + x₄ ≤ 1" keeps every mark.