Implicit cover inequalities
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...
| Main Author: | |
|---|---|
| Other Authors: | , |
| Format: | article |
| Language: | eng |
| Published: |
2016
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10773/16491 |
| Country: | Portugal |
| Oai: | oai:ria.ua.pt:10773/16491 |
| Summary: | 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. |
|---|