Week 1
Sets notation
ℕ = {0, 1, 2, 3 … }, ℤ! = {1, 2, 3, … }, ℤ = {… , −1, 0, 1, … } and 𝔹 = {0, 1}
Binary linear programming problem
Needed if the decision variables are of the yes/no type
max ∑#"$% 𝑐" 𝑥"
𝑠. 𝑡. ∑#"$% 𝑎&" 𝑥" ≤ 𝑏& 1≤𝑖≤𝑚
𝑥" ∈ 𝔹 1≤𝑗≤𝑛
matrix notation: max{𝒄 𝒙: 𝐴𝒙 ≤ 𝒃, 𝒙 ∈ 𝔹# }
'
Integer linear programming problems
Needed if the decision variables are of the discrete type
max ∑#"$% 𝑐" 𝑥"
𝑠. 𝑡. ∑#"$% 𝑎&" 𝑥" ≤ 𝑏& 1≤𝑖≤𝑚
𝑥" ∈ ℕ 1≤𝑗≤𝑛
matrix notation: max{𝒄 𝒙: 𝐴𝒙 ≤ 𝒃, 𝒙 ∈ ℕ# }
'
Mixed integer linear programming problems
Needed if some of the decision variables are discrete or binary valued and some continuous
max ∑#"$% 𝑐" 𝑥" + ∑)($% 𝑑( 𝑦(
𝑠. 𝑡. ∑#"$% 𝑎&" 𝑥" + ∑)($% 𝑐&( 𝑦( ≤ 𝑏& 1≤𝑖≤𝑚
𝑥" ≥ 0 1≤𝑗≤𝑛
𝑦( ∈ ℕ 1≤𝑘≤𝑝
matrix notation: max 𝒄 𝒙 + 𝒅 𝒚: 𝐴𝒙 + 𝐶𝒚 ≤ 𝒃, 𝒙 ≥ 𝟎, 𝒚 ∈ ℕ) }
{ ' '
Linear assignment problem
𝑛 tasks and 𝑛 persons, each person 1 task, 𝑐&" cost of executing task 𝑗 by person 𝑖, 𝑥&" = 1 if
person 𝑖 executes task 𝑗, minimize costs. The formulation is:
min ∑#&$% ∑#"$% 𝑐&" 𝑥&"
𝑠. 𝑡. ∑#"$% 𝑥&" = 1 1≤𝑖≤𝑛
#
∑&$% 𝑥&" = 1 1≤𝑗≤𝑛
𝑥&" ∈ 𝔹 1 ≤ 𝑖, 𝑗 ≤ 𝑛
Knapsack problem
𝑛 items, 𝑎" volume of item 𝑗, 𝑏 capacity of knapsack, 𝑐" utility of item 𝑗, 𝑥" = 1 if item 𝑗 is
selected, maximize utility. The formulation is:
max ∑#"$% 𝑐" 𝑥"
𝑠. 𝑡. ∑#"$% 𝑎" 𝑥" ≤ 𝑏
𝑥" ∈ 𝔹 1≤𝑗≤𝑛
Set covering problem
𝑁 = {1, … , 𝑛} set of routes, 𝑚 customers, 𝑐" cost of route 𝑗, 𝑥" = 1 if route 𝑗 is selected,
𝑎&" = 1 if customer 𝑖 is on route 𝑗, minimize costs. The formulation is:
min ∑#&$% 𝑐" 𝑥"
𝑠. 𝑡. ∑#"$% 𝑎&" 𝑥" ≥ 1 1≤𝑖≤𝑚
𝑥" ∈ 𝔹 1≤𝑗≤𝑛
Traveling salesman problem
𝑛 cities, 𝑐&" distance between city 𝑖 and city 𝑗, 𝑥&" = 1 if directed arc (𝑖, 𝑗) is a part of route,
minimize costs. The formulation is:
min ∑#&$% ∑#"$% 𝑐&" 𝑥&"
𝑠. 𝑡. ∑#"$% 𝑥&" = 1 1≤𝑖≤𝑛
#
∑&$% 𝑥&" = 1 1≤𝑗≤𝑛
∑&∈+ ∑"∈+ ! 𝑥&" ≥ 1 𝑆 ⊂ 𝑁, 𝑆 ≠ ∅
, 𝑥&" ∈ 𝔹 1 ≤ 𝑖, 𝑗 ≤ 𝑛
Uncapacitated facility location problem
𝑚 customers, 𝑛 possible locations for plants, 𝑐&" cost of delivering from location 𝑗 to
customer 𝑖, 𝑓" cost of plant located at 𝑗, 𝑦" = 1 if a plant is constructed of site 𝑗, 𝑥&" fraction
of demand of customer 𝑖 supplied by plant 𝑗, minimize costs. The formulation is:
min ∑#&$% ∑#"$% 𝑐&" 𝑥&" + ∑#"$% 𝑓" 𝑦"
𝑠. 𝑡. ∑#"$% 𝑥&" = 1 1≤𝑖≤𝑚
,
∑&$% 𝑥&" ≤ 𝑚𝑦" 1≤𝑗≤𝑛
𝑥&" ≥ 0 1 ≤ 𝑖 ≤ 𝑚, 1 ≤ 𝑗 ≤ 𝑛
𝑦" ∈ 𝔹 1≤𝑗≤𝑛
Uncapacitated lot-sizing problem
𝑛 periods, 𝑑- demand in period 𝑡, 𝑝- unit production costs in period 𝑡, ℎ- unit inventory
costs in period 𝑡, 𝑓- setup productions costs in period 𝑡, 𝑦- if production occurs in period 𝑡,
𝑥- number of produced items in period 𝑡, 𝑠- inventory level at the end of period 𝑡, minimize
costs. The formulation is:
min ∑#-$%(𝑝- 𝑥- + ℎ- 𝑠- + 𝑓- 𝑦- )
𝑠. 𝑡. 𝑠-.% + 𝑥- = 𝑑- + 𝑠- 1≤𝑡≤𝑛
𝑥- ≤ 𝑀𝑦- 1≤𝑡≤𝑛
𝑥- , 𝑠- ≥ 0 1≤𝑡≤𝑛
𝑦- ∈ 𝔹 1≤𝑡≤𝑛
𝑠/ = 0
Either-or restrictions
Take decision vector 𝒙 ∈ ℝ# satisfying 𝟎 ≤ 𝒙 ≤ 𝒖 with restriction 𝒂%' 𝒙 ≤ 𝑏% ∨ 𝒂'0 𝒙 ≤ 𝑏0
The feasible region is {𝟎 ≤ 𝒙 ≤ 𝒖: 𝒂%' 𝒙 ≤ 𝑏% } ∪ {𝟎 ≤ 𝒙 ≤ 𝒖: 𝒂'0 𝒙 ≤ 𝑏0 }
For the linear representation procedure, compute the constant 𝑀& , 𝑖 = 1, 2 satisfying
𝑀& ≥ max{𝒂'& 𝒙 − 𝑏& : 𝟎 ≤ 𝒙 ≤ 𝒖} for the following system with decision variables 𝒙, 𝑧% , 𝑧0
𝟎≤𝒙≤𝒖
𝒂%' 𝒙 − 𝑏% ≤ 𝑀% (1 − 𝑧% )
𝒂%' 𝒙 − 𝑏0 ≤ 𝑀0 (1 − 𝑧0 )
𝑧% + 𝑧0 = 1
𝑧& ∈ 𝔹 𝑖 = 1, 2
If 𝑧& = 1, then constraint 𝒂'& 𝒙 ≤ 𝑏& is satisfied
If-then restriction
Take the problem with following restrictions: 𝟎 ≤ 𝒙 ≤ 𝒖 and if 𝒂%' 𝒙 > 𝑏% , then 𝒂'0 𝒙 ≤ 𝑏0
This is the same as the restrictions 𝟎 ≤ 𝒙 ≤ 𝒖 and ¬𝒂%' 𝒙 > 𝑏% ∨ 𝒂'0 𝒙 ≤ 𝑏0
And this is the same as the restrictions 𝟎 ≤ 𝒙 ≤ 𝒖 and 𝒂%' 𝒙 ≤ 𝑏% ∨ 𝒂'0 𝒙 ≤ 𝑏0
Week 2
Polyhedra definition
A set 𝑃 ⊆ ℝ# is called a polyhedron, if there exists some 𝑚 × 𝑛 matrix 𝐴 and some 𝒃 ∈ ℝ#
such that 𝑃 ≔ {𝒙 ∈ ℝ# : 𝐴𝒙 ≤ 𝒃}
Formulations
By the definition of a polyhedron, it follows that any integer or binary linear programming
problem can be written as max{𝒄' 𝒙: 𝒙 ∈ 𝑃 ∩ ℤ# }, with 𝑃 a polyhedron. Also, every mixed
integer linear program can be written as max{𝒄' 𝒙: 𝒙 ∈ 𝑃 ∩ (ℝ) × ℤ# )}.
A polyhedron 𝑃 ⊆ ℝ#!) is called a formulation for a set 𝑋 ⊆ ℝ) × ℤ# if and only if
𝑋 = 𝑃 ∩ (ℝ) × ℤ# ). A problem can have different formulations
Sets notation
ℕ = {0, 1, 2, 3 … }, ℤ! = {1, 2, 3, … }, ℤ = {… , −1, 0, 1, … } and 𝔹 = {0, 1}
Binary linear programming problem
Needed if the decision variables are of the yes/no type
max ∑#"$% 𝑐" 𝑥"
𝑠. 𝑡. ∑#"$% 𝑎&" 𝑥" ≤ 𝑏& 1≤𝑖≤𝑚
𝑥" ∈ 𝔹 1≤𝑗≤𝑛
matrix notation: max{𝒄 𝒙: 𝐴𝒙 ≤ 𝒃, 𝒙 ∈ 𝔹# }
'
Integer linear programming problems
Needed if the decision variables are of the discrete type
max ∑#"$% 𝑐" 𝑥"
𝑠. 𝑡. ∑#"$% 𝑎&" 𝑥" ≤ 𝑏& 1≤𝑖≤𝑚
𝑥" ∈ ℕ 1≤𝑗≤𝑛
matrix notation: max{𝒄 𝒙: 𝐴𝒙 ≤ 𝒃, 𝒙 ∈ ℕ# }
'
Mixed integer linear programming problems
Needed if some of the decision variables are discrete or binary valued and some continuous
max ∑#"$% 𝑐" 𝑥" + ∑)($% 𝑑( 𝑦(
𝑠. 𝑡. ∑#"$% 𝑎&" 𝑥" + ∑)($% 𝑐&( 𝑦( ≤ 𝑏& 1≤𝑖≤𝑚
𝑥" ≥ 0 1≤𝑗≤𝑛
𝑦( ∈ ℕ 1≤𝑘≤𝑝
matrix notation: max 𝒄 𝒙 + 𝒅 𝒚: 𝐴𝒙 + 𝐶𝒚 ≤ 𝒃, 𝒙 ≥ 𝟎, 𝒚 ∈ ℕ) }
{ ' '
Linear assignment problem
𝑛 tasks and 𝑛 persons, each person 1 task, 𝑐&" cost of executing task 𝑗 by person 𝑖, 𝑥&" = 1 if
person 𝑖 executes task 𝑗, minimize costs. The formulation is:
min ∑#&$% ∑#"$% 𝑐&" 𝑥&"
𝑠. 𝑡. ∑#"$% 𝑥&" = 1 1≤𝑖≤𝑛
#
∑&$% 𝑥&" = 1 1≤𝑗≤𝑛
𝑥&" ∈ 𝔹 1 ≤ 𝑖, 𝑗 ≤ 𝑛
Knapsack problem
𝑛 items, 𝑎" volume of item 𝑗, 𝑏 capacity of knapsack, 𝑐" utility of item 𝑗, 𝑥" = 1 if item 𝑗 is
selected, maximize utility. The formulation is:
max ∑#"$% 𝑐" 𝑥"
𝑠. 𝑡. ∑#"$% 𝑎" 𝑥" ≤ 𝑏
𝑥" ∈ 𝔹 1≤𝑗≤𝑛
Set covering problem
𝑁 = {1, … , 𝑛} set of routes, 𝑚 customers, 𝑐" cost of route 𝑗, 𝑥" = 1 if route 𝑗 is selected,
𝑎&" = 1 if customer 𝑖 is on route 𝑗, minimize costs. The formulation is:
min ∑#&$% 𝑐" 𝑥"
𝑠. 𝑡. ∑#"$% 𝑎&" 𝑥" ≥ 1 1≤𝑖≤𝑚
𝑥" ∈ 𝔹 1≤𝑗≤𝑛
Traveling salesman problem
𝑛 cities, 𝑐&" distance between city 𝑖 and city 𝑗, 𝑥&" = 1 if directed arc (𝑖, 𝑗) is a part of route,
minimize costs. The formulation is:
min ∑#&$% ∑#"$% 𝑐&" 𝑥&"
𝑠. 𝑡. ∑#"$% 𝑥&" = 1 1≤𝑖≤𝑛
#
∑&$% 𝑥&" = 1 1≤𝑗≤𝑛
∑&∈+ ∑"∈+ ! 𝑥&" ≥ 1 𝑆 ⊂ 𝑁, 𝑆 ≠ ∅
, 𝑥&" ∈ 𝔹 1 ≤ 𝑖, 𝑗 ≤ 𝑛
Uncapacitated facility location problem
𝑚 customers, 𝑛 possible locations for plants, 𝑐&" cost of delivering from location 𝑗 to
customer 𝑖, 𝑓" cost of plant located at 𝑗, 𝑦" = 1 if a plant is constructed of site 𝑗, 𝑥&" fraction
of demand of customer 𝑖 supplied by plant 𝑗, minimize costs. The formulation is:
min ∑#&$% ∑#"$% 𝑐&" 𝑥&" + ∑#"$% 𝑓" 𝑦"
𝑠. 𝑡. ∑#"$% 𝑥&" = 1 1≤𝑖≤𝑚
,
∑&$% 𝑥&" ≤ 𝑚𝑦" 1≤𝑗≤𝑛
𝑥&" ≥ 0 1 ≤ 𝑖 ≤ 𝑚, 1 ≤ 𝑗 ≤ 𝑛
𝑦" ∈ 𝔹 1≤𝑗≤𝑛
Uncapacitated lot-sizing problem
𝑛 periods, 𝑑- demand in period 𝑡, 𝑝- unit production costs in period 𝑡, ℎ- unit inventory
costs in period 𝑡, 𝑓- setup productions costs in period 𝑡, 𝑦- if production occurs in period 𝑡,
𝑥- number of produced items in period 𝑡, 𝑠- inventory level at the end of period 𝑡, minimize
costs. The formulation is:
min ∑#-$%(𝑝- 𝑥- + ℎ- 𝑠- + 𝑓- 𝑦- )
𝑠. 𝑡. 𝑠-.% + 𝑥- = 𝑑- + 𝑠- 1≤𝑡≤𝑛
𝑥- ≤ 𝑀𝑦- 1≤𝑡≤𝑛
𝑥- , 𝑠- ≥ 0 1≤𝑡≤𝑛
𝑦- ∈ 𝔹 1≤𝑡≤𝑛
𝑠/ = 0
Either-or restrictions
Take decision vector 𝒙 ∈ ℝ# satisfying 𝟎 ≤ 𝒙 ≤ 𝒖 with restriction 𝒂%' 𝒙 ≤ 𝑏% ∨ 𝒂'0 𝒙 ≤ 𝑏0
The feasible region is {𝟎 ≤ 𝒙 ≤ 𝒖: 𝒂%' 𝒙 ≤ 𝑏% } ∪ {𝟎 ≤ 𝒙 ≤ 𝒖: 𝒂'0 𝒙 ≤ 𝑏0 }
For the linear representation procedure, compute the constant 𝑀& , 𝑖 = 1, 2 satisfying
𝑀& ≥ max{𝒂'& 𝒙 − 𝑏& : 𝟎 ≤ 𝒙 ≤ 𝒖} for the following system with decision variables 𝒙, 𝑧% , 𝑧0
𝟎≤𝒙≤𝒖
𝒂%' 𝒙 − 𝑏% ≤ 𝑀% (1 − 𝑧% )
𝒂%' 𝒙 − 𝑏0 ≤ 𝑀0 (1 − 𝑧0 )
𝑧% + 𝑧0 = 1
𝑧& ∈ 𝔹 𝑖 = 1, 2
If 𝑧& = 1, then constraint 𝒂'& 𝒙 ≤ 𝑏& is satisfied
If-then restriction
Take the problem with following restrictions: 𝟎 ≤ 𝒙 ≤ 𝒖 and if 𝒂%' 𝒙 > 𝑏% , then 𝒂'0 𝒙 ≤ 𝑏0
This is the same as the restrictions 𝟎 ≤ 𝒙 ≤ 𝒖 and ¬𝒂%' 𝒙 > 𝑏% ∨ 𝒂'0 𝒙 ≤ 𝑏0
And this is the same as the restrictions 𝟎 ≤ 𝒙 ≤ 𝒖 and 𝒂%' 𝒙 ≤ 𝑏% ∨ 𝒂'0 𝒙 ≤ 𝑏0
Week 2
Polyhedra definition
A set 𝑃 ⊆ ℝ# is called a polyhedron, if there exists some 𝑚 × 𝑛 matrix 𝐴 and some 𝒃 ∈ ℝ#
such that 𝑃 ≔ {𝒙 ∈ ℝ# : 𝐴𝒙 ≤ 𝒃}
Formulations
By the definition of a polyhedron, it follows that any integer or binary linear programming
problem can be written as max{𝒄' 𝒙: 𝒙 ∈ 𝑃 ∩ ℤ# }, with 𝑃 a polyhedron. Also, every mixed
integer linear program can be written as max{𝒄' 𝒙: 𝒙 ∈ 𝑃 ∩ (ℝ) × ℤ# )}.
A polyhedron 𝑃 ⊆ ℝ#!) is called a formulation for a set 𝑋 ⊆ ℝ) × ℤ# if and only if
𝑋 = 𝑃 ∩ (ℝ) × ℤ# ). A problem can have different formulations
