[go: up one dir, main page]

0% found this document useful (0 votes)
2 views38 pages

Week3

The document discusses Integer Programming as part of a course on Deterministic Operations Research, detailing mathematical models and methods such as convex combinations and the Branch-and-Bound method. It includes examples of cost functions, variable definitions, and step-by-step solutions to various programming scenarios. The document concludes with a comparison of solutions and the implications of using different methods in optimization problems.

Uploaded by

senasivrikaya
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
2 views38 pages

Week3

The document discusses Integer Programming as part of a course on Deterministic Operations Research, detailing mathematical models and methods such as convex combinations and the Branch-and-Bound method. It includes examples of cost functions, variable definitions, and step-by-step solutions to various programming scenarios. The document concludes with a comparison of solutions and the implications of using different methods in optimization problems.

Uploaded by

senasivrikaya
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 38

EMÜ 222

Deterministic Operations Research

2023-2024 Spring

Week 3
Integer Programming

Winston W.L., Operations Research, Chapter 9


c(x)=25 (500) + 20 (1000 -500) +
15 (x-1000), 1000≤x≤1500

c(x)=25 (500) + 20 (x-500), 500≤x≤1000

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.

𝑥 = 0 𝑧1 + 500 𝑧2 + 1000 𝑧3 + 1500 𝑧4

𝑐 𝑥 = 𝑧1 0 + 𝑧2 𝑐 500 + 𝑧3 𝑐 1000 + 𝑧4 𝑐(1500)

𝑐 500 = 25 500 = 12500


𝑐 1000 = 20 1000 + 2500 = 22500
𝑐 1500 = 15 1500 + 7500 = 30000
𝑧1 𝑧2 𝑧3 𝑧4
𝑥 = 0 𝑧1 + 500 𝑧2 + 1000 𝑧3 + 1500 𝑧4

𝑐 𝑥 = 0 𝑧1 + 12500 𝑧2 + 22500 𝑧3 + 30000 𝑧4

E.g., for 𝑥 = 800, solve the following equations.

500 𝑧2 + 1000 𝑧3 = 800, 𝑧2 + 𝑧3 = 1


Then, 𝑧2 = 2/5 , 𝑧3 = 3/5
and 𝑐 𝑥 = 12500(2/5) + 22500(3/5)= 18500

𝑧1 𝑧2 𝑧3 𝑧4
800, z2 ve z3 arasında bu sebeple z1 ve z4 0 olur

500 * z3 = 300 --> z3=0.6 z2=0.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
𝑦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:

Try other values.

How to obtain;
x=200, x=1200 ?

What are the values of y and z


in each case?
Check the Excel solution for the Media Selection problem.
The optimal solution to
the LP Relaxation is
(𝑥1 , 𝑥2 ) = 0,6 , 𝑧 = 12.

Since all variables take


integer values, this
solution is also optimal
for the IP.
Example – Branch-and-Bound Method (Pure IP)
Example – Branch-and-Bound Method (Pure IP)

Step 1. Start with the LP relaxation of


this problem.

The optimal solution is (𝑥1 , 𝑥2 ) =


3.75, 2.25 , 𝑧 = 165/4.
This is an Upper Bound for
SP 1 the original problem.
165
t=1 𝑧=
4
= 41.25 This means that the optimal
𝑥1 = 3.75 objective function value of
𝑥2 = 2.25 the original problem cannot
exceed 165/4.

𝑥1 ≥ 4 𝑥1 ≤ 3

SP 2 SP 3

Let’s continue with SP2.


Optimal solution of SP2 is point C, (𝑥1 , 𝑥2 ) = 4, 9/5 , 𝑧 = 41.
SP 1
165
t=1 𝑧= = 41.25
4
𝑥1 = 3.75
𝑥2 = 2.25

𝑥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

Let’s continue with the other recently created SP, SP6.


Optimal solution of SP6 is point A, 𝑥1 , 𝑥2 = 5, 0 , 𝑧 = 40.
Since all variables are integer, we fathom SP6 (no need to continue branching).
Solution of SP6 is another candidate solution. Its z-value is larger than SP7’s z-value. Thus,
SP7 cannot yield the optimal solution (place Χ near SP7). New Lower Bound is 40.
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
𝑧 = 40 𝑧 = 37
t=6 t=5
𝑥1 = 5 𝑥1 = 4
𝑥2 = 0 𝑥2 = 1

Candidate solution

Let’s continue with the only remaining SP, SP3.


Optimal solution of SP3 is point F, 𝑥1 , 𝑥2 = 3,3 , 𝑧 = 39.
Since the z-value of SP3 cannot yield a z-value exceeding 40 (Lower bound), place Χ near
SP3 and do not continue.
SP 1
t=1 165
𝑧= = 41.25
4

𝑥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

The optimal solution is 𝑥1 = 5 and 𝑥2 = 0, and 𝑧 = 40.


SP 1
t=1 165
𝑧= = 41.25
4

𝑥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

How would the B&B tree grow if we used jumptracking?


Example – Branch-and-Bound Method (Mixed IP)

The method is similar for Mixed IPs.


- Start with LP relaxation.
- Branch on only the integer variable.

A solution is a candidate solution, if the variable that is required to


be integer takes an integer value.
The optimal solution is 𝑥1 = 1 and 𝑥2 = 3/2, and 𝑧 = 7/2.

You might also like