TY - GEN A1 - Heinz, Stefan A1 - Stephan, Rüdiger A1 - Schlechte, Thomas T1 - Solving Steel Mill Slab Problems with Branch and Price N2 - 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. T3 - ZIB-Report - 09-14 KW - steel mill slab problem KW - branch-and-price KW - integer programming Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11260 SN - 1438-0064 ER - TY - GEN A1 - Stephan, Rüdiger T1 - Cardinality Constrained Combinatorial Optimization: Complexity and Polyhedra N2 - 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. T3 - ZIB-Report - 08-48 KW - Combinatorial Optimization KW - Cardinality Constraints KW - Matroids KW - Cardinality Forcing Inequalities Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11026 SN - 1438-0064 ER - TY - GEN A1 - Stephan, Rüdiger T1 - On the cardinality constrained matroid polytope N2 - 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. T3 - ZIB-Report - 08-08 KW - Matroid-Polytop KW - Kardinalitätsbeschränkung KW - Separationsalgorithmus KW - Matroid Polytope KW - Cardinality constraints KW - Separation algorithm Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10614 SN - 1438-0064 ER - TY - GEN A1 - Stephan, Rüdiger T1 - Facets of the (s,t)-p-path polytope N2 - \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. T3 - ZIB-Report - 06-38 Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9328 ER - TY - GEN A1 - Kaibel, Volker A1 - Stephan, Rüdiger T1 - On cardinality constrained cycle and path polytopes N2 - 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. T3 - ZIB-Report - 07-25 KW - path KW - cycles KW - integer characterizations KW - facets Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10093 SN - 1438-0064 ER - TY - GEN A1 - Stephan, Rüdiger A1 - Maurras, Jean A1 - Nedev, Roumen T1 - On the connectivity of k-clique polytopes N2 - In this paper, we study the neighbourlicity of the polytope $P_{k n}^2$ constituted by the $k$-cliques of the complete graph $K_n$ on $n$ vertices. We prove that this polytope is $3$-, but not $4$-neighbourly. Following a remark of Pierre Duchet, we partially generalize this result to the $k$-clique polytopes of $r$-uniform complete hypergraphs, $P_{kn}^r$. We show that the neighbourlicity of $P_{kn}^r$ is between $r$ and $2^r-1$ whenever $k\geq r+1$ and $n\geq k+r+1$. Computational results indicate that the upper bound is tight. T3 - ZIB-Report - 10-29 KW - clique polytope KW - connectivity Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11949 ER - TY - GEN A1 - Stephan, Rüdiger T1 - Smaller compact formulation for lot-sizing with constant batches N2 - We consider a variant of the classical lot-sizing problem in which the capacity in each period is an integer multiple of some basic batch size. Pochet and Wolsey (Math. Oper. Res. 18, 1993) presented an O(n^2 min{n,C}) algorithm to solve this problem and a linear program with O(n^3) variables and inequalities, where n is the number of periods and C the batch size. We provide a linear program of size O(n^2 min{n,C}), that is, in case that C < n, our formulation is smaller. T3 - ZIB-Report - 10-30 KW - compact formulation KW - lot-sizing KW - constant batch size Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11956 ER - TY - GEN A1 - Heinz, Stefan A1 - Schlechte, Thomas A1 - Stephan, Rüdiger A1 - Winkler, Michael T1 - Solving steel mill slab design problems N2 - The steel mill slab design problem from the CSPLIB is a combinatorial optimization problem motivated by an application of the steel industry. It has been widely studied in the constraint programming community. Several methods were proposed to solve this problem. A steel mill slab library was created which contains 380 instances. A closely related binpacking problem called the multiple knapsack problem with color constraints, originated from the same industrial problem, was discussed in the integer programming community. In particular, a simple integer program for this problem has been given by Forrest et al. The aim of this paper is to bring these different studies together. Moreover, we adapt the model of Forrest et al. for the steel mill slab design problem. Using this model and a state-of-the-art integer program solver all instances of the steel mill slab library can be solved efficiently to optimality. We improved, thereby, the solution values of 76 instances compared to previous results. Finally, we consider a recently introduced variant of the steel mill slab design problem, where within all solutions which minimize the leftover one is interested in a solution which requires a minimum number of slabs. For that variant we introduce two approaches and solve all instances of the steel mill slab library with this slightly changed objective function to optimality. T3 - ZIB-Report - 11-38 KW - steel mill slab design problem KW - multiple knapsack problem with color constraints KW - integer programming KW - set partitioning KW - binpacking with side constraints Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14089 SN - 1438-0064 ER - TY - JOUR A1 - Balas, Egon A1 - Stephan, Rüdiger T1 - On the cycle polytope of a directed graph and its relaxations JF - Networks Y1 - 2009 U6 - https://doi.org/10.1002/net.20303 VL - 54 IS - 1 SP - 47 EP - 55 ER - TY - JOUR A1 - Kaibel, Volker A1 - Stephan, Rüdiger T1 - On cardinality constrained cycle and path polytopes JF - Math. Program. Y1 - 2010 U6 - https://doi.org/10.1007/s10107-008-0257-2 VL - 123 IS - 2 (A) SP - 371 EP - 394 ER - TY - GEN A1 - Maurras, Jean A1 - Stephan, Rüdiger T1 - On the cardinality constrained matroid polytope Y1 - 2009 ER - TY - BOOK A1 - Stephan, Rüdiger T1 - Polytopes associated with length restricted directed circuits Y1 - 2005 PB - diploma thesis, Technische Universität Berlin ER - TY - JOUR A1 - Stephan, Rüdiger T1 - Facets of the (s,t)-p-path polytope JF - Discrete Appl. Math. Y1 - 2009 U6 - https://doi.org/10.1016/j.dam.2009.06.003 VL - 157 IS - 14 SP - 3119 EP - 3132 ER - TY - JOUR A1 - Stephan, Rüdiger T1 - Cardinality constrained combinatorial optimization JF - Discrete Optim. Y1 - 2010 VL - 7 IS - 3 SP - 99 EP - 113 ER - TY - JOUR A1 - Stephan, Rüdiger A1 - Spiegelberg, Ingo T1 - On cardinality constrained polymatroids JF - Electronic Notes in Discrete Mathematics Y1 - 2010 UR - http://www.sciencedirect.com/science/article/B75GV-50JJF7F-4K/2/2761e6edfcb262af0ba4856767d82a42 U6 - https://doi.org/DOI: 10.1016/j.endm.2010.05.129 VL - 36 SP - 1017 EP - 1024 ER - TY - GEN A1 - Stephan, Rüdiger T1 - An extension of disjunctive programming and its impact for compact tree formulations Y1 - 2010 PB - Center for Operations Research and Econometrics, Université catholique de Louvain, Discussion paper 2010/45 ER - TY - THES A1 - Stephan, Rüdiger T1 - Polyhedral aspects of cardinality constrained combinatorial optimization problems Y1 - 2009 ER - TY - JOUR A1 - Heinz, Stefan A1 - Schlechte, Thomas A1 - Stephan, Rüdiger A1 - Winkler, Michael T1 - Solving steel mill slab design problems JF - Constraints N2 - The steel mill slab design problem from the CSPLIB is a combinatorial optimization problem motivated by an application of the steel industry. It has been widely studied in the constraint programming community. Several methods were proposed to solve this problem. A steel mill slab library was created which contains 380 instances. A closely related binpacking problem called the multiple knapsack problem with color constraints, originated from the same industrial problem, was discussed in the integer programming community. In particular, a simple integer program for this problem has been given by Forrest et al. (INFORMS J Comput 18:129–134, 2006). The aim of this paper is to bring these different studies together. Moreover, we adapt the model of Forrest et al. (INFORMS J Comput 18:129–134, 2006) for the steel mill slab design problem. Using this model and a state-of-the-art integer program solver all instances of the steel mill slab library can be solved efficiently to optimality. We improved, thereby, the solution values of 76 instances compared to previous results (Schaus et al., Constraints 16:125–147, 2010). Finally, we consider a recently introduced variant of the steel mill slab design problem, where within all solutions which minimize the leftover one is interested in a solution which requires a minimum number of slabs. For that variant we introduce two approaches and solve all instances of the steel mill slab library with this slightly changed objective function to optimality. Y1 - 2012 U6 - https://doi.org/10.1007/s10601-011-9113-8 VL - 17 IS - 1 SP - 39 EP - 50 ER - TY - JOUR A1 - Grötschel, Martin A1 - Stephan, Rüdiger T1 - Characterization of Facets of the Hop Constrained Chain Polytope via Dynamic Programming JF - Discrete Applied Mathematics Y1 - 2014 U6 - https://doi.org/10.1016/j.dam.2013.08.015 VL - 162 SP - 229 EP - 246 ER - TY - GEN A1 - Grötschel, Martin A1 - Stephan, Rüdiger T1 - Characterization of Facets of the Hop Constrained Chain Polytope via Dynamic Programming N2 - 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. T3 - ZIB-Report - 11-54 KW - hop constraints KW - chains KW - dynamic programming KW - facets Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14914 SN - 1438-0064 ER -