Recently, Buchheim and Klein 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. The monomials are linearised and we study the corresponding polytope with the aim to better understand the structure of polytopes arising from such linearisations and to provide strengthened cutting planes as well as separation algorithms for linearisations of matroid optimisation problems with general polynomial objective function. Extending results by Edmonds 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.
Citation
NAM Preprint 2016-2, Institute for Numerical and Applied Mathematics, University of Goettingen, March 2016
Article
View Matroid Optimisation Problems with Nested Non-linear Monomials in the Objective Function