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