Network & Cutting Plane Methods

ME25.1 withdrawn - author request of 9/1

• Sungsoo Park; KAIST, Dept. of IE, 373-1 Gusong-Dong Yusong-Gu, Taejon, , Korea; sspark@cais.kaist.ac.kr
• Kyungsik Lee; ;

ME25.2 withdrawn - chair request of 9/16

• Antoine Deza; Ecole des Hautes, Centre d'Analyse et de Math., 54 Boulevard Raspail, Paris, 75 006 , France; deza@ehess.fr
• David Avis; McGill University, Dept. of Comp. Sci., Montreal, Quebec, , Canada;

ME25.3 A Combinatorial Polynomial-Time Algorithm for Generalized Min Cost Flow

• Kevin Wayne; Princeton University; wayne@cs.princeton.edu

We develop the first combinatorial polynomial-time algorithm for the generalized min cost flow problem. Despite a rich history dating back to Dantzig, until now, all previous polynomial-time algorithms were based on general LP techniques. Our techniques also extend to optimize LPs with 2 variables per inequality.

ME25.4 Polyhedral Methods for Piecewise-Linear Functions

• Dan Wilson; University of Kentucky, c/o Jon Lee Math. Dept., Patterson Office Tower, Lexington, KY 40506; jlee@ms.uky.edu
• Jon Lee; University of Kentucky, Dept. of Math., Patterson Office Tower, Lexington, KY 40506-0027; jlee@ms.uky.edu

We formulate nonseparable piecewise-linear functions using methods of integer LP. Our formulations generalize the well-know lambda and delta methods. We use strong cutting-plane and reformulation techniques to make our methods practical. We present computational results obtained using AMPL.

ME25.5 The p-Cycle Polytope

• Mark Hartmann; University of North Carolina, Dept. of OR CB 3180, 210 Smith Bldg., Chapel Hill, NC 27599-3180; mudville@or.unc.edu
• Ozgur Ozluk; University of North Carolina, OR Dept., Smith Bldg., CB 3180, Chapel Hill, NC 27599-3180;

The p-cycle polytope is the convex hull of incidence vectors of directed cycles with p nodes (the p-node ATSP polytope is a face). We give the equality set, dimension and facet-defining inequalities for 2