@misc{BuesingD'Andreagiovanni2013, author = {B{\"u}sing, Christina and D'Andreagiovanni, Fabio}, title = {A new theoretical framework for Robust Optimization under multi-band uncertainty}, issn = {1438-0064}, doi = {10.1007/978-3-319-00795-3_17}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42644}, year = {2013}, abstract = {We provide an overview of our main results about studying Linear Programming Problems whose coefficient matrix is subject to uncertainty and the uncertainty is modeled through a multi-band set. Such an uncertainty set generalizes the classical one proposed by Bertsimas and Sim and is particularly suitable in the common case of arbitrary non-symmetric distributions of the parameters. Our investigations were inspired by practical needs of our industrial partner in ongoing projects with focus on the design of robust telecommunications networks.}, language = {en} } @misc{BlancoSchlechte2013, author = {Blanco, Marco and Schlechte, Thomas}, title = {Analysis of Micro-Macro Transformations of Railway Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42710}, year = {2013}, abstract = {A common technique in the solution of large or complex optimization problems is the use of micro-macro transformations. In this paper, we carry out a theoretical analysis of such transformations for the track allocation problem in railway networks. We prove that the cumulative rounding technique of Schlechte et al. satisfies two of three natural optimality criteria and that this performance cannot be improved. We also show that under extreme circumstances, this technique can perform inconvieniently by underestimating the global optimal value.}, language = {en} } @misc{ZakrzewskaD'AndreagiovanniRueppetal.2013, author = {Zakrzewska, Anna and D'Andreagiovanni, Fabio and Ruepp, Sarah and Berger, Michael S.}, title = {Biobjective Optimization of Radio Access Technology Selection and Resource Allocation in Heterogeneous Wireless Networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42675}, year = {2013}, abstract = {We propose a novel optimization model for resource assignment in heterogeneous wireless network. The model adopts two objective functions maximizing the number of served users and the minimum granted utility at once. A distinctive feature of our new model is to consider two consecutive time slots, in order to include handover as an additional decision dimension. Furthermore, the solution algorithm that we propose refines a heuristic solution approach recently proposed in literature, by considering a real joint optimization of the considered resources. The simulation study shows that the new model leads to a significant reduction in handover frequency, when compared to a traditional scheme based on maximum SNR.}, language = {en} } @misc{BauschertBuesingD'Andreagiovannietal.2013, author = {Bauschert, Thomas and B{\"u}sing, Christina and D'Andreagiovanni, Fabio and Koster, Arie M.C.A. and Kutschka, Manuel and Steglich, Uwe}, title = {Network Planning under Demand Uncertainty with Robust Optimization}, issn = {1438-0064}, doi = {10.1109/MCOM.2014.6736760}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42557}, year = {2013}, abstract = {The planning of a communication network is inevitably depending on the quality of both the planning tool and the demand forecast used. In this article, we show exemplarily how the emerging area of Robust Optimization can advance the network planning by a more accurate mathematical description of the demand uncertainty. After a general introduction of the concept and its application to a basic network design problem, we present two applications: multi-layer and mixed-line-rate network design. We conclude with a discussion of extensions of the robustness concept to increase the accuracy of handling uncertainties.}, language = {en} } @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} }