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

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