Optimization Online


Cuts over Extended Formulations by Flow Discretization

Eduardo Uchoa(uchoa***at***producao.uff.br)

Abstract: Large-sized extended formulations have the potential for providing high-quality bounds on some combinatorial optimization problems where the natural formulations perform poorly. This chapter discusses the use of some families of cuts that have been recently applied on extended formulations that are obtained by the discretization of the continuous variables occurring in the natural formulation of the Fixed Charge Network Flow Problem. By interpreting the flows as being link capacities, loads or times, similar cuts can be used on problems like the Capacitated Minimum Spanning Tree, Vehicle Routing and Parallel-Machine Scheduling.

Keywords: Cutting planes, extended formulations

Category 1: Integer Programming

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: To appear as a chapter of "Progress in Combinatorial Optimization" (ISTE-Wiley)

Download: [PDF]

Entry Submitted: 08/31/2011
Entry Accepted: 08/31/2011
Entry Last Modified: 08/31/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society