Week3
Week3
2023-2024 Spring
Week 3
Integer Programming
c(x)=25x, 0≤x≤500
- Write 𝑥 as a convex combination of the
breakpoints.
- Write 𝑐(𝑥) as a convex combination of the
cost values corresponding to the
breakpoints.
𝑧1 𝑧2 𝑧3 𝑧4
800, z2 ve z3 arasında bu sebeple z1 ve z4 0 olur
𝑦2 𝑧1 ≤ 𝑦1
𝑧2 ≤ 𝑦1 + 𝑦2
𝑧3 ≤ 𝑦2 + 𝑦3
𝑦1 𝑧4 ≤ 𝑦3
𝑦1 + 𝑦2 + 𝑦3 = 1 Choose one segment
𝑧1 + 𝑧2 + 𝑧3 + 𝑧4 = 1
𝑦𝑖 ∈ 0,1 , 𝑖 = 1,2,3, 𝑧𝑖 ≥ 0, 𝑖 = 1,2,3,4
𝑧1 𝑧2 𝑧3 𝑧4
𝑦3 - Define a {0,1} variable 𝑦𝑖 for each
segment.
- Relate the 𝑦𝑖 variables with the 𝑧
variables.
𝑦2 𝑧1 ≤ 𝑦1
For the selected
𝑧2 ≤ 𝑦1 + 𝑦2
segment, z variables
𝑧3 ≤ 𝑦2 + 𝑦3
can be positive.
𝑦1 𝑧4 ≤ 𝑦3
𝑦1 + 𝑦2 + 𝑦3 = 1
𝑧1 + 𝑧2 + 𝑧3 + 𝑧4 = 1
𝑦𝑖 ∈ 0,1 , 𝑖 = 1,2,3, 𝑧𝑖 ≥ 0, 𝑖 = 1,2,3,4
𝑧1 𝑧2 𝑧3 𝑧4
𝑦3 - Define a {0,1} variable 𝑦𝑖 for each
segment.
- Relate the 𝑦𝑖 variables with the 𝑧
variables.
𝑦2 𝑧1 ≤ 𝑦1
𝑧2 ≤ 𝑦1 + 𝑦2
𝑧3 ≤ 𝑦2 + 𝑦3 z’s should sum up
𝑧4 ≤ 𝑦3 to 1 for taking the
𝑦1
𝑦1 + 𝑦2 + 𝑦3 = 1 convex
𝑧1 + 𝑧2 + 𝑧3 + 𝑧4 = 1 combination.
𝑦𝑖 ∈ 0,1 , 𝑖 = 1,2,3, 𝑧𝑖 ≥ 0, 𝑖 = 1,2,3,4
𝑧1 𝑧2 𝑧3 𝑧4
The whole mathematical model:
The whole mathematical model: To set 𝑥 = 800,
𝑦2 = 1, 𝑦1 = 𝑦3 = 0
Then,
𝑧2 ≤ 1
𝑧3 ≤ 1
𝑧1 = 𝑧4 = 0
𝑧2 + 𝑧3 = 1,
𝑥 = 500𝑧2 + 1000𝑧3
𝑐 𝑥 = 12500𝑧2 + 22500𝑧3
To set 𝑥 = 800,
𝑧2 = 2/5
𝑧3 = 3/5
𝑐 𝑥 = 18500
The whole mathematical model:
How to obtain;
x=200, x=1200 ?
𝑥1 ≥ 4 𝑥1 ≤ 3
SP 2 SP 3
𝑥1 ≥ 4 𝑥1 ≤ 3
SP 2 SP 3
𝑧 = 41
t=2 𝑥1 = 4
𝑥2 = 9/5
𝑥2 ≥ 2 𝑥2 ≤ 1
SP 4 SP 5
Let’s
continue
with the most
recently
created SP,
arbitrarily
choose SP4.
SP4 is infeasible. It is fathomed (it yields no useful information if we continue branching).
40
Let’s continue with SP5. Optimal solution of SP5 is point I, (𝑥1 , 𝑥2 ) = 9
,1 , 𝑧 = 365/9.
SP 1
t=1 𝑧=
165
= 41.25
4
𝑥1 ≥ 4 𝑥1 ≤ 3
SP 2 SP 3
t=2
𝑧 = 41
𝑥2 ≥ 2 𝑥2 ≤ 1
SP 4
t=3 infeasible SP 5
365
𝑧= = 40.56
9 t=4
40
𝑥1 =
9
𝑥2 = 1
𝑥1 ≥ 5 𝑥1 ≤ 4
SP 6 SP 7 Let’s
continue
with the most
recently
created SP,
arbitrarily
choose SP7.
Optimal solution of SP7 is point H, 𝑥1 , 𝑥2 = 4, 1 , 𝑧 = 37.
Since all variables are integer, we fathom SP7 (no need to continue branching).
Solution of SP7 is a candidate solution. It is a Lower Bound to the original problem, 𝑧 ≥ 37.
SP 1
t=1 165
𝑧= = 41.25
4
𝑥1 ≥ 4 𝑥1 ≤ 3
SP 2 SP 3
t=2 𝑧 = 41
𝑥2 ≥ 2 𝑥2 ≤ 1
SP 4 SP 5
t=3 infeasible 𝑧 = 40.56
t=4
𝑥1 ≥ 5 𝑥1 ≤ 4
SP 6 SP 7 t=5
𝑧 = 37
Candidate solution
𝑥1 = 4
𝑥2 = 1
𝑥1 ≥ 4 𝑥1 ≤ 3
SP 2 SP 3
t=2
𝑧 = 41
𝑥2 ≥ 2 𝑥2 ≤ 1
SP 4 SP 5
t=3 infeasible 𝑧 = 40.56
t=4
𝑥1 ≥ 5 𝑥1 ≤ 4
SP 6 SP 7
𝑧 = 40 𝑧 = 37
t=6 t=5
𝑥1 = 5 𝑥1 = 4
𝑥2 = 0 𝑥2 = 1
Candidate solution
𝑥1 ≥ 4 𝑥1 ≤ 3
SP 2
t=2 SP 3
𝑧 = 41
𝑧 = 39 t=7
𝑥2 ≥ 2 𝑥2 ≤ 1
𝑥1 = 3
𝑥2 = 3
SP 4 SP 5
t=3 infeasible 𝑧 = 40.56
t=4
𝑥1 ≥ 5 𝑥1 ≤ 4
SP 6 SP 7
𝑧 = 40 𝑧 = 37
t=6 t=5
𝑥1 = 5 𝑥1 = 4
𝑥2 = 0 𝑥2 = 1
Candidate solution
𝑥1 ≥ 4 𝑥1 ≤ 3
SP 2
t=2 SP 3
𝑧 = 41
𝑧 = 39 t=7
𝑥2 ≥ 2 𝑥2 ≤ 1
𝑥1 = 3
𝑥2 = 3
SP 4 SP 5
t=3 infeasible 𝑧 = 40.56
t=4
𝑥1 ≥ 5 𝑥1 ≤ 4
SP 6 SP 7
𝑧 = 40 𝑧 = 37
t=6 t=5
𝑥1 = 5 𝑥1 = 4
𝑥2 = 0 𝑥2 = 1
Candidate solution