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.
Citation
To appear as a chapter of "Progress in Combinatorial Optimization" (ISTE-Wiley)