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.