Optimization Summary Part 2

* additional notes


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 .
.

2072 1510 S t .
.

2072 1510
10834 + 507 = 2425 10834 + 507 = 2425
12 =
25 T2 26
7 (20,
7 (20
,

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