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.
Citation
NAM Preprint 2017-6, University of Goettingen, August 2017
Article
View Matroid Optimization Problems with Monotone Monomials in the Objective