Benders (once more ...)

(1)

Thomas Stidsen 1

Benders (once more ...)

Thomas Stidsen

thst@man.dtu.dk

DTU-Management

Technical University of Denmark

(2)

Outline

The algorithm

The assignment from last week GAMS Implementation

(3)

Thomas Stidsen 3

Definitions

RBMP: Relaxed Benders Master Problem BPSP: Benders Primal Sub-Problem: The direct formulation for finding the u values.

BDSP: Benders Dual Sub-Problem: The original problem with fixed y values

RGP: Ray Generation Problem

(4)

But ...

When we solve the BPSP ( the u problem) what if:

Problem solved: No problem (we add optimality cut)

Problem infeasible: We have a solution which is infeasible because of the y values. Hence we need a feasibility cut based on an extreme ray.

Problem un-bounded: Original problem un-bounded !

(5)

Thomas Stidsen 5

Benders Alorithm

Initialize RBMP, RGP, BDSP/BPSP Z_LO = −∞, Z_{U P} = ∞, y, ǫ

while Z_{U P} − Z_LO > ǫ

Solve BDSP(y) or BPSP(y)getting u if feasible

update Z_{U P}

Add Optimality constraint else

Solve RGP(y) getting u Add Feasibility constraint Solve RBMP getting y

update Z_LO endwhile

(6)

Example

Min:

z⁰ = 5x − 3y s.t.:

x + 2y ≥ 4 2x − y ≥ 0

x − 3y ≥ −13 x ≥ 0

y ∈ {0, . . . , 10}

Optimal value: (x=2.5, y=5), z=-2.5

(7)

Thomas Stidsen 7

Example 10.6: The B matrix

A =

2 6 6 4

1 2 1

3 7 7 5

B =

2 6 6 4

2 -1 -3

3 7 7 5

b^T = [4, 0, −13]

c^T = [5]

f^T = [−3]

(8)

The Optimality cuts

The optimality cuts we are looking for are:

z⁰ ≥ f^T y + (uⁱ)^T (b − By) i = 1, . . . , q

Which becomes:

z⁰ ≥ −3y + (uⁱ)^T ([4, 0, −13]^T − [2, −1, −3]^T y)

Hence, every time we find new optimality cut values, i.e. u values, we only have to plug them in, in the above equation.

(9)

Thomas Stidsen 9

Example

Min:

z⁰ = 5x − 3y s.t.:

x ≥ 4 − 2y 2x ≥ 0 + y

x ≥ −13 + 3y x ≥ 0

y ∈ {0, . . . , 10}

Optimal value: (x=2.5, y=5), z=-2.5

(10)

1. Iteration: Subproblem

Max:

z¹ = (4 − 2y)u¹ + y · u² + (−13 + 3y)u³ s.t.:

u¹ + 2u² + u³ ≤ 5 u_i ≥ 0

(11)

Thomas Stidsen 11

Inititialisation

Initial solution

¯

y⁰ = 0. Upper bound:

U P⁰ = ∞. Lower bound:

LO⁰ = −∞.

(12)

Graphical BMP, initialisation

10

1 Y

Z

120 100 80 20

60 40

(13)

Thomas Stidsen 13

1. Iteration: Subproblem

Max:

z¹ = 4u¹ − 13u³ s.t.:

u¹ + 2u² + u³ ≤ 5 u_i ≥ 0

(14)

1. Iteration: Subproblem

Optimal solution:

¯

z¹ = 20

¯

u = (5, 0, 0) Giving a new upper bound:

U P¹ = min{z¯¹, U P⁰(= ∞)} = 20. And arriving at the cut:

z⁰ ≥ −3y + (5, 0, 0)^T ([4, 0, −13]^T − [2, −1, −3]^T y)

=

z ≥ −13y + 20

(15)

Thomas Stidsen 15

1. Iteration: Benders Master Problem

Min:

z¹ s.t.:

z¹ ≥ 20 − 13y y ∈ {0, . . . , 10}

(16)

1. Iteration: Benders Master Problem

Optimal solution

¯

z¹ = −110

¯

y = 10

New lower bound:

LO¹ = max{z¯¹, LO⁰(= −∞)} = −110.

(17)

Thomas Stidsen 17

Graphical BMP, 1. iteration

Z >= 20 − 13y

Y Z

Optimum 20

40

60

80

100

120

1

10

(18)

2. iteration: Primal Subproblem

Max:

z² = −16u¹ + 10u² + 17u³ − 30 s.t.:

u¹ + 2u² + u³ ≤ 5 u_i ≥ 0

(19)

Thomas Stidsen 19

2. iteration: Primal Subproblem

Optimal solution:

¯

z² = 55

¯

u = (0, 0, 5)

