matroids

Convex optimization under combinatorial sparsity constraints

  • Christoph Buchheim
  • Emiliano Traversi
    • Categories Graphs and Matroids, Linear, Cone and Semidefinite Programming Tags , , ,

    We present a heuristic approach for convex optimization problems containing sparsity constraints. The latter can be cardinality constraints, but our approach also covers more complex constraints on the support of the solution. For the special case that the support is required to belong to a matroid, we propose an exchange heuristic adapting the support in … Read more

    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