-

 

 

 




Optimization Online





 

Matroid Optimization Problems with Monotone Monomials in the Objective

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: 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. We present a complete description of this polytope. Apart from linearization constraints one needs appropriately strengthened rank inequalities. The separation problem for these inequalities reduces to a submodular function minimization problem. These polyhedral results give rise to a new hierarchy for the solution of matroid optimization problems with polynomial objectives. Finally, we consider extensions of our results and give suggestions for future work.

Keywords: Polynomial 0-1 Programming, Polyhedral Combinatorics, Matroids, Complete Description, Hierarchy

Category 1: Combinatorial Optimization (Graphs and Matroids )

Category 2: Combinatorial Optimization (Polyhedra )

Category 3: Integer Programming (0-1 Programming )

Citation: NAM Preprint 2017-6, University of Goettingen, August 2017

Download: [PDF]

Entry Submitted: 08/24/2017
Entry Accepted: 08/24/2017
Entry Last Modified: 08/24/2017

Modify/Update this entry


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

 

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