Refine
Year of publication
Document Type
- ZIB-Report (9)
- Article (7)
- Other (2)
- Book (1)
- Doctoral Thesis (1)
Language
- English (20)
Is part of the Bibliography
- no (20)
Keywords
- facets (2)
- integer programming (2)
- Cardinality Constraints (1)
- Cardinality Forcing Inequalities (1)
- Cardinality constraints (1)
- Combinatorial Optimization (1)
- Kardinalitätsbeschränkung (1)
- Matroid Polytope (1)
- Matroid-Polytop (1)
- Matroids (1)
Institute
\noindent We give a partial description of the $(s,t)-p$-path polytope of a directed graph $D$ which is the convex hull of the incidence vectors of simple directed $(s,t)$-paths in $D$ of length $p$. First, we point out how the $(s,t)-p$-path polytope is located in the family of path and cycle polyhedra. Next, we give some classes of valid inequalities which are very similar to inequalities which are valid for the $p$-cycle polytope, that is, the convex hull of the incidence vectors of simple cycles of length $p$ in $D$. We give necessary and sufficient conditions for these inequalities to be facet defining. Furthermore, we consider a class of inequalities that has been identifie d to be valid for $(s,t)$-paths of cardinality at most $p$. Finally, we transfer the results to related polytopes, in particular, the undirected counterpart of the $(s,t)-p$-path polytope.
We consider polytopes associated with cardinality constrained path and cycle problems defined on a directed or undirected graph. We present integer characterizations of these polytopes by facet defining linear inequalities for which the separation problem can be solved in polynomial time. Moreover, we give further facet defining inequalities, in particular those that are specific to odd/even paths and cycles.
Given a combinatorial optimization problem and a subset $N$ of natural numbers, we obtain a cardinality constrained version of this problem by permitting only those feasible solutions whose cardinalities are elements of $N$. In this paper we briefly touch on questions that addresses common grounds and differences of the complexity of a combinatorial optimization problem and its cardinality constrained version. Afterwards we focus on polytopes associated with cardinality constrained combinatorial optimization problems. Given an integer programming formulation for a combinatorial optimization problem, by essentially adding Grötschel's cardinality forcing inequalities, we obtain an integer programming formulation for its cardinality restricted version. Since the cardinality forcing inequalities in their original form are mostly not facet defining for the associated polyhedra, we discuss possibilities to strengthen them.
Edmonds showed that the so-called rank inequalities and the nonnegativity constraints provide a complete linear description of the matroid polytope. By essentially adding Grötschel's cardinality forcing inequalities, we obtain a complete linear description of the cardinality constrained matroid polytope which is the convex hull of the incidence vectors of those independent sets that have a feasible cardinality. Moreover, we show how the separation problem for the cardinality forcing inequalities can be reduced to that for the rank inequalities. We also give necessary and sufficient conditions for a cardinality forcing inequality to be facet defining.
The steel mill slab design problem from the CSPLib is a binpacking problem that is motivated by an application of the steel industry and that has been widely studied in the constraint programming community. Recently, several people proposed new models and methods to solve this problem. A steel mill slab library was created which contains 380 instances. A closely related binpacking problem called multiple knapsack problem with color constraints, originated from the same industrial problem, were discussed in the integer programming community. In particular, a simple integer programming for this problem has been given by Forrest et al. [3]. The aim of this paper is to bring these different studies together. Moreover, we adopt the model of [3] for the steel mill slab problem. Using a state of the art integer program solver, this model is capable to solve all instances of the steel mill slab library, mostly in less than one second, to optimality. We improved, thereby, the solution value of 76 instances.