This detailed handwritten summary on Optimization covers key concepts and methods from both lecture notes and tutorial notes. It includes topics such as linear optimization models, simplex methods, duality in optimization, sensitivity analysis, integer linear optimization, and dynamic programming. ...
Lecture 5 Integer Linear Optimization
1. ILo-models :
integer linear optimisation
max[cte Axb , x 0 , integers
>
integrality constraints : ' integer
integer point :
point whose
corresponding vector has integer-valued entries
*Lo-relaxation removing the integrality constraints from 120-model
:
maxEci Axeb <03 >Maxi Axeb xo x integer 1 , , ,
.
2 MILo-models : mixed integer linear optimisation
max (, x , + C2
S t . .
A , 34 + AzTz = D
30
>0 & integer
with A: myn , matrix
A2 : My He Matrix
similarly to 10-model ,
10-relaxation applies
.
3 Branch & Bound divide I conquer approach
1) start with solve the 10-relaxation &
(2) If solution is integer-valued then stop coptimal sol found) ·
-
else divide feasible region of 10-relaxation
,
Fo into 2 sub-regions
Flor & Floe
with Froi FloFlozE Flo
"
: E
Fro 1 1 Flor = 0 disjoint
10 sol. no longer feasible
i (FOUFO) FU Fo2 some
current sol. no longer in either #
v .
(F1L8 : U Filo2) =
FiLo all integer sol Still in either F
.
Fo
~
Flor FLOz all integer solutions
Still in either Foe/Froz
Since
omitted current solution excluded
* implicit enumeration of all integer solutions
* Branch
& cut :
cut constraints are added during the iterations of the branch bound
algorithm
to
yield better upper bounds on the optimal objective value
than branch & bound can provide alone
, example :
dairy corp.
M1 : max 10007 , + 700x2
S t
.
.
2072 :510
100x +
50x = 2425
Th , The 0
Tho =
[11 ,
2512] found graphically
z10 =
. 35
29
12 = 25 12726
L Y
M2 :
max 1000 , + 7001 Mz :
Max 1000, + 7007
S t .
.
T40 =
[11314, 25] infeasible ,
constraints 1d5 violate
zo =
29 25 .
each other
now branch on :
(11 ,
The 12
* problem is partioned if LP-feasible & fractional with better bound
zo ; = Z10 ; = Epst = E *0 = Evol
4.
integer knapsack problem
given are n type of items with value C & volume weight a
for j =
1, ....
n
find a selection of items with maximal value that fits knapsack
with capacity b
assume items are ordered S t . d , de .
,
Y . .
. On
an
- 1st item in the rank is the most valuable
: number of items selected of type ;
x =
max([
; [ = b , , 0 & integer Vi
↑
&
.
5 Dinary knapsack problem
same layout as integer problem ,
but now :
Xi =
1 if item i is selected &O otherwise
max([i ; [ D Teso 13/ 3 =
,
,
6 continuous knapsack problem
same layout as
binary problem but ,
now :
max[[(j1; [jajj =b ,
0
< 1 fil
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper lucia2001. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €5,46. Je zit daarna nergens aan vast.