New upper bound: U P² = min{z¯², U P¹(= 20)} = 20.

(20)

2. iteration: Benders Master Problem

Min:

z² s.t.:

z² ≥ 20 − 13y z² ≥ −65 + 12y

y ∈ {0, . . . , 10}

(21)

Thomas Stidsen 21

2. iteration: Benders Master Problem

Optimal solution:

z² = −19 y = 3

New upper bound:

LO² = min{z¯², LO¹(−110)} = −19.

(22)

Graphical BMP, 2. iteration

Optimum

Y Z

20

40

60

80

100

120

1

10

Z >= 20 − 13y Z >= −65 + 12y

(23)

Thomas Stidsen 23

3. iteration: Primal Subproblem

Max:

z³ = −2u¹ + 3u² − 4u³ − 9 s.t.:

u¹ + 2u² + u³ ≤ 5 u_i ≥ 0

(24)

3. iteration: Primal Subproblem

Optimal solution:

¯

z² = −1.5

¯

u = (0, 2.5, 0)

New upper bound:

U P³ = min{z¯³, U P²(= 19)} = −2.5.

(25)

Thomas Stidsen 25

3. iteration: Benders Master Problem

Min:

z³ s.t.:

z³ ≥ 20 − 13y z³ ≥ −65 + 12y z³ ≥ −0.5y

y ∈ {0, . . . , 10}

(26)

3. iteration: Benders Master Problem

Optimal solution:

z³ = −2.5 y = 5

New

lowerbound:LO³ = max{z¯¹, LO³(= −19)} = −2.5. Now: LO³ = U P³

(27)

Thomas Stidsen 27

Graphical BMP, 3. iteration

Z >= 20 − 13y

Y Z

Optimum 20

40

60

80

100

120

1

10

Z >= −65 + 12y

Z >= −0.5y

(28)

Exercise 10.1 (RKM)

Several constraints are added without improving bound (in case of minimization, non-increasing) why: Primal degeneracy: Possible to include new variables into the simplex tableau without changing the objective value (the new variables may stay at value zero). Dual degeneracy: If the current

“solution” has several active constraints.

(29)

Thomas Stidsen 29

Exercise 10.2 (RKM)

If the Bender’s subproblem is infeasible what does that imply about the original problem ?

Original problem un-bounded ! Why ? Bender’s Dual Sub-Problem is then un-bounded.

Bender’s Dual Sub-Problem is a restricted

version of the original problem meaning, hence the original problem is also un-bounded.

(30)

How did we get here ?

Original Problem

Full Benders Master Problem

Project out x variables

Relaxed Benders Problem

Benders Dual Sup−Problem (Original Problem)

Ray Generation Problem Drop some (all ?) constraints

Benders Sub−Problem

(31)

Thomas Stidsen 31

Master Problem: Lowerbound

Farka’s lemma guarantees direct

correspondence between original problem and the Full Benders Master Problem

The Relaxed Benders Master Problem will hence always give a lower bound ...

(32)

Sub Problem: Upperbound

Bender’s dual problem is a restricted version of the original problem, hence a solution to the

sub-problem is also a solution to the original problem

(33)

Thomas Stidsen 33

The Benders Sub-problem

Max:

f^T y + (b − By)^T u s.t.:

A^T u ≤ c u ≥ 0

Problem: If the objective is un-bounded, how to find rays ?

(34)

Extreme rays

We need to find the extreme rays in the cone {u|A^T u ≤ 0, u ≥ 0}, such that a cut

(uⁱ)^T (b − By) > 0 is found, see Proposition 10.3, hence:

Max:

(b − By)^T u s.t.:

A^T u ≤ 0

0 ≤ u ≤ L

(35)

Thomas Stidsen 35

Ray generation: An example

Min:

2x¹ + 6x² + 2y¹ + 3y² s.t.:

−x¹ + 2x² + 3y¹ − y² ≥ 5 x¹ − 3x² + 2y¹ + 2y² ≥ 4

x¹, x² ≥ 0 y ∈ {0, 1, 2}

(36)

Primal Subproblem

Max:

u¹ · [5 − 3y¹ + y2] + u² · [4 − 2y¹ − 2y²] s.t.:

−u1 + u² ≤ 2 2u¹ − 3u² ≤ 6 u¹, u² ≥ 0

(37)

Thomas Stidsen 37

Visually

00 11

0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000

1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111

000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000

111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111

0000 0000 1111 1111

00 00 11 11

u2=(0,2)

u3=(3,0) (u1,u2)=(1,1)

u1=(0,0)

00 11

(u1,u2)=(3,2)

(38)

Objectives for subproblem

(5 − 3y¹ + y², 4 − 2y¹ − 2y²), and y¹, y² ∈ {0, 1, 2}

