GOMORY CUTTING PLANE ALGORITHM USING EXACT ARITHMETIC By Kristin Farwell A Thesis Submitted to the Graduate Faculty of Rensselaer Polytechnic Institute in Partial Ful(cid:12)llment of the Requirements for the Degree of DOCTOR OF PHILOSOPHY Major Subject: Mathematics Approved by the Examining Committee: John Mitchell, Thesis Adviser Michael Kupferschmid, Member Joseph Ecker, Member Kristin Bennett, Member Aparna Gupta, Member Rensselaer Polytechnic Institute Troy, New York January 17, 2006 (For Graduation May 2006) GOMORY CUTTING PLANE ALGORITHM USING EXACT ARITHMETIC By Kristin Farwell An Abstract of a Thesis Submitted to the Graduate Faculty of Rensselaer Polytechnic Institute in Partial Ful(cid:12)llment of the Requirements for the Degree of DOCTOR OF PHILOSOPHY Major Subject: Mathematics The original of the complete thesis is on (cid:12)le in the Rensselaer Polytechnic Institute Library Examining Committee: John Mitchell, Thesis Adviser Michael Kupferschmid, Member Joseph Ecker, Member Kristin Bennett, Member Aparna Gupta, Member Rensselaer Polytechnic Institute Troy, New York January 17, 2006 (For Graduation May 2006) (cid:13)c Copyright 2006 by Kristin Farwell All Rights Reserved ii CONTENTS LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2. Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1 Primal Simplex Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Revised Simplex Algorithm . . . . . . . . . . . . . . . . . . . . . . . 21 2.3 Dual Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3. Exact Arithmetic and Matrix Implementation . . . . . . . . . . . . . . . . 25 3.1 Exact Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2 Exact vs. Real Arithmetic Simplex Algorithm . . . . . . . . . . . . . 28 3.3 Matrix Conditioning . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.4 Matrix Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4. Gomory Cutting Planes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5. Gomory Cutting Planes in Exact Arithmetic . . . . . . . . . . . . . . . . . 46 5.1 Weaker Gomory Cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 6. Degenerate Pivots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 7. Adding and Dropping Constraints . . . . . . . . . . . . . . . . . . . . . . . 64 8. Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 8.1 P0040 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 8.2 GT2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 8.3 MOD008 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 8.4 BM23 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 8.5 P0033 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 8.6 PIPEX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 8.7 LSEU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 iii 8.8 P0201 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 8.9 P0282 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 8.10 P0291 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 8.11 SENTOY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 9. CPLEX and Exact Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . 102 10.Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 iv LIST OF TABLES 1.1 Knapsack Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 3.1 Euclid’s Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.1 Average Size of Gomory cutting planes . . . . . . . . . . . . . . . . . . 50 5.2 Size of Gomory cutting planes for each Gomory Iteration . . . . . . . . 51 5.3 Objective Value and ROP for Example 6 . . . . . . . . . . . . . . . . . 54 8.1 MIPLIB Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 8.2 De(cid:12)nition Table for Table 8.1. . . . . . . . . . . . . . . . . . . . . . . . 73 8.3 Results Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 8.4 De(cid:12)nition Table for Table 8.3. . . . . . . . . . . . . . . . . . . . . . . . 74 8.5 Number of Gomory Cutting Planes for Problem P0201. . . . . . . . . . 90 v LIST OF FIGURES 1.1 A weak cutting plane on a two dimensional integer programming prob- lem found in [19] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 ConvexHullofthetwodimensionalintegerprogrammingproblemfound in [19] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1 Basic Simplex Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Revised Simplex Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.3 Basic Dual Simplex Algorithm . . . . . . . . . . . . . . . . . . . . . . . 23 4.1 Exact Strong Gomory Cutting Plane Algorithm . . . . . . . . . . . . . 37 4.2 Graph of the Original and all of the types of Gomory cutting planes . . 41 4.3 Original constraints of a simple example . . . . . . . . . . . . . . . . . . 42 4.4 First set of Gomory cutting planes for a simple example . . . . . . . . . 43 4.5 Second set of Gomory cutting planes for a simple example . . . . . . . . 44 4.6 Final set of Gomory cutting planes for a simple example . . . . . . . . . 45 5.1 Feasible Integer Points for Example . . . . . . . . . . . . . . . . . . . . 47 5.2 Average Size of Gomory Cutting Planes for Example 6 . . . . . . . . . 52 5.3 First Set of Gomory Cutting Planes . . . . . . . . . . . . . . . . . . . . 53 5.4 Second Set of Gomory Cutting Planes . . . . . . . . . . . . . . . . . . . 54 5.5 Third Set of Gomory Cutting Planes . . . . . . . . . . . . . . . . . . . 55 5.6 Fourth Set of Gomory Cutting Planes . . . . . . . . . . . . . . . . . . . 56 5.7 Results of CPLEX vs. Exact Code for Example . . . . . . . . . . . . . 57 5.8 Results of CPLEX vs. Exact Code for Example . . . . . . . . . . . . . 58 6.1 An example with multiple alternate optima . . . . . . . . . . . . . . . . 60 6.2 Graph after the (cid:12)rst Gomory cuts added with multiple alternate optima 62 6.3 Results with multiple alternate optima . . . . . . . . . . . . . . . . . . 63 7.1 Example with dropping . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 vi 7.2 Example with dropping . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 7.3 Example with dropping . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 7.4 Example with dropping . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 8.1 CPLEX Settings Table . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 8.2 CPLEX Settings Data Gathering . . . . . . . . . . . . . . . . . . . . . . 72 8.3 Results of CPLEX vs. Exact Code for GT2 . . . . . . . . . . . . . . . . 75 8.4 Results of CPLEX vs. Exact Code for MOD008 . . . . . . . . . . . . . 76 8.5 Results of CPLEX vs. Exact Code for BM23 . . . . . . . . . . . . . . . 76 8.6 Results of Weak Cuts for BM23 . . . . . . . . . . . . . . . . . . . . . . 77 8.7 Average Digits for Storage of Non-Zeros elements of Gomory cutting planes for problem BM23 with Cuto(cid:11) 300 . . . . . . . . . . . . . . . . . 78 8.8 Average Digits for Storage of Non-Zeros elements of Gomory cutting planes for problem BM23 with Cuto(cid:11) 100 . . . . . . . . . . . . . . . . . 78 8.9 Average Digits for Storage of Non-Zeros elements of Gomory cutting planes for problem BM23 with no Cuto(cid:11) . . . . . . . . . . . . . . . . . 79 8.10 Maximum size of the element of w-vector for problem BM23 . . . . . . 79 8.11 Maximum size of the element of w-vector for problem BM23 . . . . . . 80 8.12 Maximum size of the element of w-vector for problem BM23 . . . . . . 80 8.13 Results of CPLEX vs. Exact Code for P0033 . . . . . . . . . . . . . . . 81 8.14 Average Digits for Storage of Non-Zeros elements of Gomory cutting planes for problem P0033 . . . . . . . . . . . . . . . . . . . . . . . . . . 82 8.15 Average Digits for Storage of Non-Zeros elements of Gomory cutting planes for problem P0033 . . . . . . . . . . . . . . . . . . . . . . . . . . 82 8.16 Maximum size of the element of w-vector for problem P0033 . . . . . . 83 8.17 Maximum size of the element of w-vector for problem P0033 . . . . . . 83 8.18 Results of CPLEX vs. Exact Code for PIPEX . . . . . . . . . . . . . . 84 8.19 Results of CPLEX vs. Exact Code for LSEU . . . . . . . . . . . . . . . 85 8.20 Results of Weak Cuts for LSEU . . . . . . . . . . . . . . . . . . . . . . 85 vii 8.21 Average Digits for Storage of Non-Zeros elements of Gomory cutting planes for problem LSEU . . . . . . . . . . . . . . . . . . . . . . . . . . 86 8.22 Average Digits for Storage of Non-Zeros elements of Gomory cutting planes for problem LSEU . . . . . . . . . . . . . . . . . . . . . . . . . . 87 8.23 Average Digits for Storage of Non-Zeros elements of Gomory cutting planes for problem LSEU . . . . . . . . . . . . . . . . . . . . . . . . . . 87 8.24 Maximum size of the element of w-vector for problem LSEU . . . . . . 88 8.25 Maximum size of the element of w-vector for problem LSEU . . . . . . 88 8.26 Maximum size of the element of w-vector for problem LSEU . . . . . . 89 8.27 Results of CPLEX vs. Exact Code for P0201 . . . . . . . . . . . . . . . 90 8.28 Average Digits for Storage of Non-Zeros elements of Gomory cutting planes for problem P0201 . . . . . . . . . . . . . . . . . . . . . . . . . . 91 8.29 Maximum size of the element of w-vector for problem P0201 . . . . . . 91 8.30 Results of CPLEX vs. Exact Code for P0282 . . . . . . . . . . . . . . . 92 8.31 Average Digits for Storage of Non-Zeros elements of Gomory cutting planes for problem P0282 . . . . . . . . . . . . . . . . . . . . . . . . . . 92 8.32 Maximum size of the element of w-vector for problem P0282 . . . . . . 93 8.33 Results of CPLEX vs. Exact Code for P0291 . . . . . . . . . . . . . . . 93 8.34 Results of Weak Cuts for P0291 . . . . . . . . . . . . . . . . . . . . . . 94 8.35 Average Digits for Storage of Non-Zeros elements of Gomory cutting planes for problem P0291 . . . . . . . . . . . . . . . . . . . . . . . . . . 95 8.36 Average Digits for Storage of Non-Zeros elements of Gomory cutting planes for problem P0291 . . . . . . . . . . . . . . . . . . . . . . . . . . 95 8.37 Average Digits for Storage of Non-Zeros elements of Gomory cutting planes for problem P0291 . . . . . . . . . . . . . . . . . . . . . . . . . . 96 8.38 Maximum size of the element of w-vector for problem P0291 . . . . . . 96 8.39 Maximum size of the element of w-vector for problem P0291 . . . . . . 97 8.40 Maximum size of the element of w-vector for problem P0291 . . . . . . 97 8.41 Results of CPLEX vs. Exact Code for SENTOY . . . . . . . . . . . . . 98 8.42 Results of Weak Cuts for SENTOY . . . . . . . . . . . . . . . . . . . . 98 viii 8.43 Average Digits for Storage of Non-Zeros elements of Gomory cutting planes for problem SENTOY . . . . . . . . . . . . . . . . . . . . . . . . 99 8.44 Average Digits for Storage of Non-Zeros elements of Gomory cutting planes for problem SENTOY . . . . . . . . . . . . . . . . . . . . . . . . 99 8.45 Average Digits for Storage of Non-Zeros elements of Gomory cutting planes for problem SENTOY . . . . . . . . . . . . . . . . . . . . . . . . 100 8.46 Maximum size of the element of w-vector for problem SENTOY . . . . 100 8.47 Maximum size of the element of w-vector for problem SENTOY . . . . 101 8.48 Maximum size of the element of w-vector for problem SENTOY . . . . 101 ix