BAN402 – Decision Modelling in

Business

Lecturer
Mario Guajardo
[email protected]

Fall 2022 26-September-2022

Page 80

2
Outline Lecture 7
 Integer linear programming and
Mixed integer linear programming
- Fixed cost problem
- Knapsack problem
- Facility location problem
- Assignment problem

 Literature
- Chapter 20: “Integer linear programs” in AMPL book.
- Chapter 13: “Integer programming models” in Optimization textbook.

3
Integer programming
 An integer programming (IP) problem is a
problem where one or several variables are
restricted to integer values or, more
precisely, to discrete values (countable set).

xj ∈ {0,1,2,3,4}
1 2 3 Note by defining yj = 4xj, the new
xj ∈ 0, , , , 1
4 4 4 variable yj can only take integer values

xj ∈ {0,1} We will mainly focus on this type of decisions

4
Integer programming (p.324)

 Example
Max z = x1 + x2
s.t. 11x1 - 8x2 ≤ 22
11x1 - 12x2 ≥ 0
x1, x2 ≥ 0, integer

Note we will still require linearity in objective function and constraints,

so strictly speaking we are studying integer linear models.

5
 Feasible set: Max z = x1 + x2
{(0,0);(1,0);(2,0);(2,1);(3,2);(4,3)}
s.t. 11x1 - 8x2 ≤ 22
11x1 - 12x2 ≥ 0
x1, x2 ≥ 0, integer

Optimal solution:
x1* = 4
x2* = 3

Optimal objective value:

z* = 7

6
LP relaxation
 If we remove the integer requirements on
the variables, we get a linear programming
problem which is called the LP relaxation of
the integer programming problem.

Max z = x1 + x2
Keep the same O.F.
s.t. 11x1 - 8x2 ≤ 22 and constraints
11x1 - 12x2 ≥ 0
Replace integer for
x 1, x 2 ≥ 0 continuous condition
(Of course, the integer points that were
feasible in the IP are also contained in the
feasible region of this relaxed problem)
7
The feasible region of the LP
Max z = x1 + x2
relaxation is delimited by the s.t. 11x1 - 8x2 ≤ 22
triangle in this figure
Optimal solution of the LP 11x1 - 12x2 ≥ 0
relaxation: x 1, x 2 ≥ 0
x1* = 6; x2* = 5.5
z* = 11.5
Optimal solution of the IP:
x1* = 4
x2* = 3

Optimal objective value of the IP:

z* = 7

8
IP and LP relaxation
 In the LP relaxation all variables may take
fractional values, while the IP requires only integer
values.
 The objective function of the LP is continuous,
while the one of the IP, in general, is not.
 The feasible region of the LP behaves more
smoothly (it is convex), while the feasible area of
the IP is a set of discrete points (non-convex).
 The optimal solution to an LP can always be found
in a corner point of the feasible area (intersection
of constraint lines), while the solution to the IP will
rarely lie in a corner. 9
IP solution
 It is harder to solve an integer linear model than a
continuous linear model.
 Rounding the solution of the LP relaxation to the
closest integer might be reasonable only in some
(few) cases. In general, the rounded solution may
not even be feasible.

10
 Optimal solution of the LP
relaxation:
Max z = x1 + x2
x1* = 6; x2* = 5.5
s.t. 11x1 - 8x2 ≤ 22
11x1 - 12x2 ≥ 0
x 1, x 2 ≥ 0

Rounded solution: x1* = 6; x2* = 6, does not satisfy the

second constraint (11 ˟ 6 - 12 ˟ 6 = - 6 < 0 )
x1* = 6; x2* = 5, does not satisfy the first constraint (11 ˟ 6 -
8 ˟ 5 = 26 > 22 ) 11
General IP model
 A general integer linear programming model
with n variables and m constraints can be
formulated as
𝑛𝑛

𝑀𝑀𝑀𝑀𝑀𝑀 𝑧𝑧 = � 𝑐𝑐𝑗𝑗 𝑥𝑥𝑗𝑗

𝑗𝑗=1
s.t.
𝑛𝑛

� 𝑎𝑎𝑖𝑖𝑖𝑖 𝑥𝑥𝑗𝑗 ≤ 𝑏𝑏𝑖𝑖 𝑖𝑖 = 1, … , 𝑚𝑚

𝑗𝑗=1
xj ≥ 0 , integer j=1,…,n
12
IP, MIP and 0/1 problems
 If all the variables are integer, we have a
pure integer programming problem. In
particular, if all variables are binary, that is,
variables can take values either 0 or 1, we
have a 0/1-problem.

 If only some variables are integer and other

