Resume
Samenvatting Combinatorisch Optimaliseren (FEB22002)
- Cours
- Établissement
Uitgebreide samenvatting van Combinatorisch Optimaliseren (econometrie EUR)
[Montrer plus]
Vendeur
S'abonner
LeonVerweij
Avis reçus
Aperçu du contenu
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
Les avantages d'acheter des résumés chez Stuvia:
Qualité garantie par les avis des clients
Les clients de Stuvia ont évalués plus de 700 000 résumés. C'est comme ça que vous savez que vous achetez les meilleurs documents.
L’achat facile et rapide
Vous pouvez payer rapidement avec iDeal, carte de crédit ou Stuvia-crédit pour les résumés. Il n'y a pas d'adhésion nécessaire.
Focus sur l’essentiel
Vos camarades écrivent eux-mêmes les notes d’étude, c’est pourquoi les documents sont toujours fiables et à jour. Cela garantit que vous arrivez rapidement au coeur du matériel.
Foire aux questions
Qu'est-ce que j'obtiens en achetant ce document ?
Vous obtenez un PDF, disponible immédiatement après votre achat. Le document acheté est accessible à tout moment, n'importe où et indéfiniment via votre profil.
Garantie de remboursement : comment ça marche ?
Notre garantie de satisfaction garantit que vous trouverez toujours un document d'étude qui vous convient. Vous remplissez un formulaire et notre équipe du service client s'occupe du reste.
Auprès de qui est-ce que j'achète ce résumé ?
Stuvia est une place de marché. Alors, vous n'achetez donc pas ce document chez nous, mais auprès du vendeur LeonVerweij. Stuvia facilite les paiements au vendeur.
Est-ce que j'aurai un abonnement?
Non, vous n'achetez ce résumé que pour 6,99 €. Vous n'êtes lié à rien après votre achat.
Peut-on faire confiance à Stuvia ?
4.6 étoiles sur Google & Trustpilot (+1000 avis)
70055 résumés ont été vendus ces 30 derniers jours
Fondée en 2010, la référence pour acheter des résumés depuis déjà 14 ans