-

 

 

 




Optimization Online





 

Polyhedral investigations on stable multi-sets

Arie M.C.A. Koster (koster***at***zib.de)
Adrian Zymolka (zymolka***at***zib.de)

Abstract:

Stable multi-sets are an evident generalization of the well-known stable sets. As integer programs, they constitute a general structure which allows for a wide applicability of the results. Moreover, the study of stable multi-sets provides new insights to well-known properties of stable sets. In this paper, we continue our investigations started in Koster and Zymolka (2002) and present results of three types: on the relation to other combinatorial problems, on the polyhedral structure of the stable multi-set polytope, and on the computational impact of the polyhedral results.

First of all, we embed stable multi-sets in a framework of generalized set packing problems and point out several relations. The second part discusses properties of the stable multi-set polytope. We show that the vertices of the linear relaxation are half integer and have a special structure. Moreover, we strengthen the conditions for cycle inequalities to be facet defining, show that the separation problem for these inequalities is polynomial time solvable, and discuss the impact of chords in cycles. The last result allows to interpret cliques as cycles with many chords.

The paper is completed with a computational study to the practical importance of the cycle inequalities. The computations show that the performance of state-of-the-art integer programming solvers can be improved significantly by including these inequalities.

Keywords: stable multi-sets, set packing, polyhedral combinatorics

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Category 3: Combinatorial Optimization (Graphs and Matroids )

Citation: ZIB-Report 03-10, Konrad-Zuse-Zentrum für Informationstechnik Berlin (

Download: [Postscript][PDF]

Entry Submitted: 08/04/2003
Entry Accepted: 08/04/2003
Entry Last Modified: 08/04/2003

Modify/Update this entry


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

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society