Matroid optimisation problems with nested non-linear monomials in the objective function

• 成果类型: Article
• 署名作者: Fischer, Anja; Fischer, Frank; McCormick, S. Thomas
• 署名单位: University of Gottingen; Universitat Kassel; University of British Columbia
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1140-9
• 发表日期: 2018
• 页码: 417-446
• 关键词: quadratic-term; programming-problems; reduction; polytope

摘要

Recently, Buchheim and Klein (Discrete Appl Math 177:34-52, 2014) suggested to study polynomial-time solvable optimisation problems with linear objective functions combined with exactly one additional quadratic monomial. They concentrated on special quadratic spanning tree or forest problems. We extend their results to general matroid optimisation problems with a set of nested monomials in the objective function. We study polytopes arising from the standard linearisation of the monomials. Our results provide insight on the polyhedral structure of matroid optimisation problems with arbitrary polynomial objective function, with a focus on separation algorithms and strengthened cutting planes. Extending results by Edmonds (Comb Struct Appl, 69-87, 1970) for the matroid polytope we present a complete description for the linearised polytope. Indeed, apart from the standard linearisation one needs appropriately strengthened rank inequalities satisfying certain non-separability conditions. The separation problem of these extended rank inequalities reduces to a submodular function minimisation problem. In the case of exactly one additional non-linear monomial we completely characterise the facetial structure of the associated polytope.