Utilize este identificador para referenciar este registo:
http://hdl.handle.net/10773/16491
Título: | Implicit cover inequalities |
Autor: | Agra, Agostinho Requejo, Cristina Santos, Eulália |
Palavras-chave: | Cover inequalities Weighted minimal spanning tree problem Lifting Matroidal knapsack |
Data: | Abr-2016 |
Editora: | Springer Verlag |
Resumo: | 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 |
Aparece nas coleções: | CIDMA - Artigos OGTCG - Artigos |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
art%3A10.1007%2Fs10878-014-9812-3.pdf | documento principal | 506.47 kB | Adobe PDF |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.