I LINEAR PROGRAMMING, THE SIMPLEX ALGORITHM, AND EXACT
SOLUTIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Why Exact Solutions? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 Binary Floating Point Representation . . . . . . . . . . . . . . . . . 4
1.2.2 The Limits and Errors of Floating Point Arithmetic . . . . . . . . . 8
1.2.3 Why Floating Point representation is used at all? . . . . . . . . . . 9
1.2.4 What is an Exact Solution? . . . . . . . . . . . . . . . . . . . . . . 10
1.2.5 When do we need exact LP solutions? . . . . . . . . . . . . . . . . 13
1.2.6 Previously known results . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3 Getting Exact LP Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3.1 Selecting the Right Tools . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3.2 A Ørst Naƒ³ve Approach . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3.3 Is Everything Lost? . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.3.4 Working with Floating Point with Dynamic Precision . . . . . . . . 21
1.4 Some Applications and Numerical Results . . . . . . . . . . . . . . . . . . 29
1.4.1 Orthogonal Arrays with Mixed Levels . . . . . . . . . . . . . . . . . 29
1.4.2 The NETLIB, MIPLIB and other instances . . . . . . . . . . . . . 32
1.4.3 TSP-related Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
1.5 Final Comments and Missing Links . . . . . . . . . . . . . . . . . . . . . . 43
1.5.1 Shortcomings and Possible Improvements . . . . . . . . . . . . . . . 43
1.5.2 Final Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
II MIXED INTEGER PROBLEMS AND LOCAL CUTS . . . . . . . . . 49
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.2 The Separation Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.2.1 Facet Description of MIPs . . . . . . . . . . . . . . . . . . . . . . . 52
2.2.2 The Optimization Oracle and the Separation Problem . . . . . . . 55
2.2.3 On the Polynomiality and Finiteness of the Separation Algorithm . 59
2.3 Obtaining high-dimensional Faces . . . . . . . . . . . . . . . . . . . . . . . 61
2.3.1 An Algorithmic Approach . . . . . . . . . . . . . . . . . . . . . . . 62
2.3.2 Solving the Tilting Problem . . . . . . . . . . . . . . . . . . . . . . 67
2.3.3 More on the Facet Procedure . . . . . . . . . . . . . . . . . . . . . 74
2.4 Looking for Easier Problems: The Mapping Problem . . . . . . . . . . . . 77
2.4.1 Taking Advantage of the so-called Combinatorial Explosion . . . . 78
2.4.2 Mappings with Guarantees . . . . . . . . . . . . . . . . . . . . . . . 80
2.4.3 Final notes on mappings . . . . . . . . . . . . . . . . . . . . . . . . 84
2.5 Putting it all Together . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
2.5.1 The Melting Pot . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
2.5.2 The Local Cut Procedure (v0.1) . . . . . . . . . . . . . . . . . . . . 85
2.5.3 The Dark Corners of Local Cuts . . . . . . . . . . . . . . . . . . . . 87
2.6 Choosing Relevant Mappings . . . . . . . . . . . . . . . . . . . . . . . . . . 90
2.6.1 Problem Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
2.6.2 Simple Local Cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
2.6.3 Integer Local Cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
2.6.4 Gomory-Projected Local Cuts . . . . . . . . . . . . . . . . . . . . . 93
2.6.5 Minimal Projection Local Cuts . . . . . . . . . . . . . . . . . . . . 94
2.6.6 2-Tableau and 4-Tableau Local Cuts . . . . . . . . . . . . . . . . . 96
2.7 Computational Experience . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
2.7.1 The Branch and Cut Solver . . . . . . . . . . . . . . . . . . . . . . 100
2.7.2 Choosing The Default Settings . . . . . . . . . . . . . . . . . . . . . 102
2.7.3 Comparing the default settings against Local Cuts . . . . . . . . . 107
2.8 Final Thoughts on Local Cuts . . . . . . . . . . . . . . . . . . . . . . . . . 110
III THE TSP PROBLEM AND THE DOMINO PARITY INEQUALITIES112
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
3.2 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
3.3 DP Inequalities and Letchford's Algorithm . . . . . . . . . . . . . . . . . . 116
3.3.1 Building Dominoes . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
3.3.2 The Odd-Cycle Problem . . . . . . . . . . . . . . . . . . . . . . . . 120
3.3.3 Generating More Inequalities . . . . . . . . . . . . . . . . . . . . . 121
3.3.4 Putting it All Together . . . . . . . . . . . . . . . . . . . . . . . . . 124
3.4 Shrinking and Non-Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . 124
3.4.1 Safe Shrinking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
3.4.2 Domino Transformations . . . . . . . . . . . . . . . . . . . . . . . . 126
3.4.3 Proof of Safe-Shrinking Conditions for DP-inequalities . . . . . . . 129
3.5 Finding a Planar Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
3.5.1 Edge-Elimination Planarization . . . . . . . . . . . . . . . . . . . . 135
3.6 Tightening DP Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
3.7 Computational Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
3.7.1 Solution of D18512 and PLA33810 . . . . . . . . . . . . . . . . . . 141
3.7.2 Final Comments on our Computational Tests . . . . . . . . . . . . 142
APPENDIX A | RUNNING TIMES FOR QSOPT EX COMPARED
AGAINST QSOPT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
REFERENCES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163

[此贴子已经被作者于2007-6-7 7:52:07编辑过]