variables are continuous, we have a mixed
integer programming problem.

13
Why studying integer models?
Two main reasons.
1) Variables are “naturally” integer, then it is
not reasonable to get a solution by rounding
the solution to the LP relaxation.
 If x is a variable to decide the kg of apples to
transport from supply to demand point, and the
optimal solution to the LP relaxation is 1530.2, it
sounds reasonable to round this to x = 1530.
 If y is a variable to decide the number of certain type
of machines to use in a refinery and the optimal
solution to the LP relaxation is y = 2.7, it is perhaps
less reasonable to round this solution. 14
Why studying integer models?
Two main reasons.
1) Variables are “naturally” integer, then it is
not reasonable to get a solution by rounding
the solution to the LP relaxation.
 If x is a variable to decide how much to deposit in a
bank account and the optimal solution to the LP
relaxation is 1,500,000.25 NOK, it sounds
reasonable to round this to x = 1,500,000 NOK.
 If y is a variable to decide whether to implement a
project or not (not possible to implement a fraction of
the project) and the optimal solution to the LP
relaxation is 0.4, it is less reasonable to round. 15
Why studying integer models?
Two main reasons.
2) Binary 0/1 variables help to improve the
model ability.
 Modelling fixed cost.
 Modelling Yes/No decisions.
 Logical restrictions.
e.g. if A happens, then B cannot happen and vice
versa. xA + xB ≤ 1
 When only a discrete set of values is allowed.
e.g. if w can only take one of the values 0, 4, 7 or 10 can be modelled as
w = 4x + 7y + 10z, where x + y + z ≤ 1 and x, y, z ∈{0,1} 16
Solving IP models
AMPL coding
 Syntax remains the same as for continuous
problems, except for definition of variables:

var x integer >=0; # x in {0,1,2,…}

var y binary; # y in {0,1}

var w {MySetP} integer >=0;

var z {MySetI,MySetJ} binary;
17
Fixed cost (p.327 in text book; p.440 in AMPL book)

Problems where total cost includes a fixed

cost:
 Fixed cost to run activity
 Initial investment on a project
 Setup cost of a machine to start production
 Fixed cost of using a facility
 Cost to expand capacity
 Fixed cost to use a link on a network

18
Fixed cost
f + cx if x > 0
Total cost
Total cost =
0 if x = 0
f + cx
f

Total cost is a sum of a fixed cost f to start

production and a variable production cost c
– Fixed cost does not depend on the amount produced
– Variable cost linearly increases with the amount produced
19
 Fixed cost model
Define a binary variable y, which takes value 1
if x > 0, and zero otherwise
1 if x > 0 This binary variable
y= represents a decision
0 if x = 0 (e.g. producing or not)

Minimize Total cost = fy + cx

s.t. x ≤ My (… other constraint
to model some
x≥0 requirements, e.g.,
satisfy demand…)
y ∈ {0,1}
M is a constant value chosen sufficiently big (e.g. the
maximum capacity of production) 20
 KEEP LINEARITY!
When defining or using the variable in AMPL,
no command if should be used! Otherwise
linearity is missed.
1 if x > 0 This definition is what we aim
to get, but we cannot use it as
y= such in a linear model.
0 if x = 0 Declare: var y binary;
Minimize Total cost = fy + cx
s.t. x ≤ My This is a linear
formulation, ok!
x≥0
y ∈ {0,1}
M is a constant value chosen sufficiently big (e.g. the
maximum capacity of production) 21
Example of a fixed cost problem
 Because of excessive pollution on the Mommis
River, the state of Mommis wants to build
pollution treatment stations. Three sites (1, 2
and 3) are under consideration.
 Mommis is interested in controlling the pollution
levels of two pollutants (1 and 2). The state
legislature requires that at least 80,000 tons of
pollutant 1 and at least 50,000 of pollutant 2 will
be removed from the river.
 Minimize the cost of meeting the state
legislature’s goals. 22
Problem data
Fixed cost Variable cost

Amount removed per

Cost of
Cost of 1000[lt] of water
treating
Site building
1000[lt] of
station
water Pollutant 1 Pollutant 2

1 100 000 20 0.40 0.30

2 60 000 30 0.25 0.20

3 40 000 40 0.20 0.25

Target pollutant 1 = 80 000 [ton]

