Optimization Online


Matroid Optimisation Problems with Nested Non-linear Monomials in the Objective Function

Anja Fischer(anja.fischer***at***mathematik.uni-goettingen.de)
Frank Fischer(frank.fischer***at***uni-kassel.de)
S. Thomas McCormick(tom.mccormick***at***sauder.ubc.ca)

Abstract: 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.

Keywords: polyhedral combinatorics, matroid, matroid polytope, linearisation, polynomial optimisation, separation

Category 1: Combinatorial Optimization (Graphs and Matroids )

Category 2: Combinatorial Optimization (Polyhedra )

Category 3: Integer Programming (0-1 Programming )

Citation: NAM Preprint 2016-2, Institute for Numerical and Applied Mathematics, University of Goettingen, March 2016

Download: [PDF]

Entry Submitted: 03/21/2016
Entry Accepted: 03/21/2016
Entry Last Modified: 03/21/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society