6533b831fe1ef96bd12982d0

RESEARCH PRODUCT

Matroid optimization problems with monotone monomials in the objective

S. Thomas MccormickFrank FischerAnja Fischer

subject

PolynomialMonomialOptimization problemRank (linear algebra)Applied Mathematics0211 other engineering and technologies021107 urban & regional planningPolytopeMonotonic function0102 computer and information sciences02 engineering and technology01 natural sciencesMatroidCombinatoricsMonotone polygon010201 computation theory & mathematicsComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATIONDiscrete Mathematics and CombinatoricsMathematics

description

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. This hierarchy allows to strengthen the relaxations of arbitrary linearized combinatorial optimization problems with polynomial objective functions and matroidal substructures. Finally, we give suggestions for future work.

yearjournalcountryeditionlanguage
2022-02-01Discrete Applied Mathematics
https://doi.org/10.1016/j.dam.2020.04.004