@article{KaibelStephan2010, author = {Kaibel, Volker and Stephan, R{\"u}diger}, title = {On cardinality constrained cycle and path polytopes}, volume = {123}, journal = {Math. Program.}, number = {2 (A)}, doi = {10.1007/s10107-008-0257-2}, pages = {371 -- 394}, year = {2010}, language = {en} } @article{Stephan2009, author = {Stephan, R{\"u}diger}, title = {Facets of the (s,t)-p-path polytope}, volume = {157}, journal = {Discrete Appl. Math.}, number = {14}, doi = {10.1016/j.dam.2009.06.003}, pages = {3119 -- 3132}, year = {2009}, language = {en} } @article{BalasStephan2009, author = {Balas, Egon and Stephan, R{\"u}diger}, title = {On the cycle polytope of a directed graph and its relaxations}, volume = {54}, journal = {Networks}, number = {1}, doi = {10.1002/net.20303}, pages = {47 -- 55}, year = {2009}, language = {en} } @misc{MaurrasStephan2009, author = {Maurras, Jean and Stephan, R{\"u}diger}, title = {On the cardinality constrained matroid polytope}, year = {2009}, language = {en} } @book{Stephan2005, author = {Stephan, R{\"u}diger}, title = {Polytopes associated with length restricted directed circuits}, publisher = {diploma thesis, Technische Universit{\"a}t Berlin}, year = {2005}, language = {en} } @misc{GroetschelStephan2012, author = {Gr{\"o}tschel, Martin and Stephan, R{\"u}diger}, title = {Characterization of Facets of the Hop Constrained Chain Polytope via Dynamic Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14914}, year = {2012}, abstract = {In this paper, we study the hop constrained chain polytope, that is, the convex hull of the incidence vectors of (s,t)-chains using at most k arcs of a given digraph, and its dominant. We use extended formulations (implied by the inherent structure of the Moore-Bellman-Ford algorithm) to derive facet defining inequalities for these polyhedra via projection. Our findings result into characterizations of all facet defining {0,+1,-1}-inequalities for the hop constrained chain polytope and all facet defining {0,1}-inequalities for its dominant. Although the derived inequalities are already known, such classifications were not previously given to the best of our knowledge. Moreover, we use this approach to generalize so called jump inequalities, which have been introduced in a paper of Dahl and Gouveia in 2004.}, language = {en} } @misc{Stephan2008, author = {Stephan, R{\"u}diger}, title = {On the cardinality constrained matroid polytope}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10614}, number = {08-08}, year = {2008}, abstract = {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{\"o}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.}, language = {en} } @misc{KaibelStephan2007, author = {Kaibel, Volker and Stephan, R{\"u}diger}, title = {On cardinality constrained cycle and path polytopes}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10093}, number = {07-25}, year = {2007}, abstract = {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.}, language = {en} } @misc{HeinzStephanSchlechte2009, author = {Heinz, Stefan and Stephan, R{\"u}diger and Schlechte, Thomas}, title = {Solving Steel Mill Slab Problems with Branch and Price}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11260}, number = {09-14}, year = {2009}, abstract = {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.}, language = {en} } @misc{Stephan2008, author = {Stephan, R{\"u}diger}, title = {Cardinality Constrained Combinatorial Optimization: Complexity and Polyhedra}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11026}, number = {08-48}, year = {2008}, abstract = {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{\"o}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.}, language = {en} }