Skip to content
Sem 5 Prep
← BI & Data ScienceInteger, binary and mixed-integer programming

Formulas for this chapter

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
Step 2 of 23
Worked examplePractical

Worked example: the deck's nearby integer points

Maximise reach Z = 5,000x + 8,000y subject to x + 2y <= 20 (budget) and 2x + y <= 30 (time), x and y whole numbers.

The continuous optimum is (13.33, 3.33) with reach 93,333. Test the whole-number points around it, as the deck does.

0 of 9 lines shown.

← BackContinue →