Summary
Summary Combinatorial Optimisation (FEB22002X)
- Course
- Institution
Comprehensive summary of Combinatorial Optimisation (econometrics EUR)
[Show more]
Seller
Follow
LeonVerweij
Reviews received
Content preview
Week 1Sets 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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller LeonVerweij. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.50. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
67474 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now