MGMT90280 · Managerial Decision Analytics
Integer Linear Programming (ILP)
Integer Linear Programming (ILP) is the Seminar-2 topic of MGMT90280 Managerial Decision Analytics at the University of Melbourne, extending linear programming to decisions that must be whole numbers or plain yes/no choices. You will formulate pure-integer, mixed-integer and binary (0–1) programs, use the LP relaxation as a bound on the integer optimum, and solve and interpret them in Excel Solver — the selection and capital-budgeting models that anchor the optimisation question of the 50% final exam.
What this chapter covers
- 01Integer vs continuous decision variables: when a linear program needs whole-number answers
- 02Three model types: pure (all-integer) ILP, mixed-integer (MILP), and binary (0–1) programs
- 03The LP relaxation: dropping integrality to get an easier continuous problem
- 04The relaxation as a bound — an upper bound for a max, a lower bound for a min
- 05Why rounding the relaxation is unreliable (may be infeasible or sub-optimal)
- 06Yes/no modelling with 0–1 variables for project, plant and product-line decisions
- 07Logical constraints: at-most-k, exactly-k, multiple-choice, conditional, co-requisite, mutually exclusive
- 08Capital-budgeting formulation: objective, budget constraint and logical rules
- 09Solving in Excel Solver (Simplex LP + integer/binary, Integer Optimality 0%)
- 10Reading the Solver Answer Report and why ILP sensitivity analysis needs re-solving
Binary capital budgeting with logical constraints
- +1Decision variables: x_j = 1 if project j is funded, 0 if not, for j = 1..5 (all binary).
- +1Objective: Max NPV = 90x1 + 70x2 + 60x3 + 40x4 + 30x5 (in $000s).
- +2Budget constraint: 50x1 + 40x2 + 35x3 + 25x4 + 20x5 <= 120.
- +2P3 only if P1: x3 <= x1, i.e. x3 - x1 <= 0 (if P1 is rejected, x1 = 0 forces x3 = 0).
- +1At most one of P4 and P5: x4 + x5 <= 1.
- +1At least two projects: x1 + x2 + x3 + x4 + x5 >= 2, with every x_j in {0, 1}.
- +1Solve in Solver (Simplex LP, binary variables, Integer Optimality 0%): x1 = x2 = x4 = 1; x3 = x5 = 0.
- +1Decision: NPV = 90 + 70 + 40 = $200k; cost = 50 + 40 + 25 = $115k, so $5k of the $120k budget is unused.
Key terms
- Integer linear program (ILP)
- A linear program in which some or all decision variables are required to take whole-number values.
- Pure (all-integer) ILP
- An integer program in which every decision variable must be an integer.
- Mixed-integer program (MILP)
- A program in which only a subset of the variables are restricted to integers while the rest stay continuous.
- Binary (0–1) variable
- A variable restricted to 0 or 1, used to model a yes/no decision such as select/reject or build/don't-build.
- LP relaxation
- The linear program obtained by dropping the integer (or binary) requirement, so variables may be fractional; it is easier to solve and gives a bound.
- Relaxation bound
- The optimal objective of the LP relaxation bounds the integer optimum: an upper bound for a maximisation, a lower bound for a minimisation.
- Conditional constraint
- A logical row x_j <= x_i meaning option j can be chosen only if option i is chosen.
- Multiple-choice constraint
- A row summing several 0–1 variables to 1, forcing exactly one option to be selected.
Integer Linear Programming (ILP) FAQ
Can I just round the LP-relaxation answer to get the integer solution?
Not reliably. If the relaxation already comes out whole, it also solves the ILP. Otherwise rounding can be infeasible (it breaks a constraint) or feasible but sub-optimal (a better integer point lies at a different corner). The relaxation value is only a bound — an upper bound for a max, a lower bound for a min — so you should re-solve with the integer or binary requirement in Solver rather than round.
How do I turn 'project B only if project A' into a constraint?
Use binary variables x_A and x_B and write x_B <= x_A (equivalently x_B - x_A <= 0). Test it: if A is rejected then x_A = 0 forces x_B = 0, which is exactly the condition. Similarly 'not both' is x_A + x_B <= 1, and 'both or neither' is x_A = x_B.
Can AI help me with Integer Linear Programming (ILP) in MGMT90280?
Yes — Sia can explain ILP step by step: how to define binary variables, translate each English rule into a linear constraint, set up the model in Excel Solver, and read the Answer Report. It is a study aid that builds your understanding for the open-book final and coursework; it does not do assessed work for you or guarantee a grade, and Assignment 1 explicitly prohibits generative AI, so always follow the MGMT90280 assessment rules.
Exam move
Practise the full loop on selection and capital-budgeting problems: define each binary variable in words, translate one English sentence into one linear constraint, then solve in Excel Solver with Simplex LP, binary variables and Integer Optimality set to 0%. Drill the logical templates until they are automatic — at-most-k, exactly-one, conditional (x_j <= x_i), co-requisite and mutually exclusive — because a reversed inequality is the commonest lost mark. Always cross-check with the LP relaxation as a bound (upper for a max, lower for a min), and finish by stating the decision in business terms. In the ~November 2026 open-book final, budget time in proportion to marks (about 1.2 minutes per mark on a 100-mark, 2-hour paper); confirm the exact format on the LMS.
Working through Integer Linear Programming (ILP) in MGMT90280? Sia is AskSia’s AI Statistics tutor — ask any MGMT90280 Integer Linear Programming (ILP) question and get a clear, step-by-step explanation grounded in how MGMT90280 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
