Binary decision model
Maximise SUM (return_j x x_j)
subject to SUM (cost_ij x x_j) <= budget_i for each period i
x_j in {0, 1}
Any accept-or-reject list: projects, plants, machines, product launches. Declared in Solver as a bin constraint on the changing cells.
- x_j
- 1 if item j is chosen, 0 otherwise
- return_j
- NPV or return of item j
- cost_ij
- Resource or cash item j consumes in period i
- budget_i
- Resource available in period i
Logical constraints on binaries
at most one of 1, 2 x1 + x2 <= 1
exactly one of 1, 2 x1 + x2 = 1
4 only if 3 x4 <= x3
at least one of a set SUM x_j >= 1
at most k of a set SUM x_j <= k
if 1 or 3 then 5 x5 >= x1 AND x5 >= x3
Translating the words of a problem statement into algebra. Always test a conditional constraint by substituting 0 and 1 for the trigger.
- x_j
- Binary decision, 1 for chosen
- k
- The stated maximum number of items
LP relaxation as a bound
Maximisation: Z(integer) <= Z(relaxation)
Minimisation: Z(integer) >= Z(relaxation)
Judging how much the integer restriction costs, and knowing when further search is pointless. Example: relaxation 93,333, integer optimum 92,000, gap 1.4 %.
- Z(relaxation)
- Objective with the integer requirement dropped
- Z(integer)
- Best objective achievable with whole numbers