@misc{Stephan2006, author = {Stephan, R{\"u}diger}, title = {Facets of the (s,t)-p-path polytope}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9328}, number = {06-38}, year = {2006}, abstract = {\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.}, language = {en} } @misc{HeinzSchlechteStephanetal.2011, author = {Heinz, Stefan and Schlechte, Thomas and Stephan, R{\"u}diger and Winkler, Michael}, title = {Solving steel mill slab design problems}, issn = {1438-0064}, doi = {10.1007/s10601-011-9113-8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14089}, number = {11-38}, year = {2011}, abstract = {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.}, language = {en} } @misc{StephanMaurrasNedev2010, author = {Stephan, R{\"u}diger and Maurras, Jean and Nedev, Roumen}, title = {On the connectivity of k-clique polytopes}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11949}, number = {10-29}, year = {2010}, abstract = {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.}, language = {en} } @misc{Stephan2010, author = {Stephan, R{\"u}diger}, title = {Smaller compact formulation for lot-sizing with constant batches}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11956}, number = {10-30}, year = {2010}, abstract = {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.}, language = {en} } @article{Stephan2010, author = {Stephan, R{\"u}diger}, title = {Cardinality constrained combinatorial optimization}, volume = {7}, journal = {Discrete Optim.}, number = {3}, pages = {99 -- 113}, year = {2010}, language = {en} } @article{GroetschelStephan2014, author = {Gr{\"o}tschel, Martin and Stephan, R{\"u}diger}, title = {Characterization of Facets of the Hop Constrained Chain Polytope via Dynamic Programming}, volume = {162}, journal = {Discrete Applied Mathematics}, doi = {10.1016/j.dam.2013.08.015}, pages = {229 -- 246}, year = {2014}, language = {en} } @article{HeinzSchlechteStephanetal.2012, author = {Heinz, Stefan and Schlechte, Thomas and Stephan, R{\"u}diger and Winkler, Michael}, title = {Solving steel mill slab design problems}, volume = {17}, journal = {Constraints}, number = {1}, doi = {10.1007/s10601-011-9113-8}, pages = {39 -- 50}, year = {2012}, abstract = {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.}, language = {en} } @article{StephanSpiegelberg2010, author = {Stephan, R{\"u}diger and Spiegelberg, Ingo}, title = {On cardinality constrained polymatroids}, volume = {36}, journal = {Electronic Notes in Discrete Mathematics}, doi = {DOI: 10.1016/j.endm.2010.05.129}, pages = {1017 -- 1024}, year = {2010}, language = {en} } @misc{Stephan2010, author = {Stephan, R{\"u}diger}, title = {An extension of disjunctive programming and its impact for compact tree formulations}, publisher = {Center for Operations Research and Econometrics, Universit{\´e} catholique de Louvain, Discussion paper 2010/45}, year = {2010}, language = {en} } @phdthesis{Stephan2009, author = {Stephan, R{\"u}diger}, title = {Polyhedral aspects of cardinality constrained combinatorial optimization problems}, year = {2009}, language = {en} }