GOMORY’S CUTTING PLANE ALGORITHM Gomory Algorithm ...

GOMORY'S CUTTING PLANE ALGORITHM

Gomory Algorithm Background :

? Consider standard LP problem with all variables restricted to integers

? Basic strategy: a) use simplex algorithm to solve LP; b) iteratively add constraints (cutting planes) to find optimal integer solution.

? Cutting Plane Example A (Exer. 6.1.2): Maximize 2x1 + 9x2,

subject to 2x1 + x2 20, x1 + 5x5 24, with integer x1, x2 0.

Simplex

solution

(849,

3

1 9

);

z

=

4489.

Constraint Lines 2x+y=20, x+5y=24

6

5

4

y

3

2

1

0

0

2

4

6

8

10

12

x

2

GOMORY'S CUTTING PLANE ALGORITHM CONT.

Cutting Plane Example A: first new constraint

x1 x2 x5

x1 x2 x3

x1 1 0 0 0 1 0 0 0

x2 0 1 0 0 0 1 0 0

x3

5 9

-1

9

-5

9 1 9

0

0

1

0

x4 -1

9 2 9

-8

9 16 9

-1

2 5 8 5 8 5

x5 0

0

1

0

1 -1

5

-9

5 1 5

76 9 28 9

-4

9 404

9

8

16 5 4 5 224 5

Page1 of 1 printed on April 14, 2016 by genz at 11:15:43 AM PDT

3

GOMORY'S CUTTING PLANE ALGORITHM CONT.

Cutting Plane Example A: second new constraint

x1

x2

x3

x4

x5

x6

x1

1

0

0

-1

1

0

8

x2

0

1

0

2 5

-1

5

0

16 5

x3

0

0

1

8 5

-9

5

0

4 5

x6

0

0

0

-3

5

-1

5

1

-4

5

8

1

224

0

0

0

5

5

0

5

x1

1

0

0

-4

0

5

4

x2

0

1

0

1

0

-1

4

x3

0

0

1

7

0

-9

8

x5

0

0

0

3

1

-5

4

0

0

0

1

0

1

44

Page1 of 1 printed on April 14, 2016 by genz at 11:16:12 AM PDT

4

GOMORY'S CUTTING PLANE ALGORITHM CONT.

Gomory Algorithm Details : let [a] be greatest integer a (rounding down), and define the fractional part of a to be = a - [a].

1. Begin with LP in standard form for application of simplex method. 2. Apply simplex method until convergence, and select any noninteger bi constraint:

aijxj = bi

j

3. Rewrite constraint using fractional parts fij = aij - [aij], fi = bi - [bi]:

fijxj - fj = [bj ] - [aij]xj

j

j

Heuristic for step 2: choose bi with largest fi.

4. Add new constraint j fijxj - fj 0, with integer excess, to tableau.

5. Repeat steps 2-4 (using dual simplex) until all rhs bi 's are integers.

5

GOMORY'S CUTTING PLANE ALGORITHM CONT.

Gomory Algorithm Analysis :

? For each iteration, consider converged

xt

simplex tableau at step 2 with m ? n A:

xB A b . ct z0

For any noninteger basic variable xB(i)

xB(i) = bi = j ai,jxj j[ai,j]xj j[ai,j][xj].

? So, for integer x, j[ai,j]xj [xB(i)]; add integer slack xn+1 0.

[bi ] = j[ai,j]xj + xn+1.

Integer solutions to original problem must satisfy new constraint. ? Subtract to get extra constraint for tableau:

fi = fi,jxj - xn+1, or - fi,jxj + xn+1 = -fi.

j

j

? New constraint (plane) "cuts" off part of original feasible region, but revised tableau has same integer solutions as original problem.

? Issues with Gomory algorithm: no integer solution until end; rounding errors.

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download