A polyhedral study of the generalized vertex packing problem

Hanif D. Sherali, J. Cole Smith

Research output: Contribution to journalArticle

7 Scopus citations

Abstract

The traditional vertex packing problem defined on an undirected graph identifies the largest weighted independent set of nodes, that is, a set of nodes whose induced subgraph contains no edges. In this paper, we examine a generalized vertex packing problem (GVP-k) in which k ''violations'' to the independent set restriction are permitted, whereby k edges may exist within the subgraph induced by the chosen set of nodes. A particular context in which such problems arise is in the national airspace planning model of Sherali, Smith, and Trani (2000), where a set of flight-plans need to be composed for various flights subject to conflict, workload, and equity considerations. The GVP-k structure arises in modeling the air-traffic control sector workload restrictions, which stipulate that for each sector and during each discretized time-slot, the number of aircraft conflicts that would need to be resolved should not exceed k, for some k 1. We derive several classes of facetial valid inequalities for GVP-k for certain specially structured subgraphs, identifying polynomial-sized convex hull representations for some of these cases. Related constraint generation routines are also developed, and some computational results are provided to demonstrate the efficacy of utilizing the proposed valid inequalities in solving GVP-k for different values of k.

Original languageEnglish (US)
Pages (from-to)367-390
Number of pages24
JournalMathematical Programming
Volume107
Issue number3
DOIs
StatePublished - Jul 1 2006
Externally publishedYes

Keywords

  • Air-space management
  • Integer programming
  • Reformulation-linearization technique
  • Valid inequalities/cutting planes
  • Vertex packing

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'A polyhedral study of the generalized vertex packing problem'. Together they form a unique fingerprint.

  • Cite this