On computing small variable disjunction branch-and-bound trees

• 成果类型: Article
• 署名作者: Glaeser, Max; Pfetsch, Marc E.
• 署名单位: Technical University of Darmstadt
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-01968-y
• 发表日期: 2024
• 页码: 145-173
• 关键词: Complexity; approximation; RESOLUTION

摘要

This article investigates smallest branch-and-bound trees and their computation. We first revisit the notion of hiding sets to deduce lower bounds on the size of branch-and bound trees for certain binary programs, using both variable disjunctions and general disjunctions. We then provide exponential lower bounds for variable disjunctions by a disjoint composition of smaller binary programs. Moreover, we investigate the complexity of finding small branch-and-bound trees using variable disjunctions: We show that it is not possible to approximate the size of a smallest branch-and-bound tree within a factor of 2 (5)/(1n) in time O(2(dn)) with 8 < (5)/(1), unless the strong exponential time hypothesis fails. Similarly, for any e > 0, no polynomial time 2((2)/(1) -(e))(n)-approximation is possible, unless P = NP. We also show that computing the size of a smallest branch and-bound tree exactly is #P-hard. Similar results hold for estimating the size of the tree produced by branching rules like most-infeasible branching. Finally, we discuss that finding small branch-and-bound trees generalizes finding short treelike resolution refutations, and thus non-automatizability results transfer from this setting.