Matroid optimization problems with monotone monomials in the objective

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 hiera…

Counting degree sequences of spanning trees in bipartite graphs: A graph‐theoretic proof

Decorous combinatorial lower bounds for row layout problems

Abstract In this paper we consider the Double-Row Facility Layout Problem (DRFLP). Given a set of departments and pairwise transport weights between them the DRFLP asks for a non-overlapping arrangement of the departments along both sides of a common path such that the weighted sum of the center-to-center distances between the departments is minimized. Despite its broad applicability in factory planning, only small instances can be solved to optimality in reasonable time. Apart from this even deriving good lower bounds using existing integer programming formulations and branch-and-cut methods is a challenging problem. We focus here on deriving combinatorial lower bounds which can be compute…

Data for: Decorous Combinatorial Lower Bounds for Row Layout Problems

Files of the new randomly generated instancesnlengths of the departmentsmatrix with the transport weights THIS DATASET IS ARCHIVED AT DANS/EASY, BUT NOT ACCESSIBLE HERE. TO VIEW A LIST OF FILES AND ACCESS THE FILES IN THIS DATASET CLICK ON THE DOI-LINK ABOVE