Target pollutant 2 = 50 000 [ton]
23
Example of a fixed cost problem
I: set of sites
P: set of pollutants
fi: cost of building station at site i
ci: cost of treating 1000[lt] of water at site i
aip: amount of pollutant p removed per 1000[lt] of water
treated at site i
tp: target of pollutant p to be removed
Decision variables
xi = amount of water treated at site i (in 1000lt or [klt])
1 if pollution treatment station is built at site i
yi =
0 otherwise 24
Objective function

𝑀𝑀𝑀𝑀𝑀𝑀 𝑧𝑧 = �(𝑓𝑓𝑖𝑖 𝑦𝑦𝑖𝑖 + 𝑐𝑐𝑖𝑖 𝑥𝑥𝑖𝑖 )

𝑖𝑖∈𝐼𝐼
𝑀𝑀𝑀𝑀𝑀𝑀 𝑧𝑧
= 100,000 𝑦𝑦1 + 60,000 𝑦𝑦2 + 40,000 𝑦𝑦3 + 20𝑥𝑥1
+ 30𝑥𝑥2 + 40𝑥𝑥3

25
Constraints
• Targets of pollutant reduction must be satisfied

� 𝑎𝑎𝑖𝑖𝑖𝑖 𝑥𝑥𝑖𝑖 ≥ 𝑡𝑡𝑝𝑝 ∀𝑝𝑝 ∈ 𝑃𝑃

𝑖𝑖∈𝐼𝐼

0.40𝑥𝑥1 + 0.25𝑥𝑥2 + 0.20𝑥𝑥3 ≥ 80,000 (pollutant 1)

0.30𝑥𝑥1 + 0.20𝑥𝑥2 + 0.25𝑥𝑥3 ≥ 50,000 (pollutant 2)

• Water is only processed in sites where a station has been built

𝑥𝑥𝑖𝑖 ≤ 𝑀𝑀𝑦𝑦𝑖𝑖 ∀𝑖𝑖 ∈ 𝐼𝐼
𝑥𝑥1 ≤ 𝑀𝑀𝑦𝑦1 (site 1)
𝑥𝑥2 ≤ 𝑀𝑀𝑦𝑦2 (site 2)
𝑥𝑥3 ≤ 𝑀𝑀𝑦𝑦3 (site 3) 26
Constraints
• Nature of the variables
𝑥𝑥𝑖𝑖 ≥ 0 ∀𝑖𝑖 ∈ 𝐼𝐼
𝑦𝑦𝑖𝑖 ∈ {0,1} ∀𝑖𝑖 ∈ 𝐼𝐼

Solving the model in AMPL/CPLEX

Definition of binary variables y

This is a “very large” M (if possible avoid

arbitrarily big numbers and use your
knowledge on the problem, to avoid
numerical issues)
27
Solving the model in AMPL/CPLEX
General model code

Based on knowledge At most 400,000 klt of water must be

processed to remove the required pollutants
M=
Maximum quotient (tp/aip) = 80 000/0.20 = 400 000 28
Solving the model in AMPL/CPLEX
y1 = 1 x1 = 200,000
y2 = 0 x2 = 0
y3 = 0 x3 = 0

The optimal decision is to build the station at site 1 only,

and processing 200,000 [klt] of water in this site.
The amount of pollutant 1 reduced is:
200,000×0.40=80,000 [ton]
The amount of pollutant 2 reduced is:
200,000×0.30=60,000 [ton]
The total cost is 4,100,000 (fixed cost 100,000 + variable
cost 20x200,000)
29
Knapsack problem (p.330)

Select the “best” objects (projects,

investments), given a resource
constraint, such as
 weight
 budget
 time

Requirement: no shares or proportions of full objects

or projects can be chosen.

30
Knapsack problem
J : set of objects
cj : benefit added by object j if it is chosen
aj : weight of object j (amount of resource it uses)
b : maximum weight (or resource available)

Decision variables
For each object j we define a binary variable:

1 if item j is chosen
xj =
0 otherwise

31
Knapsack problem
Objective function
Maximize total benefit

𝑀𝑀𝑀𝑀𝑀𝑀 𝑧𝑧 = � 𝑐𝑐𝑗𝑗 𝑥𝑥𝑗𝑗

𝑗𝑗∈𝐽𝐽
Constraints
Maximum weight the knapsack can hold

� 𝑎𝑎𝑗𝑗 𝑥𝑥𝑗𝑗 ≤ 𝑏𝑏
𝑗𝑗∈𝐽𝐽

Binary nature of the variables

𝑥𝑥𝑗𝑗 ∈ {0,1} ∀𝑗𝑗 ∈ 𝐽𝐽 32
Knapsack with multiple resources
J : set of objects
I : set of resources
cj : benefit added by object j if it is chosen
aij : amount of resource i used by object j
bi : availability of resource i

