Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/16491
Title: Implicit cover inequalities
Author: Agra, Agostinho
Requejo, Cristina
Santos, Eulália
Keywords: Cover inequalities
Weighted minimal spanning tree problem
Lifting
Matroidal knapsack
Issue Date: Apr-2016
Publisher: Springer Verlag
Abstract: In this paper we consider combinatorial optimization problems whose feasible sets are simultaneously restricted by a binary knapsack constraint and a cardinality constraint imposing the exact number of selected variables. In particular, such sets arise when the feasible set corresponds to the bases of a matroid with a side knapsack constraint, for instance the weighted spanning tree problem and the multiple choice knapsack problem. We introduce the family of implicit cover inequalities which generalize the well-known cover inequalities for such feasible sets and discuss the lifting of the implicit cover inequalities. A computational study for the weighted spanning tree problem is reported.
Peer review: yes
URI: http://hdl.handle.net/10773/16491
DOI: 10.1007/s10878-014-9812-3
ISSN: 1382-6905
Appears in Collections:CIDMA - Artigos
OGTCG - Artigos

Files in This Item:
File Description SizeFormat 
art%3A10.1007%2Fs10878-014-9812-3.pdfdocumento principal506.47 kBAdobe PDF    Request a copy


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.