Computational experience with general cutting planes for the Set Covering problem

Pasquale Avella(avellaunisannio.it)
Maurizio Boccia(maurizio.bocciaunisannio.it)
Igor Vasiliev(vasilievigorgmail.com)

Abstract: In this paper we present a cutting plane algorithm for the Set Covering problem. Cutting planes are generated by a "general" (i.e. not based on the "template paradigm") separation algorithm based on the following idea: i) identify a suitably small subproblem defined by a subset of the constraints of the formulation; ii) run an exact separation algorithm over the subproblem to produce a violated cutting plane, if any exists. Computational results on difficult small-medium size instances are reported.

Keywords: Cutting Planes, Set Covering

Category 1: Integer Programming (0-1 Programming )

Citation:

Download: [PDF]

Entry Submitted: 09/02/2007
Entry Accepted: 09/02/2007
Entry Last Modified: 09/02/2007

Modify/Update this entry