## Integer Programming and Combinatorial Optimization: 10th International IPCO Conference, New York, NY, USA, June 7-11, 2004, Proceedings, Volume 10This volume contains the papers accepted for publication at IPCO X, the Tenth InternationalConferenceonInteger ProgrammingandCombinatorialOptimi- tion, held in New York City, New York, USA, June 7–11, 2004.The IPCO series of conferences presents recent results in theory, computation and applications of integer programming and combinatorial optimization. These conferences are sponsoredby the Mathematical ProgrammingSociety, andareheldin thoseyearsin whichno InternationalSymposiumonMathema- calProgrammingtakes place.IPCO VIII was held in Utrecht (The Netherlands) and IPCO IX was held in Cambridge (USA). A total of 109 abstracts, mostly of very high quality, were submitted. The ProgramCommittee accepted 32, in order to meet the goal of having three days of talks with no parallel sessions. Thus, many excellent abstracts could not be accepted. The papers in this volume havenot been refereed. It is expected that revised versions of the accepted papers will be submitted to standard scienti?c journals for publication. The Program Committee thanks all authors of submitted manuscripts for their support of IPCO. March 2004 George Nemhauser Daniel Bienstock Organization IPCO X was hosted by the Computational Optimization Research Center (CORC), Columbia University. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Robust BranchandCutandPrice for the Capacitated Vehicle Routing Problem | 1 |

Metric Inequalities and the Network Loading Problem | 16 |

Valid Inequalities Based on Simple MixedInteger Sets | 33 |

The Price of Anarchy when Costs Are Nonseparable and Asymmetric | 46 |

Computational Complexity Fairness and the Price of Anarchy of the Maximum Latency Problem | 59 |

Polynomial Time Algorithm for Determining Optimal Strategies in Cyclic Games | 74 |

A Robust Optimization Approach to Supply Chain Management | 86 |

Approximation Algorithms for Stochastic Optimization Problems | 101 |

Separable Concave Optimization Approximately Equals Piecewise Linear Optimization | 234 |

Three Kinds of Integer Programming Algorithms Based on Barvinoks Rational Functions | 244 |

The PathPacking Structure of Graphs | 256 |

More on a BinaryEncoded Coloring Formulation | 271 |

Single Machine Scheduling with Precedence Constraints | 283 |

The Constrained Minimum Weighted Sum of Job Completion Times Problem | 298 |

NearOptimum Global Routing with Coupling Delay Bounds and Power Consumption | 308 |

A FlowBased Method for Improving the Expansion or Conductance of Graph Cuts | 325 |

Scheduling an Industrial Production Facility | 116 |

Three MinMax Theorems Concerning Cyclic Orders of Strong Digraphs | 132 |

A TDI Description of Restricted 2Matching Polytopes | 139 |

Enumerating Minimal Dicuts and Strongly Connected Subgraphs and Related Geometric Problems | 152 |

Semicontinuous Cuts for MixedInteger Programming | 163 |

Combinatorial Benders Cuts | 178 |

A Faster Exact Separation Algorithm for Blossom Inequalities | 196 |

LPbased Approximation Algorithms for Capacitated Facility Location | 206 |

A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem | 219 |

All Rational Polytopes Are Transportation Polytopes and All Polytopal Integer Sets Are Contingency Tables | 338 |

A Capacity Scaling Algorithm for Mconvex Submodular Flow | 352 |

Integer Concave Cocirculations and Honeycombs | 368 |

Minsquare Factors and Maxﬁx Covers of Graphs | 388 |

LowDimensional Faces of Random 01Polytopes | 401 |

On Polyhedra Related to Even Factors | 416 |

Optimizing over Semimetric Polytopes | 431 |

444 | |

### Other editions - View all

### Common terms and phrases

acyclic approximation algorithms arcs assigned binary branch-and-cut capacitated capacitated facility location capacity client cluster Combinatorial Optimization components compute concave cocirculation consider contains convex corresponding cost Cplex cut-tree cycle decomposition deﬁne defined demand denote digraph directed graph Discrete edges exists facility location problem feasible solution ﬁrst flow problem formulation fractional given graph G heuristic honeycomb implies instances integer program IPCO Lemma linear programming lower bound LP relaxation M-convex Math matrix maximal maximum latency Metric Inequalities min-max minimal minimum mixed-integer multicommodity Nash equilibrium Nemhauser Eds nodes NP-hard objective function obtained Operations Research optimal solution partition path polyhedral polyhedron polynomial polytope precedence constraints Proof prove ratio satisﬁes scenario schedule Section semi-continuous solve Steiner trees stochastic strongly connected subgraph subset supernode symmetric T-partition Theorem tight tree upper bound variables vector vertex set vertices weight