(0,0) : (5,4) (0,1) : (6,2) (0,2) : (7,0) (1,0) : (2,2) (1,1) : (3,0) (1,2) : (4,−2) (2,0) : (−1,0) (2,1) : (0,−2) (2,2) : (1,−4)

(39)

Thomas Stidsen 39

Visually with possible objectives

(0,−2)

(3,0)

(7,0)

(4,−2)

(5,4) (6,2)

(1,−4)

00 11 00 11

00 11

0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000 0000000000000

1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111 1111111111111

000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000 000000000000

111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111 111111111111

(−1,0)

(2,2)

(40)

First iteration

Initial guess for (y¹, y²) = (1, 1): Max:

u¹ · [5 − 3y¹ + y2] + u² · [4 − 2y¹ − 2y²] = 3u¹ s.t.:

−u1 + u² ≤ 2 2u¹ − 3u² ≤ 6 u¹, u² ≥ 0

(41)

Thomas Stidsen 41

Tabular LP form, first iteration

B.V. u¹ u² d¹ d² R.S. UB

Z -3 0 0 0 0

d¹ -1 1 1 0 2 no limit

d² 2 -3 0 1 6 u¹ ≤ ⁶₂ = 3 ← min B.V.: Basic Variables

R.S.: Right hand side

(42)

Tabular LP form, first iteration

B.V. u¹ u² d¹ d² R.S. UB Z 0 -⁹₂ 0 ³₂ 9

d¹ 0 -¹₂ 1 ¹₂ 5 no limit u¹ 1 -³₂ 0 ¹₂ 3 no limit

We can increase u² as much as we like !!! Ok, so what is the extreme ray ?

(43)

Thomas Stidsen 43

The simplex tableau as equations

−1

2u² + d¹ + 1

2d² = 5 u¹ − 3

2u² + 1

2d² = 3

But when we use the simplex algorithm, we only want to increase one variable at the time, and we hence freeze the slack variable d² = 0

(44)

After the freeze

u1 = 3 + 3 2u2

d¹ = 5 + 1 2u²

⇓

u² = 2

3u¹ − 2

(45)

Thomas Stidsen 45

To find extreme rays by problem modifications

Ok, that’s all very nice, but what about using computer codes for finding the rays ?

(46)

Extreme Ray

The extreme rays arises when our dual subproblem is unbounded:

Max:

dummy_z s.t.:

dummy_z = 0 f^T y + (b − By)^T u = 1 A^T u ≤ 0 u ≥ 0

(47)

Thomas Stidsen 47

Modifications

Zero right hand sides

Dummy objective (the objective does not matter

!)

Fix value of objective function to 1

What solution will the simplex or dual-simplex solve find ?

(48)

Example

A good example with the fixed charge

Transportation Problem ... see the Erwin Kalvelagen note.

(49)

Thomas Stidsen 49

The Fixed Charge Transportation problem

Min: X

i,j

(f_i,jy_i,j + c_i,jx_i,j) s.t.:

X

j

x_i,j = s_i ∀i X

i

x_i,j = d_j ∀j

x_i,j ≤ M_iy_i,j ∀i, j x_i,j ≥ 0 y_i,j ∈ {0, 1}

(50)

Benders (primal) subproblem

Max: X

i

(−s_i)u_i + X

j

d_jv_j + X

i,j

(−M_i,jy_i,j)w_i,j

s.t.:

u_i + v_j − w_i,j ≤ c_i,j ∀i, j u_i, v_j, w_i,j ≥ 0

(51)

Thomas Stidsen 51

Benders Master Problem

Min:

z s.t.:

z ≥ X

i,j

f_i,jy_i,j + X

i

(−s_i)u^k_i + X

j

d_jv^k_j

+ X

i,j

(−M_i,jw^k_i,j)y_i,j ∀k

0 ≥ X

i

(−s_i)u^k_i ^′ + X

j

d_jv^k_j^′

+ X

i,j

(−M_i,jw^k_i,j^′ )y_i,j ∀k^′

(52)

Extreme rays

What about the extreme rays ? How does Kalvelagen handle these ?

How does he detect an extreme ray ? He adds an artificial upper bound on the objective !

If the optimal objective value is significantly less than the upper bound, he assumes it to be

correct ...

If there is an extreme ray, he adds the dummy objective adds the objective constraint and fix the original objective value to 1 and solve the

(53)

Thomas Stidsen 53

Changed Benders Subproblem

Max:

dummy s.t.:

dummy = 0 X

i

(−s_i)u_i + X

j

d_jv_j + X

i,j

(−M_i,jy_i,j)w_i,j = 1

u_i + v_j − w_i,j ≤ c_i,j ∀i, j u_i, v_j, w_i,j ≥ 0