Optimization Online


Path Cover and Path Pack Inequalities for the Capacitated Fixed-Charge Network Flow Problem

Alper Atamturk(atamturk***at***berkeley.edu)
Birce Tezel(btezel***at***berkeley.edu)
Kucukyavuz Simge(simge***at***uw.edu)

Abstract: Capacitated fixed-charge network flows are used to model a variety of problems in telecommunication, facility location, production planning and supply chain management. In this paper, we investigate capacitated path substructures and derive strong and easy-to-compute path cover and path pack inequalities. These inequalities are based on an explicit characterization of the submodular inequalities through a fast computation of parametric minimum cuts on a path, and they generalize the well-known flow cover and flow pack inequalities for the single-node relaxations of fixed-charge flow models. We provide necessary and sufficient facet conditions. Computational results demonstrate the effectiveness of the inequalities when used as cuts in a branch-and-cut algorithm.

Keywords: Submodularity, covers, packs, paths

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Integer Programming (Cutting Plane Approaches )

Citation: BCOL Research Report 15.03, IEOR, UC Berkeley

Download: [PDF]

Entry Submitted: 11/12/2016
Entry Accepted: 11/13/2016
Entry Last Modified: 11/12/2016

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