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 3 of 23
The real wordsTheory

Three kinds of integer model

All-integer modelEvery decision variable must be a whole number. Number of machines, number of staff, number of adverts.
Binary (0-1) modelEvery variable is restricted to 0 or 1, so each one answers a yes-or-no question: do we take this project, open this plant, buy this machine.
Mixed-integer modelSome variables are integer or binary and others stay continuous. The class advertising workbook is exactly this: television and radio are all-or-nothing, online and newspaper can be part-funded.
← BackContinue →