Implicit cover inequalities |
| |
Authors: | Agostinho Agra Cristina Requejo Eulália Santos |
| |
Institution: | 1.CIDMA and Department of Mathematics,University of Aveiro,Aveiro,Portugal;2.CIDMA,ISLA-Higher Institute of Leiria,Leiria,Portugal |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|