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
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 lucia2001. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $5.93. You're not tied to anything after your purchase.
