|
|||||
|
|
Extended formulations for the cardinality constrained subtree of a tree problem |
|
| Authors: | A Agra L Gouveia C Requejo |
| Institution: | a DMat and CEOC, University of Aveiro, Campus Universitário de Santiago 3810-193 Aveiro, Portugal b DEIO and CIO, Faculdade de Ciências, Universidade de Lisboa, Campo Grande, Edifício C6 - 4° piso, 1749-016 Lisboa, Portugal |
| Abstract: | Given a tree with n nodes, we consider the problem of finding the most profitable subtree of that tree with at most K nodes which is known as the Cardinality Subtree of a Tree Problem. We present a new exact linear extended formulation with O(nK) two-indexed variables and O(nK) constraints. |
| Keywords: | Subtree of a tree Cardinality constraint Extended formulations Ordering variables |
| 本文献已被 ScienceDirect 等数据库收录！ | |