S. Thomas McCormick

Matroid Optimization Problems with Monotone Monomials in the Objective

  • Anja Fischer
  • Frank Fischer
  • S. Thomas McCormick
    • Categories 0-1 Programming, Graphs and Matroids, Polyhedra Tags , , , ,

    In this paper we investigate non-linear matroid optimization problems with polynomial objective functions where the monomials satisfy certain monotonicity properties. Indeed, we study problems where the set of non-linear monomials consists of all non-linear monomials that can be built from a given subset of the variables. Linearizing all non-linear monomials we study the respective polytope. … Read more

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

  • Anja Fischer
  • Frank Fischer
  • S. Thomas McCormick
    • Categories 0-1 Programming, Graphs and Matroids, Polyhedra Tags , , , , ,

    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 … Read more