Optimization Online


Computational experience with general cutting planes for the Set Covering problem

Pasquale Avella(avella***at***unisannio.it)
Maurizio Boccia(maurizio.boccia***at***unisannio.it)
Igor Vasiliev(vasilievigor***at***gmail.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 )


Download: [PDF]

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

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 Programming Society