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 1 of 23
The ideaTheory

You cannot run a third of a television advert

The advertising exercise in the last chapter ended at x = 13.33 social campaigns and y = 3.33 television adverts, reaching 93,333 customers.

Read it back to a marketing manager and she will laugh. There is no such thing as a third of a television advert.

The deck's own next slide asks exactly this, then evaluates the nearby whole-number points by hand. That is the honest way in: integer programming exists because some decisions come in indivisible lumps.

← BackContinue →