@misc{BorndoerferMehrgardtReutheretal.2013, author = {Bornd{\"o}rfer, Ralf and Mehrgardt, Julika and Reuther, Markus and Schlechte, Thomas and Waas, Kerstin}, title = {Re-optimization of Rolling Stock Rotations}, issn = {1438-0064}, doi = {10.1007/978-3-319-07001-8_8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42569}, year = {2013}, abstract = {The Rolling Stock Rotation Problem is to schedule rail vehicles in order to cover timetabled trips by a cost optimal set of vehicle rotations. The problem integrates several facets of railway optimization, i.e., vehicle composition, maintenance constraints, and regularity aspects. In industrial applications existing schedules often have to be re-optimized to integrate timetable changes or construction sites. We present an integrated modeling and algorithmic approach for this task as well as computational results for industrial problem instances of DB Fernverkehr AG.}, language = {en} } @misc{SagnolHarman2013, author = {Sagnol, Guillaume and Harman, Radoslav}, title = {Computing exact D-optimal designs by mixed integer second order cone programming}, issn = {1438-0064}, doi = {10.1214/15-AOS1339}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-41932}, year = {2013}, abstract = {Let the design of an experiment be represented by an \$s\$-dimensional vector \$\vec{w}\$ of weights with non-negative components. Let the quality of \$\vec{w}\$ for the estimation of the parameters of the statistical model be measured by the criterion of \$D\$-optimality defined as the \$m\$-th root of the determinant of the information matrix \$M(\vec{w})=\sum_{i=1}^s w_iA_iA_i^T\$, where \$A_i\$, \$i=1,...,s\$, are known matrices with \$m\$ rows. In the paper, we show that the criterion of \$D\$-optimality is second-order cone representable. As a result, the method of second order cone programming can be used to compute an approximate \$D\$-optimal design with any system of linear constraints on the vector of weights. More importantly, the proposed characterization allows us to compute an \emph{exact} \$D\$-optimal design, which is possible thanks to high-quality branch-and-cut solvers specialized to solve mixed integer second order cone problems. We prove that some other widely used criteria are also second order cone representable, for instance the criteria of \$A\$-, and \$G\$-optimality, as well as the criteria of \$D_K\$- and \$A_K\$-optimality, which are extensions of \$D\$-, and \$A\$-optimality used in the case when only a specific system of linear combinations of parameters is of interest. We present several numerical examples demonstrating the efficiency and universality of the proposed method. We show that in many cases the mixed integer second order cone programming approach allows us to find a provably optimal exact design, while the standard heuristics systematically miss the optimum.}, language = {en} } @misc{Berthold2013, author = {Berthold, Timo}, title = {Primal MINLP Heuristics in a nutshell}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42170}, year = {2013}, abstract = {Primal heuristics are an important component of state-of-the-art codes for mixed integer nonlinear programming (MINLP). In this article we give a compact overview of primal heuristics for MINLP that have been suggested in the literature of recent years. We sketch the fundamental concepts of different classes of heuristics and discuss specific implementations. A brief computational experiment shows that primal heuristics play a key role in achieving feasibility and finding good primal bounds within a global MINLP solver.}, language = {en} } @misc{ShinanoHeinzVigerskeetal.2013, author = {Shinano, Yuji and Heinz, Stefan and Vigerske, Stefan and Winkler, Michael}, title = {FiberSCIP - A shared memory parallelization of SCIP}, issn = {1438-0064}, doi = {10.1287/ijoc.2017.0762}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42595}, year = {2013}, abstract = {Recently, parallel computing environments have become significantly popular. In order to obtain the benefit of using parallel computing environments, we have to deploy our programs for these effectively. This paper focuses on a parallelization of SCIP (Solving Constraint Integer Programs), which is a MIP solver and constraint integer programming framework available in source code. There is a parallel extension of SCIP named ParaSCIP, which parallelizes SCIP on massively parallel distributed memory computing environments. This paper describes FiberSCIP, which is yet another parallel extension of SCIP to utilize multi-threaded parallel computation on shared memory computing environments, and has the following contributions: First, the basic concept of having two parallel extensions and the relationship between them and the parallelization framework provided by UG (Ubiquity Generator) is presented, including an implementation of deterministic parallelization. Second, the difficulties to achieve a good performance that utilizes all resources on an actual computing environment and the difficulties of performance evaluation of the parallel solvers are discussed. Third, a way to evaluate the performance of new algorithms and parameter settings of the parallel extensions is presented. Finally, current performance of FiberSCIP for solving mixed-integer linear programs (MIPs) and mixed-integer non-linear programs (MINLPs) in parallel is demonstrated.}, language = {en} } @misc{Gamrath2013, author = {Gamrath, Gerald}, title = {Improving strong branching by domain propagation}, issn = {1438-0064}, doi = {10.1007/s13675-014-0021-8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42546}, year = {2013}, abstract = {One of the essential components of a branch-and-bound based mixed-integer linear programming (MIP) solver is the branching rule. Strong branching is a method used by many state-of-the-art branching rules to select the variable to branch on. It precomputes the dual bounds of potential child nodes by solving auxiliary linear programs (LPs) and thereby helps to take good branching decisions that lead to a small search tree. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Domain propagation is a technique usually used at every node of the branch-and-bound tree to tighten the local domains of variables. Computational experiments on standard MIP instances indicate that our improved strong branching method significantly improves the quality of the predictions and causes almost no additional effort. For a full strong branching rule, we are able to obtain substantial reductions of the branch-and-bound tree size as well as the solving time. Moreover, also the state-of-the-art hybrid branching rule can be improved this way. This paper extends previous work by the author published in the proceedings of the CPAIOR 2013.}, language = {en} } @misc{BorndoerferHoangKarbsteinetal.2013, author = {Bornd{\"o}rfer, Ralf and Hoang, Nam-Dung and Karbstein, Marika and Koch, Thorsten and Martin, Alexander}, title = {How Many Steiner Terminals Can You Connect in 20 Years?}, issn = {1438-0064}, doi = {10.1007/978-3-642-38189-8_10}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42524}, year = {2013}, abstract = {Steiner trees are constructed to connect a set of terminal nodes in a graph. This basic version of the Steiner tree problem is idealized, but it can effectively guide the search for successful approaches to many relevant variants, from both a theoretical and a computational point of view. This article illustrates the theoretical and algorithmic progress on Steiner tree type problems on two examples, the Steiner connectivity and the Steiner tree packing problem.}, language = {en} } @misc{HeismannHildenbrandtSilvestrietal.2013, author = {Heismann, Olga and Hildenbrandt, Achim and Silvestri, Francesco and Reinelt, Gerhard and Bornd{\"o}rfer, Ralf}, title = {HUHFA: A Framework for Facet Classification}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42230}, year = {2013}, abstract = {Usually complete linear descriptions of polytopes consist of an enormous number of facet-defining inequalities already for very small problem sizes. In this paper, we describe a method for dividing the inequalities into equivalence classes without resorting to a normal form. Within each class, facets are related by certain symmetries and it is sufficient to list one representative of each class to give a complete picture of the structural properties of a polytope. We propose an algorithm for the classification and illustrate its efficiency on a broad range of combinatorial optimization problems including the Traveling Salesman and the Linear Ordering Problem.}, language = {en} }