Integer Programming and Combinatorial Optimization: 10th International IPCO Conference, New York, NY, USA, June 7-11, 2004. Proceedings

Daniel Bienstock (ed.), George Nemhauser (ed.)3540221131, 9783540221135, 9783540259602

This book constitutes the refereed proceedings of the 10th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2004, held in New York City, USA in June 2004.

The 32 revised papers presented were carefully reviewed and selected from 109 submissions. Among the topics addressed are vehicle routing, network management, mixed-integer programming, computational complexity, game theory, supply chain management, stochastic optimization problems, production scheduling, graph computations, computational graph theory, separation algorithms, local search, linear optimization, integer programming, graph coloring, packing, combinatorial optimization, routing, flow algorithms, 0/1 polytopes, and polyhedra.

---

Table of contents :
Front Matter….Pages –
Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem….Pages 1-15
Metric Inequalities and the Network Loading Problem….Pages 16-32
Valid Inequalities Based on Simple Mixed-Integer Sets….Pages 33-45
The Price of Anarchy when Costs Are Non-separable and Asymmetric….Pages 46-58
Computational Complexity, Fairness, and the Price of Anarchy of the Maximum Latency Problem….Pages 59-73
Polynomial Time Algorithm for Determining Optimal Strategies in Cyclic Games….Pages 74-85
A Robust Optimization Approach to Supply Chain Management….Pages 86-100
Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization Problems….Pages 101-115
Scheduling an Industrial Production Facility….Pages 116-131
Three Min-Max Theorems Concerning Cyclic Orders of Strong Digraphs….Pages 132-138
A TDI Description of Restricted 2-Matching Polytopes….Pages 139-151
Enumerating Minimal Dicuts and Strongly Connected Subgraphs and Related Geometric Problems….Pages 152-162
Semi-continuous Cuts for Mixed-Integer Programming….Pages 163-177
Combinatorial Benders’ Cuts….Pages 178-195
A Faster Exact Separation Algorithm for Blossom Inequalities….Pages 196-205
LP-based Approximation Algorithms for Capacitated Facility Location….Pages 206-218
A Multi-exchange Local Search Algorithm for the Capacitated Facility Location Problem….Pages 219-233
Separable Concave Optimization Approximately Equals Piecewise Linear Optimization….Pages 234-243
Three Kinds of Integer Programming Algorithms Based on Barvinok’s Rational Functions….Pages 244-255
The Path-Packing Structure of Graphs….Pages 256-270
More on a Binary-Encoded Coloring Formulation….Pages 271-282
Single Machine Scheduling with Precedence Constraints….Pages 283-297
The Constrained Minimum Weighted Sum of Job Completion Times Problem….Pages 298-307
Near-Optimum Global Routing with Coupling, Delay Bounds, and Power Consumption….Pages 308-324
A Flow-Based Method for Improving the Expansion or Conductance of Graph Cuts….Pages 325-337
All Rational Polytopes Are Transportation Polytopes and All Polytopal Integer Sets Are Contingency Tables….Pages 338-351
A Capacity Scaling Algorithm for M-convex Submodular Flow….Pages 352-367
Integer Concave Cocirculations and Honeycombs….Pages 368-387
Minsquare Factors and Maxfix Covers of Graphs….Pages 388-400
Low-Dimensional Faces of Random 0/1-Polytopes….Pages 401-415
On Polyhedra Related to Even Factors….Pages 416-430
Optimizing over Semimetric Polytopes….Pages 431-443
Back Matter….Pages –