Decision variables
For each object j we define a binary variable:
1 if item j is chosen
xj =
0 otherwise

33
Knapsack with multiple resources
Objective function
Maximize total benefit

𝑀𝑀𝑀𝑀𝑀𝑀 𝑧𝑧 = � 𝑐𝑐𝑗𝑗 𝑥𝑥𝑗𝑗

𝑗𝑗∈𝐽𝐽
Constraints
Maximum availability of each resource

� 𝑎𝑎𝑖𝑖𝑖𝑖 𝑥𝑥𝑗𝑗 ≤ 𝑏𝑏𝑖𝑖 ∀𝑖𝑖 ∈ 𝐼𝐼

𝑗𝑗∈𝐽𝐽

Binary nature of the variables

𝑥𝑥𝑗𝑗 ∈ {0,1} ∀𝑗𝑗 ∈ 𝐽𝐽 34
Example of Knapsack problem
 A company is considering four alternatives of
investments. Each alternative requires a certain
cash outflow at the present time and yields a net
present value (NPV), given in the table below.

Alternative 1 Alternative 2 Alternative 3 Alternative 4

NPV 16,000 22,000 12,000 8,000

I0 5,000 7,000 4,000 3,000

 Currently, $ 14 000 are available for investment

 Which alternatives should be chosen such that
total NPV is maximized? 35
Example of Knapsack problem
1 if investment on alternative j is chosen, j = 1,…,4
xj =
0 otherwise

𝑀𝑀𝑀𝑀𝑀𝑀 𝑧𝑧 = 16𝑥𝑥1 + 22𝑥𝑥2 + 12𝑥𝑥3 + 8𝑥𝑥4

s.t. 5𝑥𝑥1 + 7𝑥𝑥2 + 4𝑥𝑥3 + 3𝑥𝑥4 ≤ 14

𝑥𝑥𝑗𝑗 ∈ 0,1 𝑗𝑗 = 1, … , 4

Optimal IP solution: (0,1,1,1), that is, the investment on all

alternatives is made except for alternative 1. Total NPV = 42,000

Optimal LP solution (relax binary condition to 0 ≤ x ≤ 1): (1,1,0.5,0).

Total NPV = 44,000 Note the rounded solution is infeasible! 36
Facility location (p.332)

 A facility location problem consists of

choosing a set of facilities (e.g. terminals,
depots, distribution centres) and from these,
fulfil demand of a set of customers.
 Each facility has limited capacity.
 There is a fixed cost fi if facility i is chosen.
 The cost of supplying one unit from facility i
to customer j is cij.
 The goal is to satisfy all demand at minimum
total cost. 37
Facility location problem (p.61)

Extended from the transportation problem of Lecture 2

Milk company: Facilities & Customers 38

Table 2: Unit transportation cost (per litre) between facilities and customers
39
40
41
The company is examining the possibility of
closing down one ore several facilities since
they have excess capacity.
Fixed cost of operating each facility:

42
43
Mixed integer linear
programming model
45
Facility location problem: extension (p.333)

Each customer must be associated with only one facility.

cij: re-defined as cost of supplying total demand of customer j from i

Pure integer programming model (0/1- problem)

Assignment problem (p.337)

Every object in one set must be assigned

(allocated) to one object in another set of the same
cardinality.
cij : cost if object i ∈ I is assigned object j ∈ J (the
cost can be monetary cost, time, etc.)
Staff Projects

47
Assignment problem
1 if object i ∈ I is assigned object j ∈ J
xij =
0 otherwise

𝑀𝑀𝑀𝑀𝑀𝑀 𝑧𝑧 = � � 𝑐𝑐𝑖𝑖𝑖𝑖 𝑥𝑥𝑖𝑖𝑖𝑖

𝑖𝑖∈𝐼𝐼 𝑗𝑗∈𝐽𝐽
s.t.

� 𝑥𝑥𝑖𝑖𝑖𝑖 = 1 ∀ 𝑖𝑖 ∈ 𝐼𝐼
𝑗𝑗∈𝐽𝐽

� 𝑥𝑥𝑖𝑖𝑖𝑖 = 1 ∀ 𝑗𝑗 ∈ 𝐽𝐽
𝑖𝑖∈𝐼𝐼

𝑥𝑥𝑖𝑖𝑖𝑖 ∈ 0,1 ∀ 𝑖𝑖 ∈ 𝐼𝐼, 𝑗𝑗 ∈ 𝐽𝐽 48

49
Assignment problem

50