TY - JOUR A1 - Berthold, Timo A1 - Gleixner, Ambros A1 - Heinz, Stefan A1 - Vigerske, Stefan T1 - Analyzing the computational impact of MIQCP solver components JF - Numerical Algebra, Control and Optimization N2 - We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on a linear relaxation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances. Y1 - 2012 U6 - https://doi.org/10.3934/naco.2012.2.739 VL - 2 IS - 4 SP - 739 EP - 748 ER - TY - CHAP A1 - Heinz, Stefan A1 - Beck, J. Christopher T1 - Reconsidering Mixed Integer Programming and MIP-based Hybrids for Scheduling T2 - Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2012) Y1 - 2012 VL - 7298 SP - 211 EP - 227 ER - TY - CHAP A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Schulz, Jens T1 - An approximative Criterion for the Potential of Energetic Reasoning T2 - Theory and Practice of Algorithms in (Computer) Systems Y1 - 2011 VL - 6595 SP - 229 EP - 239 ER - TY - CHAP A1 - Hendel, Gregor A1 - Berthold, Timo A1 - Achterberg, Tobias T1 - Rounding and Propagation Heuristics for Mixed Integer Programming T2 - Operations Research Proceedings 2011 N2 - Primal heuristics are an important component of state-of-the-art codes for mixed integer programming. In this paper, we focus on primal heuristics that only employ computationally inexpensive procedures such as rounding and logical deductions (propagation). We give an overview of eight different approaches. To assess the impact of these primal heuristics on the ability to find feasible solutions, in particular early during search, we introduce a new performance measure, the primal integral. Computational experiments evaluate this and other measures on MIPLIB~2010 benchmark instances. Y1 - 2011 SP - 71 EP - 76 ER - TY - GEN A1 - Berthold, Timo A1 - Salvagnin, Domenico ED - Gomes, Carla ED - Sellmann, Meinolf T1 - Cloud branching T2 - Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems N2 - Branch-and-bound methods for mixed-integer programming (MIP) are traditionally based on solving a linear programming (LP) relaxation and branching on a variable which takes a fractional value in the (single) computed relaxation optimum. In this paper we study branching strategies for mixed-integer programs that exploit the knowledge of multiple alternative optimal solutions (a cloud) of the current LP relaxation. These strategies naturally extend state-of-the-art methods like strong branching, pseudocost branching, and their hybrids. We show that by exploiting dual degeneracy, and thus multiple alternative optimal solutions, it is possible to enhance traditional methods. We present preliminary computational results, applying the newly proposed strategy to full strong branching, which is known to be the MIP branching rule leading to the fewest number of search nodes. It turns out that cloud branching can reduce the mean running time by up to 30% on standard test sets. Y1 - 2013 U6 - https://doi.org/10.1007/978-3-642-38171-3_3 VL - 7874 SP - 28 EP - 43 PB - Springer 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 - Berthold, Timo A1 - Gleixner, Ambros T1 - Undercover: a primal MINLP heuristic exploring a largest sub-MIP JF - Mathematical Programming N2 - We present Undercover, a primal heuristic for nonconvex mixed-integer nonlinear programming (MINLP) that explores a mixed-integer linear subproblem (sub-MIP) of a given MINLP. We solve a vertex covering problem to identify a minimal set of variables that need to be fixed in order to linearize each constraint, a so-called cover. Subsequently, these variables are fixed to values obtained from a reference point, e.g., an optimal solution of a linear relaxation. We apply domain propagation and conflict analysis to try to avoid infeasibilities and learn from them, respectively. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem. We present computational results on a test set of mixed-integer quadratically constrained programs (MIQCPs) and general MINLPs from MINLPLib. It turns out that the majority of these instances allow for small covers. Although general in nature, the heuristic appears most promising for MIQCPs, and complements nicely with existing root node heuristics in different state-of-the-art solvers. Y1 - 2014 U6 - https://doi.org/10.1007/s10107-013-0635-2 VL - 144 IS - 1-2 SP - 315 EP - 346 ER - TY - JOUR A1 - Achterberg, Tobias A1 - Berthold, Timo T1 - Improving the Feasibility Pump JF - Discrete Optimization Y1 - 2007 VL - Special Issue 4 IS - 1 SP - 77 EP - 86 ER - TY - JOUR A1 - Berthold, Timo T1 - Heuristiken im Branch-and-Cut-Framework SCIP JF - OR News Y1 - 2008 IS - 32 SP - 24 EP - 25 ER - TY - GEN A1 - Shinano, Yuji A1 - Heinz, Stefan A1 - Vigerske, Stefan A1 - Winkler, Michael T1 - FiberSCIP - A shared memory parallelization of SCIP N2 - 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. T3 - ZIB-Report - 13-55 KW - parallel KW - branch-and-bound KW - deterministic parallelism KW - constraint integer programming KW - mixed integer programming KW - mixed integer nonlinear programming KW - SCIP KW - MIP KW - MINLP Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42595 SN - 1438-0064 ER - TY - GEN A1 - Gamrath, Gerald T1 - Improving strong branching by domain propagation N2 - 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. T3 - ZIB-Report - 13-47 KW - mixed-integer programming KW - branch-and-bound KW - branching rule KW - variable selection KW - strong branching KW - domain propagation Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42546 SN - 1438-0064 ER - TY - GEN A1 - Gamrath, Gerald A1 - Melchiori, Anna A1 - Berthold, Timo A1 - Gleixner, Ambros A1 - Salvagnin, Domenico T1 - Branching on multi-aggregated variables N2 - In mixed-integer programming, the branching rule is a key component to a fast convergence of the branch-and-bound algorithm. The most common strategy is to branch on simple disjunctions that split the domain of a single integer variable into two disjoint intervals. Multi-aggregation is a presolving step that replaces variables by an affine linear sum of other variables, thereby reducing the problem size. While this simplification typically improves the performance of MIP solvers, it also restricts the degree of freedom in variable-based branching rules. We present a novel branching scheme that tries to overcome the above drawback by considering general disjunctions defined by multi-aggregated variables in addition to the standard disjunctions based on single variables. This natural idea results in a hybrid between variable- and constraint-based branching rules. Our implementation within the constraint integer programming framework SCIP incorporates this into a full strong branching rule and reduces the number of branch-and-bound nodes on a general test set of publicly available benchmark instances. For a specific class of problems, we show that the solving time decreases significantly. T3 - ZIB-Report - 15-10 KW - mixed-integer programming, branch-and-bound, branching rule, strong branching Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-53829 SN - 1438-0064 ER - TY - GEN A1 - Witzig, Jakob A1 - Gamrath, Gerald A1 - Hiller, Benjamin T1 - Reoptimization Techniques in MIP Solvers N2 - Recently, there have been many successful applications of optimization algorithms that solve a sequence of quite similar mixed-integer programs (MIPs) as subproblems. Traditionally, each problem in the sequence is solved from scratch. In this paper we consider reoptimization techniques that try to benefit from information obtained by solving previous problems of the sequence. We focus on the case that subsequent MIPs differ only in the objective function or that the feasible region is reduced. We propose extensions of the very complex branch-and-bound algorithms employed by general MIP solvers based on the idea to ``warmstart'' using the final search frontier of the preceding solver run. We extend the academic MIP solver SCIP by these techniques to obtain a reoptimizing branch-and-bound solver and report computational results which show the effectiveness of the approach. T3 - ZIB-Report - 15-24 Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54375 SN - 1438-0064 ER - TY - GEN A1 - Maher, Stephen J. A1 - Fischer, Tobias A1 - Gally, Tristan A1 - Gamrath, Gerald A1 - Gleixner, Ambros A1 - Gottwald, Robert Lion A1 - Hendel, Gregor A1 - Koch, Thorsten A1 - Lübbecke, Marco A1 - Miltenberger, Matthias A1 - Müller, Benjamin A1 - Pfetsch, Marc A1 - Puchert, Christian A1 - Rehfeldt, Daniel A1 - Schenker, Sebastian A1 - Schwarz, Robert A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Weninger, Dieter A1 - Witt, Jonas T. A1 - Witzig, Jakob T1 - The SCIP Optimization Suite 4.0 N2 - The SCIP Optimization Suite is a powerful collection of optimization software that consists of the branch-cut-and-price framework and mixed-integer programming solver SCIP, the linear programming solver SoPlex, the modeling language Zimpl, the parallelization framework UG, and the generic branch-cut-and-price solver GCG. Additionally, it features the extensions SCIP-Jack for solving Steiner tree problems, PolySCIP for solving multi-objective problems, and SCIP-SDP for solving mixed-integer semidefinite programs. The SCIP Optimization Suite has been continuously developed and has now reached version 4.0. The goal of this report is to present the recent changes to the collection. We not only describe the theoretical basis, but focus on implementation aspects and their computational consequences. T3 - ZIB-Report - 17-12 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-62170 SN - 1438-0064 ER - TY - JOUR A1 - Yokoyama, Ryohei A1 - Shinano, Yuji A1 - Taniguchi, Syusuke A1 - Ohkura, Masashi A1 - Wakui, Tetsuya T1 - Optimization of energy supply systems by MILP branch and bound method in consideration of hierarchical relationship between design and operation JF - Energy Conversion and Management N2 - To attain the highest performance of energy supply systems, it is necessary to rationally determine types, capacities, and numbers of equipment in consideration of their operational strategies corresponding to seasonal and hourly variations in energy demands. In the combinatorial optimization method based on the mixed-integer linear programming (MILP), integer variables are used to express the selection, numbers, and on/off status of operation of equipment, and the number of these variables increases with those of equipment and periods for variations in energy demands, and affects the computation efficiency significantly. In this paper, a MILP method utilizing the hierarchical relationship between design and operation variables is proposed to solve the optimal design problem of energy supply systems efficiently: At the upper level, the optimal values of design variables are searched by the branch and bound method; At the lower level, the values of operation variables are optimized independently at each period by the branch and bound method under the values of design variables given tentatively during the search at the upper level; Lower bounds for the optimal value of the objective function to be minimized are evaluated, and are utilized for the bounding operations at both the levels. This method is implemented into open and commercial MILP solvers. Illustrative and practical case studies on the optimal design of cogeneration systems are conducted, and the validity and effectiveness of the proposed method are clarified. Y1 - 2015 U6 - https://doi.org/10.1016/j.enconman.2014.12.020 VL - 92 SP - 92 EP - 104 ER - TY - CHAP A1 - Yokoyama, Ryohei A1 - Shinano, Yuji T1 - MILP Approaches to Optimal Design and Operation of Distributed Energy Systems T2 - Optimization in the Real World N2 - Energy field is one of the practical areas to which optimization can contribute significantly. In this chapter, the application of mixed-integer linear programming (MILP) approaches to optimal design and operation of distributed energy systems is described. First, the optimal design and operation problems are defined, and relevant previous work is reviewed. Then, an MILP method utilizing the hierarchical relationship between design and operation variables is presented. In the optimal design problem, integer variables are used to express the types, capacities, numbers, operation modes, and on/off states of operation of equipment, and the number of these variables increases with those of equipment and periods for variations in energy demands, and affects the computation efficiency significantly. The presented method can change the enumeration tree for the branching and bounding procedures, and can search the optimal solution very efficiently. Finally, future work in relation to this method is described. Y1 - 2015 SN - 978-4-431-55419-6 U6 - https://doi.org/10.1007/978-4-431-55420-2_9 VL - Volume 13 SP - 157 EP - 176 PB - Springer ER - TY - THES A1 - Wyczisk, Christopher T1 - Portfoliooptimierung mittels mathematischer Optimierung Y1 - 2016 ER - TY - GEN A1 - Gamrath, Gerald A1 - Fischer, Tobias A1 - Gally, Tristan A1 - Gleixner, Ambros A1 - Hendel, Gregor A1 - Koch, Thorsten A1 - Maher, Stephen J. A1 - Miltenberger, Matthias A1 - Müller, Benjamin A1 - Pfetsch, Marc A1 - Puchert, Christian A1 - Rehfeldt, Daniel A1 - Schenker, Sebastian A1 - Schwarz, Robert A1 - Serrano, Felipe A1 - Shinano, Yuji A1 - Vigerske, Stefan A1 - Weninger, Dieter A1 - Winkler, Michael A1 - Witt, Jonas T. A1 - Witzig, Jakob T1 - The SCIP Optimization Suite 3.2 N2 - The SCIP Optimization Suite is a software toolbox for generating and solving various classes of mathematical optimization problems. Its major components are the modeling language ZIMPL, the linear programming solver SoPlex, the constraint integer programming framework and mixed-integer linear and nonlinear programming solver SCIP, the UG framework for parallelization of branch-and-bound-based solvers, and the generic branch-cut-and-price solver GCG. It has been used in many applications from both academia and industry and is one of the leading non-commercial solvers. This paper highlights the new features of version 3.2 of the SCIP Optimization Suite. Version 3.2 was released in July 2015. This release comes with new presolving steps, primal heuristics, and branching rules within SCIP. In addition, version 3.2 includes a reoptimization feature and improved handling of quadratic constraints and special ordered sets. SoPlex can now solve LPs exactly over the rational number and performance improvements have been achieved by exploiting sparsity in more situations. UG has been tested successfully on 80,000 cores. A major new feature of UG is the functionality to parallelize a customized SCIP solver. GCG has been enhanced with a new separator, new primal heuristics, and improved column management. Finally, new and improved extensions of SCIP are presented, namely solvers for multi-criteria optimization, Steiner tree problems, and mixed-integer semidefinite programs. T3 - ZIB-Report - 15-60 KW - mixed-integer linear and nonlinear programming KW - MIP solver KW - MINLP solver KW - linear programming KW - LP solver KW - simplex method KW - modeling KW - parallel branch-and-bound KW - branch-cut-and-price framework KW - generic column generation KW - Steiner tree solver KW - multi-criteria optimization KW - mixed-integer semidefinite programming Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57675 SN - 1438-0064 ER - TY - GEN A1 - Ballerstein, Martin A1 - Michaels, Dennis A1 - Vigerske, Stefan T1 - Linear Underestimators for bivariate functions with a fixed convexity behavior N2 - This is a technical report for the SCIP constraint handler cons_bivariate. We describe a cut-generation algorithm for a class of bivariate twice continuously differentiable functions with fixed convexity behavior over a box. Computational results comparing our cut-generation algorithms with state-of-the-art global optimization software on a series of randomly generated test instances are reported and discussed. T3 - ZIB-Report - 13-02 KW - bivariate functions KW - convex envelope KW - global optimization KW - linear underestimator Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17641 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Hendel, Gregor T1 - Shift-And-Propagate N2 - For mixed integer programming, recent years have seen a growing interest in the design of general purpose primal heuristics for use inside complete solvers. Many of these heuristics rely on an optimal LP solution. Finding this may itself take a significant amount of time. The presented paper addresses this issue by the introduction of the Shift-And-Propagate heuristic. Shift-And-Propagate is a pre-root primal heuristic that does not require a previously found LP solution. It applies domain propagation techniques to quickly drive a variable assignment towards feasibility. Computational experiments indicate that this heuristic is a powerful supplement of existing rounding and propagation heuristics. T3 - ZIB-Report - 13-03 KW - primal heuristic KW - mixed integer programming KW - domain propagation KW - rounding Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17596 SN - 1438-0064 ER - TY - JOUR A1 - Gamrath, Gerald A1 - Koch, Thorsten A1 - Maher, Stephen J. A1 - Rehfeldt, Daniel A1 - Shinano, Yuji T1 - SCIP-Jack – A solver for STP and variants with parallelization extensions JF - Mathematical Programming Computation N2 - The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. While often a strong relationship between different Steiner tree problem variants can be observed, solution approaches employed so far have been prevalently problem-specific. In contrast, this paper introduces a general-purpose solver that can be used to solve both the classical Steiner tree problem and many of its variants without modification. This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances. Y1 - 2017 U6 - https://doi.org/10.1007/s12532-016-0114-x VL - 9 IS - 2 SP - 231 EP - 296 ER - TY - CHAP A1 - Shinano, Yuji A1 - Berthold, Timo A1 - Heinz, Stefan T1 - A First Implementation of ParaXpress: Combining Internal and External Parallelization to Solve MIPs on Supercomputers T2 - Mathematical Software - ICMS 2016, 5th International Conference Berlin, Germany, July 11-14, 2016 Proceedings Y1 - 2016 U6 - https://doi.org/10.1007/978-3-319-42432-3_38 SP - 308 EP - 316 ER - TY - BOOK A1 - Greuel, Martin A1 - Koch, Thorsten A1 - Paule, Peter A1 - Sommese, Andrew T1 - Mathematical Software - ICMS 2016, 5th Int. Conf. Berlin, Germany, July 11-14, 2016, Proceedings T3 - Lecture Notes in Computer Science (LNCS) Y1 - 2016 SN - 978-3-319-42431-6 U6 - https://doi.org/10.1007/978-3-319-42432-3 VL - 9725 PB - Springer ER - TY - CHAP A1 - Berthold, Timo A1 - Farmer, James A1 - Heinz, Stefan A1 - Perregaard, Michael T1 - Parallelization of the FICO Xpress-Optimizer T2 - Mathematical Software - ICMS 2016, 5th International Conference Berlin, Germany, July 11-14, 2016 Proceedings Y1 - 2016 U6 - https://doi.org/10.1007/978-3-319-42432-3_31 SP - 251 EP - 258 ER - TY - CHAP A1 - Chrapary, Hagen A1 - Ren, Yue T1 - The Software Portal swMATH: A State of the Art Report and Next Steps T2 - Mathematical Software - ICMS 2016, 5th International Conference Berlin, Germany, July 11-14, 2016 Proceedings Y1 - 2016 U6 - https://doi.org/10.1007/978-3-319-42432-3_49 SP - 397 EP - 402 ER - TY - CHAP A1 - Wu, Cheng-Lung A1 - Maher, Stephen J. T1 - Airline scheduling and disruption management T2 - L. Budd, S. Ison, eds., Air transportation management: an international perspective Y1 - 2017 SN - 9781472451064 SP - 151 EP - 167 PB - Routledge CY - New York ER - TY - JOUR A1 - Gleixner, Ambros A1 - Berthold, Timo A1 - Müller, Benjamin A1 - Weltge, Stefan T1 - Three Enhancements for Optimization-Based Bound Tightening JF - Journal of Global Optimization N2 - Optimization-based bound tightening (OBBT) is one of the most effective procedures to reduce variable domains of nonconvex mixed-integer nonlinear programs (MINLPs). At the same time it is one of the most expensive bound tightening procedures, since it solves auxiliary linear programs (LPs)—up to twice the number of variables many. The main goal of this paper is to discuss algorithmic techniques for an efficient implementation of OBBT. Most state-of-the-art MINLP solvers apply some restricted version of OBBT and it seems to be common belief that OBBT is beneficial if only one is able to keep its computational cost under control. To this end, we introduce three techniques to increase the efficiency of OBBT: filtering strategies to reduce the number of solved LPs, ordering heuristics to exploit simplex warm starts, and the generation of Lagrangian variable bounds (LVBs). The propagation of LVBs during tree search is a fast approximation to OBBT without the need to solve auxiliary LPs. We conduct extensive computational experiments on MINLPLib2. Our results indicate that OBBT is most beneficial on hard instances, for which we observe a speedup of 17% to 19% on average. Most importantly, more instances can be solved when using OBBT. Y1 - 2017 U6 - https://doi.org/10.1007/s10898-016-0450-4 VL - 67 IS - 4 SP - 731 EP - 757 ER - TY - CHAP A1 - Yokoyama, Ryohei A1 - Nakamura, Ryo A1 - Wakui, Tetsuya A1 - Shinano, Yuji T1 - Evaluation of Performance Robustness of a Gas Turbine Cogeneration Plant Based on a Mixed-Integer Linear Model T2 - ASME Turbo Expo 2016: Turbomachinery Technical Conference and Exposition N2 - In designing energy supply systems, designers are requested to rationally determine equipment types, capacities, and numbers in consideration of equipment operational strategies corresponding to seasonal and hourly variations in energy demands. However, energy demands have some uncertainty at the design stage, and the energy demands which become certain at the operation stage may differ from those estimated at the design stage. Therefore, designers should consider that energy demands have some uncertainty, evaluate the performance robustness against the uncertainty, and design the systems to heighten the robustness. Especially, this issue is important for cogeneration plants, because their performances depend significantly on both heat and power demands. Although robust optimal design methods of energy supply systems under uncertain energy demands were developed, all of them are based on linear models for energy supply systems. However, it is still a hard challenge to develop a robust optimal design method even based on a mixed-integer linear model. At the first step for this challenge, in this paper, a method of evaluating the performance robustness of energy supply systems under uncertain energy demands is proposed based on a mixed-integer linear model. This problem is formulated as a bilevel mixed-integer linear programming one, and a sequential solution method is applied to solve it approximately by discretizing uncertain energy demands within their intervals. In addition, a hierarchical optimization method in consideration of the hierarchical relationship between design and operation variables is applied to solve large scale problems efficiently. Through a case study on a gas turbine cogeneration plant for district energy supply, the validity and effectiveness of the proposed method and features of the performance robustness of the plant are clarified. Y1 - 2016 U6 - https://doi.org/doi:10.1115/GT2016-56217 VL - 3 SP - 1 EP - 9 ER - TY - JOUR A1 - Maher, Stephen J. A1 - Desaulniers, Guy A1 - Soumis, Francois T1 - The daily tail assignment problem under operational uncertainty using look-ahead maintenance constraints JF - European Journal of Operational Research N2 - The tail assignment problem is a critical part of the airline planning process that assigns specific aircraft to sequences of flights, called lines-of-flight, to satisfy operational constraints. The aim of this paper is to develop an operationally flexible method, based upon the one-day routes business model, to compute tail assignments that satisfy short-range—within the next three days—aircraft maintenance requirements. While maintenance plans commonly span multiple days, the methods used to compute tail assignments for the given plans can be overly complex and provide little recourse in the event of schedule perturbations. The presented approach addresses operational uncertainty by using solutions from the one-day routes aircraft maintenance routing approach as input. The daily tail assignment problem is solved with an objective to satisfy maintenance requirements explicitly for the current day and implicitly for the subsequent two days. A computational study will be performed to assess the performance of exact and heuristic solution algorithms that modify the input lines-of-flight to reduce maintenance misalignments. The daily tail assignment problem and the developed algorithms are demonstrated to compute solutions that effectively satisfy maintenance requirements when evaluated using input data collected from three different airlines. Y1 - 2018 U6 - https://doi.org/10.1016/j.ejor.2017.06.041 VL - 264 IS - 2 SP - 534 EP - 547 ER - TY - JOUR A1 - Shinano, Yuji A1 - Heinz, Stefan A1 - Vigerske, Stefan A1 - Winkler, Michael T1 - FiberSCIP - A shared memory parallelization of SCIP JF - INFORMS Journal on Computing N2 - 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 mixed-integer linear programming 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, we present the basic concept of having two parallel extensions, and the relationship between them and the parallelization framework provided by UG (Ubiquity Generator), including an implementation of deterministic parallelization. Second, we discuss the difficulties in achieving a good performance that utilizes all resources on an actual computing environment, and the difficulties of performance evaluation of the parallel solvers. Third, we present a way to evaluate the performance of new algorithms and parameter settings of the parallel extensions. Finally, we demonstrate the current performance of FiberSCIP for solving mixed-integer linear programs (MIPs) and mixed-integer nonlinear programs (MINLPs) in parallel. Y1 - 2018 U6 - https://doi.org/10.1287/ijoc.2017.0762 VL - 30 IS - 1 SP - 11 EP - 30 ER - TY - CHAP A1 - Yokoyama, Ryohei A1 - Shinano, Yuji A1 - Wakayama, Yuki A1 - Wakui, Tetsuya T1 - Multiobjective Optimal Design of a Gas Turbine Cogeneration Plant by a Revised Hierarchical Optimization Method T2 - ASME Turbo Expo 2017: Turbomachinery Technical Conference and Exposition N2 - To attain the highest performance of energy supply systems, it is necessary to rationally determine design specifications in consideration of operational strategies corresponding to energy demands. Mixed-integer linear programming (MILP) approaches have been applied widely to such optimal design problems. A MILP method utilizing the hierarchical relationship between design and operation variables have been proposed to solve them efficiently. However, it cannot necessarily be effective to multi-objective optimal design problems because of the existence of a large number of competing design candidates. In this paper, the hierarchical MILP method is revised from the viewpoint of computation efficiency so that it can be applied practically to multi-objective optimal design problems. At the lower level, the order of the optimal operation problems to be solved is changed based on incumbents obtained previously to increase a lower bound for the optimal value of the combined objective function and reduce the number of the optimal operation problems to be solved. At the upper level, a lower bound for the optimal value of the combined objective function is incorporated into the solution method to reduce the number of the design candidates to be generated. This revised hierarchical MILP method is applied to a multiobjective optimal design of a gas turbine cogeneration plant, and its validity and effectiveness are clarified. Y1 - 2017 U6 - https://doi.org/doi:10.1115/GT2017-64296 VL - 3 SP - 1 EP - 14 ER - TY - CHAP A1 - Shinano, Yuji T1 - The Ubiquity Generator Framework: 7 Years of Progress in Parallelizing Branch-and-Bound T2 - Operations Research Proceedings 2017 N2 - Mixed integer linear programming (MIP) is a general form to model combinatorial optimization problems and has many industrial applications. The performance of MIP solvers has improved tremendously in the last two decades and these solvers have been used to solve many real-word problems. However, against the backdrop of modern computer technology, parallelization is of pivotal importance. In this way, ParaSCIP is the most successful parallel MIP solver in terms of solving previously unsolvable instances from the well-known benchmark instance set MIPLIB by using supercomputers. It solved two instances from MIPLIB2003 and 12 from MIPLIB2010 for the first time to optimality by using up to 80,000 cores on supercomputers. ParaSCIP has been developed by using the Ubiquity Generator (UG) framework, which is a general software package to parallelize any state-of-the-art branch-and-bound based solver. This paper discusses 7 years of progress in parallelizing branch-and-bound solvers with UG. Y1 - 2018 U6 - https://doi.org/10.1007/978-3-319-89920-6_20 SP - 143 EP - 149 PB - Springer International Publishing ER - TY - CHAP A1 - Gamrath, Gerald A1 - Schubert, Christoph T1 - Measuring the impact of branching rules for mixed-integer programming T2 - Operations Research Proceedings 2017 N2 - Branching rules are an integral component of the branch-and-bound algorithm typically used to solve mixed-integer programs and subject to intense research. Different approaches for branching are typically compared based on the solving time as well as the size of the branch-and-bound tree needed to prove optimality. The latter, however, has some flaws when it comes to sophisticated branching rules that do not only try to take a good branching decision, but have additional side-effects. We propose a new measure for the quality of a branching rule that distinguishes tree size reductions obtained by better branching decisions from those obtained by such side-effects. It is evaluated for common branching rules providing new insights in the importance of strong branching. Y1 - 2018 U6 - https://doi.org/10.1007/978-3-319-89920-6_23 SP - 165 EP - 170 PB - Springer International Publishing ER - TY - JOUR A1 - Shinano, Yuji A1 - Berthold, Timo A1 - Heinz, Stefan T1 - ParaXpress: An Experimental Extension of the FICO Xpress-Optimizer to Solve Hard MIPs on Supercomputers JF - Optimization Methods & Software N2 - The Ubiquity Generator (UG) is a general framework for the external parallelization of mixed integer programming (MIP) solvers. In this paper, we present ParaXpress, a distributed memory parallelization of the powerful commercial MIP solver FICO Xpress. Besides sheer performance, an important feature of Xpress is that it provides an internal parallelization for shared memory systems. When aiming for a best possible performance of ParaXpress on a supercomputer, the question arises how to balance the internal Xpress parallelization and the external parallelization by UG against each other. We provide computational experiments to address this question and we show computational results for running ParaXpress on a Top500 supercomputer, using up to 43,344 cores in parallel. Y1 - 2018 U6 - https://doi.org/10.1080/10556788.2018.1428602 VL - 33 IS - 3 SP - 530 EP - 539 ER - TY - THES A1 - Schubert, Christoph T1 - Multi-Level Lookahead Branching Y1 - 2017 ER - TY - GEN A1 - Gamrath, Gerald A1 - Gleixner, Ambros A1 - Koch, Thorsten A1 - Miltenberger, Matthias A1 - Kniasew, Dimitri A1 - Schlögel, Dominik A1 - Martin, Alexander A1 - Weninger, Dieter T1 - Tackling Industrial-Scale Supply Chain Problems by Mixed-Integer Programming N2 - SAP's decision support systems for optimized supply network planning rely on mixed-integer programming as the core engine to compute optimal or near-optimal solutions. The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of a robust and future-proof decision support system for a large and diverse customer base. In this paper we describe our coordinated efforts to ensure that the performance of the underlying solution algorithms matches the complexity of the large supply chain problems and tight time limits encountered in practice. T3 - ZIB-Report - 16-45 KW - supply chain management, supply network optimization, mixed-integer linear programming, primal heuristics, numerical stability, large-scale optimization Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61107 SN - 1438-0064 ER - TY - GEN A1 - Gottwald, Robert Lion A1 - Maher, Stephen J. A1 - Shinano, Yuji T1 - Distributed domain propagation N2 - Portfolio parallelization is an approach that runs several solver instances in parallel and terminates when one of them succeeds in solving the problem. Despite it's simplicity portfolio parallelization has been shown to perform well for modern mixed-integer programming (MIP) and boolean satisfiability problem (SAT) solvers. Domain propagation has also been shown to be a simple technique in modern MIP and SAT solvers that effectively finds additional domain reductions after a variables domain has been reduced. This paper investigates the impact of distributed domain propagation in modern MIP solvers that employ portfolio parallelization. Computational experiments were conducted for two implementations of this parallelization approach. While both share global variable bounds and solutions they communicate differently. In one implementation the communication is performed only at designated points in the solving process and in the other it is performed completely asynchronously. Computational experiments show a positive performance impact of communicating global variable bounds and provide valuable insights in communication strategies for parallel solvers. T3 - ZIB-Report - 16-71 KW - mixed integer programming KW - parallelization KW - domain propagation KW - portfolio solvers Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61380 SN - 1438-0064 ER - TY - GEN A1 - Gamrath, Gerald A1 - Koch, Thorsten A1 - Maher, Stephen J. A1 - Rehfeldt, Daniel A1 - Shinano, Yuji T1 - SCIP-Jack - A solver for STP and variants with parallelization extensions N2 - The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. While often a strong relationship between different Steiner tree problem variants can be observed, solution approaches employed so far have been prevalently problem specific. In contrast, this paper introduces a general purpose solver that can be used to solve both the classical Steiner tree problem and many of its variants without modification. This is achieved by transforming various problem variants into a general form and solving them using a state-of-the-art MIP-framework. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances. T3 - ZIB-Report - 15-27 Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54648 SN - 1438-0064 N1 - A revised version is provided here: http://nbn-resolving.de/urn:nbn:de:0297-zib-60170. ER - TY - GEN A1 - Hendel, Gregor T1 - Enhancing MIP branching decisions by using the sample variance of pseudo-costs N2 - The selection of a good branching variable is crucial for small search trees in Mixed Integer Programming. Most modern solvers employ a strategy guided by history information, mainly the variable pseudo-costs, which are used to estimate the objective gain. At the beginning of the search, such information is usually collected via an expensive look-ahead strategy called strong-branching until variables are considered reliable. The reliability notion is thereby mostly based on fixed-number thresholds, which may lead to ineffective branching decisions on problems with highly varying objective gains. We suggest two new notions of reliability motivated by mathematical statistics that take into account the sample variance of the past observations on each variable individually. The first method prioritizes additional strong-branching look-aheads on variables whose pseudo-costs show a large variance by measuring the relative error of a pseudo-cost confidence interval. The second method performs a two-sample Student-t test for filtering branching candidates with a high probability to be better than the best history candidate. Both methods were implemented in the MIP-solver SCIP and computational results on standard MIP test sets are presented. T3 - ZIB-Report - 15-28 KW - mixed-integer programming KW - reliability branching Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54591 SN - 1438-0064 ER - TY - CHAP A1 - Hendel, Gregor T1 - Enhancing MIP Branching Decisions by Using the Sample Variance of Pseudo Costs T2 - Integration of AI and OR Techniques in Constraint Programming N2 - The selection of a good branching variable is crucial for small search trees in Mixed Integer Programming. Most modern solvers employ a strategy guided by history information, mainly the variable pseudo-costs, which are used to estimate the objective gain. At the beginning of the search, such information is usually collected via an expensive look-ahead strategy called strong branching until variables are considered reliable. The reliability notion is thereby mostly based on fixed-number thresholds, which may lead to ineffective branching decisions on problems with highly varying objective gains. We suggest two new notions of reliability motivated by mathematical statistics that take into account the sample variance of the past observations on each variable individually. The first method prioritizes additional strong branching look-aheads on variables whose pseudo-costs show a large variance by measuring the relative error of a pseudo-cost confidence interval. The second method performs a specialized version of a two-sample Student’s t -test for filtering branching candidates with a high probability to be better than the best history candidate. Both methods were implemented in the MIP-solver SCIP and computational results on standard MIP test sets are presented. Y1 - 2015 U6 - https://doi.org/10.1007/978-3-319-18008-3_14 VL - 9075 SP - 199 EP - 214 ER - TY - GEN A1 - Gamrath, Gerald A1 - Schubert, Christoph T1 - Measuring the impact of branching rules for mixed-integer programming N2 - Branching rules are an integral component of the branch-and-bound algorithm typically used to solve mixed-integer programs and subject to intense research. Different approaches for branching are typically compared based on the solving time as well as the size of the branch-and-bound tree needed to prove optimality. The latter, however, has some flaws when it comes to sophisticated branching rules that do not only try to take a good branching decision, but have additional side-effects. We propose a new measure for the quality of a branching rule that distinguishes tree size reductions obtained by better branching decisions from those obtained by such side-effects. It is evaluated for common branching rules providing new insights in the importance of strong branching. T3 - ZIB-Report - 17-34 KW - mixed-integer programming KW - branch-and-bound KW - branching rule KW - strong branching Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64722 SN - 1438-0064 ER - TY - GEN A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Generalized preprocessing techniques for Steiner tree and maximum-weight connected subgraph problems N2 - This article introduces new preprocessing techniques for the Steiner tree problem in graphs and one of its most popular relatives, the maximum-weight connected subgraph problem. Several of the techniques generalize previous results from the literature. The correctness of the new methods is shown, but also their NP-hardness is demonstrated. Despite this pessimistic worst-case complexity, several relaxations are discussed that are expected to allow for a strong practical efficiency of these techniques in strengthening both exact and heuristic solving approaches. T3 - ZIB-Report - 17-57 KW - Steiner tree KW - maximum-weight connected subgraph Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-65439 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Perregaard, Michael A1 - Mészáros, Csaba T1 - Four good reasons to use an Interior Point solver within a MIP solver N2 - "Interior point algorithms are a good choice for solving pure LPs or QPs, but when you solve MIPs, all you need is a dual simplex." This is the common conception which disregards that an interior point solution provides some unique structural insight into the problem at hand. In this paper, we will discuss some of the benefits that an interior point solver brings to the solution of difficult MIPs within FICO Xpress. This includes many different components of the MIP solver such as branching variable selection, primal heuristics, preprocessing, and of course the solution of the LP relaxation. T3 - ZIB-Report - 17-42 KW - mixed integer programming KW - interior point algorithm KW - Newton barrier method KW - analytic center Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64599 SN - 1438-0064 ER - TY - GEN A1 - Miltenberger, Matthias A1 - Ralphs, Ted A1 - Steffy, Daniel T1 - Exploring the Numerics of Branch-and-Cut for Mixed Integer Linear Optimization T2 - Operations Research Proceedings 2017 N2 - We investigate how the numerical properties of the LP relaxations evolve throughout the solution procedure in a solver employing the branch-and-cut algorithm. The long-term goal of this work is to determine whether the effect on the numerical conditioning of the LP relaxations resulting from the branching and cutting operations can be effectively predicted and whether such predictions can be used to make better algorithmic choices. In a first step towards this goal, we discuss here the numerical behavior of an existing solver in order to determine whether our intuitive understanding of this behavior is correct. T3 - ZIB-Report - 17-43 KW - Mixed Integer Programming KW - Linear Programming KW - Algorithm Analysis Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64645 SN - 1438-0064 ER - TY - GEN A1 - Schade, Stanley A1 - Schlechte, Thomas A1 - Witzig, Jakob T1 - Structure-based Decomposition for Pattern-Detection for Railway Timetables N2 - We consider the problem of pattern detection in large scale railway timetables. This problem arises in rolling stock optimization planning in order to identify invariant sections of the timetable for which a cyclic rotation plan is adequate. We propose a dual reduction technique which leads to an decomposition and enumeration method. Computational results for real world instances demonstrate that the method is able to produce optimal solutions as fast as standard MIP solvers. T3 - ZIB-Report - 17-40 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64525 SN - 1438-0064 ER - TY - CHAP A1 - Miltenberger, Matthias A1 - Ralphs, Ted A1 - Steffy, Daniel T1 - Exploring the Numerics of Branch-and-Cut for Mixed Integer Linear Optimization T2 - Operations Research Proceedings 2017 N2 - We investigate how the numerical properties of the LP relaxations evolve throughout the solution procedure in a solver employing the branch-and-cut algorithm. The long-term goal of this work is to determine whether the effect on the numerical conditioning of the LP relaxations resulting from the branching and cutting operations can be effectively predicted and whether such predictions can be used to make better algorithmic choices. In a first step towards this goal, we discuss here the numerical behavior of an existing solver in order to determine whether our intuitive understanding of this behavior is correct. Y1 - 2018 U6 - https://doi.org/10.1007/978-3-319-89920-6 SP - 151 EP - 157 PB - Springer International Publishing ER - TY - CHAP A1 - Yokoyama, Ryohei A1 - Shinano, Yuji A1 - Taniguchi, Syusuke A1 - Ohkura, Masashi A1 - Wakui, Tetsuya T1 - Generation of multiple best solutions in multiobjective optimal design of energy supply systems T2 - Proceedings of the 15th International Conference on Power Engineering. ICOPE 2015 N2 - Optimization approaches based on the mixed-integer linear programming (MILP) have been utilized to design energy supply systems. In this paper, an MILP method utilizing the hierarchical relationship between design and operation is extended to search not only the optimal solution but also suboptimal ones which follow the optimal one without any omissions, what are called K-best solutions, efficiently in a multiobjective optimal design problem. At the upper level, the values of design variables for the K-best solutions are searched by the branch and bound method. At the lower level, the values of operation variables are optimized independently at each period by the branch and bound method under the values of design variables given tentatively. Incumbents for the K-best solutions and an upper bound for all the values of the objective function for the K-best solutions are renewed if necessary between both the levels. This method is implemented into a commercial MILP solver. A practical case study on the multiobjective optimal design of a cogeneration system is conducted, and the validity and effectiveness of the method are clarified. Y1 - 2015 U6 - https://doi.org/10.1299/jsmeicope.2015.12._ICOPE-15-_56 ER - TY - JOUR A1 - Gleixner, Ambros A1 - Steffy, Daniel A1 - Wolter, Kati T1 - Iterative Refinement for Linear Programming JF - INFORMS Journal on Computing N2 - We describe an iterative refinement procedure for computing extended precision or exact solutions to linear programming problems (LPs). Arbitrarily precise solutions can be computed by solving a sequence of closely related LPs with limited precision arithmetic. The LPs solved share the same constraint matrix as the original problem instance and are transformed only by modification of the objective function, right-hand side, and variable bounds. Exact computation is used to compute and store the exact representation of the transformed problems, while numeric computation is used for solving LPs. At all steps of the algorithm the LP bases encountered in the transformed problems correspond directly to LP bases in the original problem description. We show that this algorithm is effective in practice for computing extended precision solutions and that it leads to a direct improvement of the best known methods for solving LPs exactly over the rational numbers. Our implementation is publically available as an extension of the academic LP solver SoPlex. Y1 - 2016 U6 - https://doi.org/10.1287/ijoc.2016.0692 VL - 28 IS - 3 SP - 449 EP - 464 ER - TY - CHAP A1 - Hendel, Gregor T1 - Exploiting Solving Phases for Mixed-Integer Programs T2 - Operations Research Proceedings 2015 N2 - Modern MIP solving software incorporates dozens of auxiliary algorithmic components for supporting the branch-and-bound search in finding and improving solutions and in strengthening the relaxation. Intuitively, a dynamic solving strategy with an appropriate emphasis on different solving components and strategies is desirable during the search process. We propose an adaptive solver behavior that dynamically reacts on transitions between the three typical phases of a MIP solving process: The first phase objective is to find a feasible solution. During the second phase, a sequence of incumbent solutions gets constructed until the incumbent is eventually optimal. Proving optimality is the central objective of the remaining third phase. Based on the MIP-solver SCIP, we demonstrate the usefulness of the phase concept both with an exact recognition of the optimality of a solution, and provide heuristic alternatives to make use of the concept in practice. Y1 - 2016 U6 - https://doi.org/10.1007/978-3-319-42902-1_1 SP - 3 EP - 9 ER - TY - CHAP A1 - Shinano, Yuji A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Koch, Thorsten A1 - Winkler, Michael T1 - Solving Open MIP Instances with ParaSCIP on Supercomputers using up to 80,000 Cores T2 - Proc. of 30th IEEE International Parallel & Distributed Processing Symposium N2 - This paper describes how we solved 12 previously unsolved mixed-integer program- ming (MIP) instances from the MIPLIB benchmark sets. To achieve these results we used an enhanced version of ParaSCIP, setting a new record for the largest scale MIP computation: up to 80,000 cores in parallel on the Titan supercomputer. In this paper we describe the basic parallelization mechanism of ParaSCIP, improvements of the dynamic load balancing and novel techniques to exploit the power of parallelization for MIP solving. We give a detailed overview of computing times and statistics for solving open MIPLIB instances. Y1 - 2016 U6 - https://doi.org/10.1109/IPDPS.2016.56 ER - TY - GEN A1 - Witzig, Jakob T1 - Conflict Driven Diving for Mixed Integer Programming N2 - The analysis of infeasibility plays an important role in solving satisfiability problems (SAT) and mixed integer programs (MIPs). In mixed integer programming, this procedure is called conflict analysis. So far, modern MIP solvers use conflict analysis only for propagation and improving the dual bound, i.e., fathoming nodes that cannot contain feasible solutions. In this short paper, we present a new approach which uses conflict information to improve the primal bound during a MIP solve. To derive new improving primal solutions we use a conflict driven diving heuristic called conflict diving that uses the information obtained by conflict analysis. Conflict diving pursues a twofold strategy. By using conflict information the new diving approach is guided into parts of the search space that are usually not explored by other diving heuristics. At the same time, conflict diving has a fail-fast-strategy to reduce the time spent if it cannot find a new primal solution. As a byproduct, additional valid conflict constraints can be derived, from which a MIP solver can gain benefit to improve the dual bound as well. To show the added-value of conflict diving within a MIP solver, conflict diving has been implemented within the non-commercial MIP solver SCIP. Experiments are carried out on general MIP instances from standard public test sets, like MIPLIB2010 or Cor@l. T3 - ZIB-Report - 17-69 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-66116 SN - 1438-0064 ER - TY - GEN A1 - Achterberg, Tobias A1 - Bixby, Robert E. A1 - Gu, Zonghao A1 - Rothberg, Edward A1 - Weninger, Dieter T1 - Presolve Reductions in Mixed Integer Programming N2 - Mixed integer programming has become a very powerful tool for modeling and solving real-world planning and scheduling problems, with the breadth of applications appearing to be almost unlimited. A critical component in the solution of these mixed-integer programs is a set of routines commonly referred to as presolve. Presolve can be viewed as a collection of preprocessing techniques that reduce the size of and, more importantly, improve the ``strength'' of the given model formulation, that is, the degree to which the constraints of the formulation accurately describe the underlying polyhedron of integer-feasible solutions. As our computational results will show, presolve is a key factor in the speed with which we can solve mixed-integer programs, and is often the difference between a model being intractable and solvable, in some cases easily solvable. In this paper we describe the presolve functionality in the Gurobi commercial mixed-integer programming code. This includes an overview, or taxonomy of the different methods that are employed, as well as more-detailed descriptions of several of the techniques, with some of them appearing, to our knowledge, for the first time in the literature. T3 - ZIB-Report - 16-44 KW - integer programming KW - presolving KW - Gurobi Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60370 SN - 1438-0064 ER - TY - GEN A1 - Rehfeldt, Daniel A1 - Koch, Thorsten A1 - Maher, Stephen J. T1 - Reduction Techniques for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem N2 - The concept of reduction has frequently distinguished itself as a pivotal ingredient of exact solving approaches for the Steiner tree problem in graphs. In this paper we broaden the focus and consider reduction techniques for three Steiner problem variants that have been extensively discussed in the literature and entail various practical applications: The prize-collecting Steiner tree problem, the rooted prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem. By introducing and subsequently deploying numerous new reduction methods, we are able to drastically decrease the size of a large number of benchmark instances, already solving more than 90 percent of them to optimality. Furthermore, we demonstrate the impact of these techniques on exact solving, using the example of the state-of-the-art Steiner problem solver SCIP-Jack. T3 - ZIB-Report - 16-47 KW - Steiner tree problems KW - reduction techniques KW - prize-collecting Steiner tree problem KW - maximum-weight connected subgraph problem Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60420 SN - 1438-0064 ER - TY - GEN A1 - Pulaj, Jonad T1 - Cutting Planes for Families Implying Frankl's Conjecture N2 - We find previously unknown families which imply Frankl’s conjecture using an algorithmic framework. The conjecture states that for any non-empty union-closed (or Frankl) family there exists an element in at least half of the sets. Poonen’s Theorem characterizes the existence of weights which determine whether a given Frankl family implies the conjecture for all Frankl families which contain it. A Frankl family is Non–Frankl-Complete (Non–FC), if it does not imply the conjecture in its elements for some Frankl family that contains it. We design a cutting-plane method that computes the explicit weights which imply the existence conditions of Poonen’s Theorem. This method allows us to find a counterexample to a ten-year-old conjecture by R. Morris about the structure of generators for Non–FC-families. T3 - ZIB-Report - 16-51 KW - extremal combinatorics, extremal set theory, cutting plane, exact integer programming Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60626 SN - 1438-0064 ER - TY - GEN A1 - Witzig, Jakob A1 - Beckenbach, Isabel A1 - Eifler, Leon A1 - Fackeldey, Konstantin A1 - Gleixner, Ambros A1 - Grever, Andreas A1 - Weber, Marcus T1 - Mixed-Integer Programming for Cycle Detection in Non-reversible Markov Processes N2 - In this paper, we present a new, optimization-based method to exhibit cyclic behavior in non-reversible stochastic processes. While our method is general, it is strongly motivated by discrete simulations of ordinary differential equations representing non-reversible biological processes, in particular molecular simulations. Here, the discrete time steps of the simulation are often very small compared to the time scale of interest, i.e., of the whole process. In this setting, the detection of a global cyclic behavior of the process becomes difficult because transitions between individual states may appear almost reversible on the small time scale of the simulation. We address this difficulty using a mixed-integer programming model that allows us to compute a cycle of clusters with maximum net flow, i.e., large forward and small backward probability. For a synthetic genetic regulatory network consisting of a ring-oscillator with three genes, we show that this approach can detect the most productive overall cycle, outperforming classical spectral analysis methods. Our method applies to general non-equilibrium steady state systems such as catalytic reactions, for which the objective value computes the effectiveness of the catalyst. T3 - ZIB-Report - 16-39 KW - Non-reversible Markov Processes KW - NESS KW - Mixed-Integer Programming KW - Markov State Models Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60353 SN - 1438-0064 ER - TY - JOUR A1 - Witzig, Jakob A1 - Beckenbach, Isabel A1 - Eifler, Leon A1 - Fackeldey, Konstantin A1 - Gleixner, Ambros A1 - Grever, Andreas A1 - Weber, Marcus T1 - Mixed-Integer Programming for Cycle Detection in Non-reversible Markov Processes JF - Multiscale Modeling and Simulation N2 - In this paper, we present a new, optimization-based method to exhibit cyclic behavior in non-reversible stochastic processes. While our method is general, it is strongly motivated by discrete simulations of ordinary differential equations representing non-reversible biological processes, in particular molecular simulations. Here, the discrete time steps of the simulation are often very small compared to the time scale of interest, i.e., of the whole process. In this setting, the detection of a global cyclic behavior of the process becomes difficult because transitions between individual states may appear almost reversible on the small time scale of the simulation. We address this difficulty using a mixed-integer programming model that allows us to compute a cycle of clusters with maximum net flow, i.e., large forward and small backward probability. For a synthetic genetic regulatory network consisting of a ring-oscillator with three genes, we show that this approach can detect the most productive overall cycle, outperforming classical spectral analysis methods. Our method applies to general non-equilibrium steady state systems such as catalytic reactions, for which the objective value computes the effectiveness of the catalyst. KW - Markov State Models KW - NESS KW - Non-reversible Markov Processes KW - Mixed-Integer Programming Y1 - 2018 U6 - https://doi.org/10.1137/16M1091162 SN - 1438-0064 VL - 16 IS - 1 SP - 248 EP - 265 ER - TY - JOUR A1 - Maher, Stephen J. T1 - A novel passenger recovery approach for the integrated airline recovery problem JF - Computers & Operations Research N2 - Schedule disruptions require airlines to intervene through the process of recovery; this involves modifications to the planned schedule, aircraft routings, crew pairings and passenger itineraries. Passenger recovery is generally considered as the final stage in this process, and hence passengers experience unnecessarily large impacts resulting from flight delays and cancellations. Most recovery approaches considering passengers involve a separately defined module within the problem formulation. However, this approach may be overly complex for recovery in many aviation and general transportation applications. This paper presents a unique description of the cancellation variables that models passenger recovery by prescribing the alternative travel arrangements for passengers in the event of flight cancellations. The results will demonstrate that this simple, but effective, passenger recovery approach significantly reduces the operational costs of the airline and increases passenger flow through the network. The integrated airline recovery problem with passenger reallocation is solved using column-and-row generation to achieve high quality solutions in short runtimes. An analysis of the column-and-row generation solution approach is performed, identifying a number of enhancement techniques to further improve the solution runtimes. Y1 - 2015 U6 - https://doi.org/10.1016/j.cor.2014.11.005 VL - 57 SP - 123 EP - 137 ER - TY - GEN A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Hendel, Gregor T1 - Rounding and Propagation Heuristics for Mixed Integer Programming N2 - Primal heuristics are an important component of state-of-the-art codes for mixed integer programming. In this paper, we focus on primal heuristics that only employ computationally inexpensive procedures such as rounding and logical deductions (propagation). We give an overview of eight different approaches. To assess the impact of these primal heuristics on the ability to find feasible solutions, in particular early during search, we introduce a new performance measure, the primal integral. Computational experiments evaluate this and other measures on MIPLIB~2010 benchmark instances. T3 - ZIB-Report - 11-29 KW - primal heuristic KW - mixed integer programming KW - domain propagation Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-13255 ER - TY - CHAP A1 - Berthold, Timo A1 - Feydy, Thibaut A1 - Stuckey, Peter ED - Lodi, Andrea ED - Milano, Michela ED - Toth, Paolo T1 - Rapid Learning for Binary Programs T2 - Proc. of CPAIOR 2010 Y1 - 2010 VL - 6140 SP - 51 EP - 55 PB - Springer ER - TY - CHAP A1 - Berthold, Timo ED - Kalcsics, Jörg ED - Nickel, Stefan T1 - Heuristics of the Branch-Cut-and-Price-Framework SCIP T2 - Operations Research Proceedings 2007 Y1 - 2008 SP - 31 EP - 36 PB - Springer-Verlag ER - TY - THES A1 - Berthold, Timo T1 - Primal Heuristics for Mixed Integer Programs Y1 - 2006 UR - http://opus.kobv.de/zib/volltexte/2007/1054/ ER - TY - CHAP A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Lübbecke, Marco A1 - Möhring, Rolf A1 - Schulz, Jens ED - Lodi, Andrea ED - Milano, Michela ED - Toth, Paolo T1 - A Constraint Integer Programming Approach for Resource-Constrained Project Scheduling T2 - Proc. of CPAIOR 2010 Y1 - 2010 VL - 6140 SP - 313 EP - 317 PB - Springer ER - TY - CHAP A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Pfetsch, Marc ED - Kullmann, Oliver T1 - Nonlinear pseudo-Boolean optimization T2 - Theory and Applications of Satisfiability Testing – SAT 2009 Y1 - 2009 VL - 5584 SP - 441 EP - 446 PB - Springer ER - TY - CHAP A1 - Achterberg, Tobias A1 - Berthold, Timo ED - van Hoeve, Willem ED - Hooker, John T1 - Hybrid Branching T2 - Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 6th International Conference, CPAIOR 2009 Y1 - 2009 VL - 5547 SP - 309 EP - 311 PB - Springer ER - TY - CHAP A1 - Berthold, Timo A1 - Pfetsch, Marc ED - Fleischmann, Bernhard ED - Borgwardt, Karl ED - Klein, Robert ED - Tuma, Axel T1 - Detecting Orbitopal Symmetries T2 - Operations Research Proceedings 2008 Y1 - 2009 SP - 433 EP - 438 PB - Springer-Verlag ER - TY - THES A1 - Gamrath, Gerald T1 - Generic Branch-Cut-and-Price N2 - In this thesis, we present the theoretical background, implementational details and computational results concerning the generic branch-cut-and-price solver GCG. KW - mixed-integer programming KW - column generation KW - branch-and-price Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57543 ER - TY - GEN A1 - Maher, Stephen J. A1 - Miltenberger, Matthias A1 - Pedroso, João Pedro A1 - Rehfeldt, Daniel A1 - Schwarz, Robert A1 - Serrano, Felipe T1 - PySCIPOpt: Mathematical Programming in Python with the SCIP Optimization Suite N2 - SCIP is a solver for a wide variety of mathematical optimization problems. It is written in C and extendable due to its plug-in based design. However, dealing with all C specifics when extending SCIP can be detrimental to development and testing of new ideas. This paper attempts to provide a remedy by introducing PySCIPOpt, a Python interface to SCIP that enables users to write new SCIP code entirely in Python. We demonstrate how to intuitively model mixed-integer linear and quadratic optimization problems and moreover provide examples on how new Python plug-ins can be added to SCIP. T3 - ZIB-Report - 16-64 KW - SCIP, Mathematical optimization, Python, Modeling Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61348 SN - 1438-0064 ER - TY - JOUR A1 - Gleixner, Ambros A1 - Maher, Stephen A1 - Müller, Benjamin A1 - Pedroso, João Pedro T1 - Price-and-verify: a new algorithm for recursive circle packing using Dantzig–Wolfe decomposition JF - Annals of Operations Research N2 - Packing rings into a minimum number of rectangles is an optimization problem which appears naturally in the logistics operations of the tube industry. It encompasses two major difficulties, namely the positioning of rings in rectangles and the recursive packing of rings into other rings. This problem is known as the Recursive Circle Packing Problem (RCPP). We present the first dedicated method for solving RCPP that provides strong dual bounds based on an exact Dantzig–Wolfe reformulation of a nonconvex mixed-integer nonlinear programming formulation. The key idea of this reformulation is to break symmetry on each recursion level by enumerating one-level packings, i.e., packings of circles into other circles, and by dynamically generating packings of circles into rectangles. We use column generation techniques to design a “price-and-verify” algorithm that solves this reformulation to global optimality. Extensive computational experiments on a large test set show that our method not only computes tight dual bounds, but often produces primal solutions better than those computed by heuristics from the literature. Y1 - 2018 U6 - https://doi.org/10.1007/s10479-018-3115-5 VL - 284 IS - 2 SP - 527 EP - 555 PB - Springer US ER - TY - GEN A1 - Gamrath, Gerald A1 - Koch, Thorsten A1 - Maher, Stephen J. A1 - Rehfeldt, Daniel A1 - Shinano, Yuji T1 - SCIP-Jack – A solver for STP and variants with parallelization extensions N2 - The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. While often a strong relationship between different Steiner tree problem variants can be observed, solution approaches employed so far have been prevalently problem-specific. In contrast, this paper introduces a general-purpose solver that can be used to solve both the classical Steiner tree problem and many of its variants without modification. This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances. T3 - ZIB-Report - 16-41 KW - Steiner tree problem KW - SCIP-Jack KW - Steiner tree variants KW - maximum-weight connected subgraph KW - prize-collecting Steiner tree Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60170 SN - 1438-0064 ER - TY - GEN A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Transformations for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem to SAP N2 - Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art solvers for well-known variants such as the Steiner tree problem in graphs. In this paper transformations for both the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to the Steiner arborescence problem are introduced for the first time. Furthermore, we demonstrate the considerable implications for practical solving approaches, including the computation of strong upper and lower bounds. T3 - ZIB-Report - 16-36 KW - graph transformation KW - Steiner tree problems KW - prize-collecting Steiner tree problem KW - maximum-weight connected subgraph problem Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59777 SN - 1438-0064 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Schenker, Sebastian A1 - Skutella, Martin A1 - Strunk, Timo ED - Greuel, G.-M. ED - Koch, Thorsten ED - Paule, Peter ED - Sommese, Andrew T1 - PolySCIP T2 - Mathematical Software – ICMS 2016, 5th International Conference, Berlin, Germany, July 11-14, 2016, Proceedings N2 - PolySCIP is a new solver for multi-criteria integer and multi-criteria linear programs handling an arbitrary number of objectives. It is available as an official part of the non-commercial constraint integer programming framework SCIP. It utilizes a lifted weight space approach to compute the set of supported extreme non-dominated points and unbounded non-dominated rays, respectively. The algorithmic approach can be summarized as follows: At the beginning an arbitrary non-dominated point is computed (or it is determined that there is none) and a weight space polyhedron created. In every next iteration a vertex of the weight space polyhedron is selected whose entries give rise to a single-objective optimization problem via a combination of the original objectives. If the ptimization of this single-objective problem yields a new non-dominated point, the weight space polyhedron is updated. Otherwise another vertex of the weight space polyhedron is investigated. The algorithm finishes when all vertices of the weight space polyhedron have been investigated. The file format of PolySCIP is based on the widely used MPS format and allows a simple generation of multi-criteria models via an algebraic modelling language. Y1 - 2016 SN - 978-3-319-42431-6 U6 - https://doi.org/10.1007/978-3-319-42432-3_32 VL - 9725 SP - 259 EP - 264 PB - Springer International Publishing ET - Mathematical Software – ICMS 2016 ER - TY - JOUR A1 - Humpola, Jesco A1 - Serrano, Felipe T1 - Sufficient pruning conditions for MINLP in gas network design JF - EURO Journal on Computational Optimization N2 - One-quarter of Europe’s energy demand is provided by natural gas distributed through a vast pipeline network covering the whole of Europe. At a cost of 1 million Euros per kilometer the extension of the European pipeline network is already a multi-billion Euro business. Therefore, automatic planning tools that support the decision process are desired. We model the topology optimization problem in gas networks by a mixed-integer nonlinear program (MINLP). This gives rise to a so-called active transmission problem, a continuous nonlinear non-convex feasibility problem which emerges from the MINLP model by fixing all integral variables. We offer novel sufficient conditions for proving the infeasibility of this active transmission problem. These conditions can be expressed in the form of a mixed-integer program (MILP), i.e., the infeasibility of a non-convex continuous nonlinear program (NLP) can be certified by solving an MILP. This result provides an efficient pruning procedure in a branch-and-bound algorithm. Our computational results demonstrate a substantial speedup for the necessary computations. Y1 - 2017 U6 - https://doi.org/10.1007/s13675-016-0077-8 VL - 5 IS - 1-2 SP - 239 EP - 261 PB - Springer Berlin Heidelberg ER - TY - GEN A1 - Breuer, Thomas A1 - Bussieck, Michael A1 - Cao, Karl-Kien A1 - Cebulla, Felix A1 - Fiand, Frederik A1 - Gils, Hans Christian A1 - Gleixner, Ambros A1 - Khabi, Dmitry A1 - Koch, Thorsten A1 - Rehfeldt, Daniel A1 - Wetzel, Manuel T1 - Optimizing Large-Scale Linear Energy System Problems with Block Diagonal Structure by Using Parallel Interior-Point Methods N2 - Current linear energy system models (ESM) acquiring to provide sufficient detail and reliability frequently bring along problems of both high intricacy and increasing scale. Unfortunately, the size and complexity of these problems often prove to be intractable even for commercial state-of-the-art linear programming solvers. This article describes an interdisciplinary approach to exploit the intrinsic structure of these large-scale linear problems to be able to solve them on massively parallel high-performance computers. A key aspect are extensions to the parallel interior-point solver PIPS-IPM originally developed for stochastic optimization problems. Furthermore, a newly developed GAMS interface to the solver as well as some GAMS language extensions to model block-structured problems will be described. T3 - ZIB-Report - 17-75 KW - energy system models KW - interior-point methods KW - high-performance computing Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-66183 SN - 1438-0064 ER - TY - GEN A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - SCIP-Jack—a solver for STP and variants with parallelization extensions: An update N2 - The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. Although the different Steiner tree problem variants are usually strongly related, solution approaches employed so far have been prevalently problem-specific. Against this backdrop, the solver SCIP-Jack was created as a general-purpose framework that can be used to solve the classical Steiner tree problem and 11 of its variants. This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. Furthermore, SCIP-Jack includes various newly developed algorithmic components such as preprocessing routines and heuristics. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances. After the introduction of SCIP-Jack at the 2014 DIMACS Challenge on Steiner problems, the overall performance of the solver has considerably improved. This article provides an overview on the current state. T3 - ZIB-Report - 18-05 Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-66416 SN - 1438-0064 ER - TY - JOUR A1 - Berthold, Timo A1 - Hendel, Gregor A1 - Koch, Thorsten T1 - From feasibility to improvement to proof: three phases of solving mixed-integer programs JF - Optimization Methods and Software N2 - Modern mixed-integer programming (MIP) solvers employ dozens of auxiliary algorithmic components to support the branch-and-bound search in finding and improving primal solutions and in strengthening the dual bound. Typically, all components are tuned to minimize the average running time to prove optimality. In this article, we take a different look at the run of a MIP solver. We argue that the solution process consists of three distinct phases, namely achieving feasibility, improving the incumbent solution, and proving optimality. We first show that the entire solving process can be improved by adapting the search strategy with respect to the phase-specific aims using different control tunings. Afterwards, we provide criteria to predict the transition between the individual phases and evaluate the performance impact of altering the algorithmic behaviour of the non-commercial MIP solver Scip at the predicted phase transition points. Y1 - 2017 U6 - https://doi.org/10.1080/10556788.2017.1392519 VL - 33 IS - 3 SP - 499 EP - 517 PB - Taylor & Francis ER - TY - JOUR A1 - Koch, Thorsten T1 - The ZIMPL modeling language JF - Optima Y1 - 2017 UR - http://www.mathopt.org/Optima-Issues/optima103.pdf VL - 103 SP - 8 EP - 9 ER - TY - GEN A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem N2 - Borne out of a surprising variety of practical applications, the maximum-weight connected subgraph problem has attracted considerable interest during the past years. This interest has not only led to notable research on theoretical properties, but has also brought about several (exact) solvers-with steadily increasing performance. Continuing along this path, the following article introduces several new algorithms such as reduction techniques and heuristics and describes their integration into an exact solver. The new methods are evaluated with respect to both their theoretical and practical properties. Notably, the new exact framework allows to solve common problem instances from the literature faster than all previous approaches. Moreover, one large-scale benchmark instance from the 11th DIMACS Challenge can be solved for the first time to optimality and the primal-dual gap for two other ones can be significantly reduced. T3 - ZIB-Report - 17-45 KW - maximum-weight connected subgraph Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64699 SN - 1438-0064 ER - TY - JOUR A1 - Rehfeldt, Daniel A1 - Koch, Thorsten A1 - Maher, Stephen J. T1 - Reduction Techniques for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem JF - Networks N2 - The concept of reduction has frequently distinguished itself as a pivotal ingredient of exact solving approaches for the Steiner tree problem in graphs. In this paper we broaden the focus and consider reduction techniques for three Steiner problem variants that have been extensively discussed in the literature and entail various practical applications: The prize-collecting Steiner tree problem, the rooted prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem. By introducing and subsequently deploying numerous new reduction methods, we are able to drastically decrease the size of a large number of benchmark instances, already solving more than 90 percent of them to optimality. Furthermore, we demonstrate the impact of these techniques on exact solving, using the example of the state-of-the-art Steiner problem solver SCIP-Jack. Y1 - 2019 U6 - https://doi.org/10.1002/net.21857 VL - 73 SP - 206 EP - 233 PB - Wiley ET - 2 ER - TY - JOUR A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Transformations for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem to SAP JF - Journal of Computational Mathematics N2 - Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art solvers for well-known variants such as the Steiner tree problem in graphs. In this paper transformations for both the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to the Steiner arborescence problem are introduced for the first time. Furthermore, we demonstrate the considerable implications for practical solving approaches, including the computation of strong upper and lower bounds. Y1 - 2018 U6 - https://doi.org/10.4208/jcm.1709-m2017-0002 VL - 36 IS - 3 SP - 459 EP - 468 ER - TY - CHAP A1 - Gamrath, Gerald A1 - Melchiori, Anna A1 - Berthold, Timo A1 - Gleixner, Ambros A1 - Salvagnin, Domenico T1 - Branching on Multi-aggregated Variables T2 - Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2015 N2 - In mixed-integer programming, the branching rule is a key component to a fast convergence of the branch-and-bound algorithm. The most common strategy is to branch on simple disjunctions that split the domain of a single integer variable into two disjoint intervals. Multi-aggregation is a presolving step that replaces variables by an affine linear sum of other variables, thereby reducing the problem size. While this simplification typically improves the performance of MIP solvers, it also restricts the degree of freedom in variable-based branching rules. We present a novel branching scheme that tries to overcome the above drawback by considering general disjunctions defined by multi-aggregated variables in addition to the standard disjunctions based on single variables. This natural idea results in a hybrid between variable- and constraint-based branching rules. Our implementation within the constraint integer programming framework SCIP incorporates this into a full strong branching rule and reduces the number of branch-and-bound nodes on a general test set of publicly available benchmark instances. For a specific class of problems, we show that the solving time decreases significantly. Y1 - 2015 U6 - https://doi.org/10.1007/978-3-319-18008-3_10 VL - 9075 SP - 141 EP - 156 ER - TY - JOUR A1 - Berthold, Timo A1 - Hendel, Gregor T1 - Shift-and-Propagate JF - Journal of Heuristics N2 - In recent years, there has been a growing interest in the design of general purpose primal heuristics for use inside complete mixed integer programming solvers. Many of these heuristics rely on an optimal LP solution, which may take a significant amount of time to find. In this paper, we address this issue by introducing a pre-root primal heuristic that does not require a previously found LP solution. This heuristic, named Shift-and-Propagate , applies domain propagation techniques to quickly drive a variable assignment towards feasibility. Computational experiments indicate that this heuristic is a powerful supplement to existing rounding and propagation heuristics. Y1 - 2014 U6 - https://doi.org/10.1007/s10732-014-9271-0 VL - 21 IS - 1 SP - 73 EP - 106 ER - TY - GEN A1 - Gamrath, Gerald A1 - Koch, Thorsten A1 - Rehfeldt, Daniel A1 - Shinano, Yuji T1 - SCIP-Jack - A massively parallel STP solver N2 - In this article we describe the impact from embedding a 15 year old model for solving the Steiner tree problem in graphs in a state-of-the-art MIP-Framework, making the result run in a massively parallel environment and extending the model to solve as many variants as possible. We end up with a high-perfomance solver that is capable of solving previously unsolved instances and, in contrast to its predecessor, is freely available for academic research. T3 - ZIB-Report - 14-35 KW - Steiner Tree Problem KW - Mixed-Integer Programming KW - Branch-and-Cut KW - DIMACS Challenge Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-52293 SN - 1438-0064 ER - TY - JOUR A1 - Humpola, Jesco A1 - Lehmann, Thomas A1 - Fügenschuh, Armin T1 - A primal heuristic for optimizing the topology of gas networks based on dual information JF - EURO Journal on Computational Optimization N2 - We present a novel heuristic to identify feasible solutions of a mixed-integer nonlinear programming problem arising in natural gas transportation: the selection of new pipelines to enhance the network's capacity to a desired level in a cost-efficient way. We solve this problem in a linear programming based branch-and-cut approach, where we deal with the nonlinearities by linear outer approximation and spatial branching. At certain nodes of the branching tree, we compute a KKT point of a nonlinear relaxation. Based on the information from the KKT point we alter some of the binary variables in a locally promising way exploiting our problem-specific structure. On a test set of real-world instances, we are able to increase the chance of identifying feasible solutions by some order of magnitude compared to standard MINLP heuristics that are already built in the general-purpose MINLP solver SCIP. Y1 - 2015 U6 - https://doi.org/10.1007/s13675-014-0029-0 VL - 3 IS - 1 SP - 53 EP - 78 ER - TY - CHAP A1 - Matuschke, Jannik A1 - Bley, Andreas A1 - Müller, Benjamin ED - Bodlaender, Hans L. ED - Italiano, Giuseppe F. T1 - Approximation Algorithms for Facility Location with Capacitated and Length-Bounded Tree Connections N2 - We consider a generalization of the uncapacitated facility location problem that occurs in planning of optical access networks in telecommunications. Clients are connected to open facilities via depth-bounded trees. The total demand of clients served by a tree must not exceed a given tree capacity. We investigate a framework for combining facility location algorithms with a tree-based clustering approach and derive approximation algorithms for several variants of the problem, using techniques for approximating shallow-light Steiner trees via layer graphs, simultaneous approximation of shortest paths and minimum spanning trees, and greedy coverings. Y1 - 2013 U6 - https://doi.org/10.1007/978-3-642-40450-4_60 VL - Algorithms -- ESA 2013 SP - 707 EP - 718 PB - Springer ER - TY - JOUR A1 - Maher, Stephen J. T1 - Solving the integrated airline recovery problem using column-and-row generation JF - Transportation Science N2 - Airline recovery presents very large and difficult problems requiring high quality solutions within very short time limits. To improve computational performance, the complete airline recovery problem is generally formulated as a series of sequential stages. While the sequential approach greatly simplifies the complete recovery problem, there is no guarantee of global optimality or solution quality. To address this, there has been increasing interest in the development of efficient solution techniques to solve an integrated recovery problem. In this paper, an integrated airline recovery problem is proposed by integrating the schedule, crew and aircraft recovery stages. To achieve short runtimes and high quality solutions, this problem is solved using column-and-row generation. Column-and-row generation achieves an improvement in solution runtimes by reducing the problem size and thereby achieving a faster execution of each LP solve. Further, the results demonstrate that a good upper bound achieved early in the solution process, indicating an improved solution quality with the early termination of the algorithm. This paper also details the integration of the row generation procedure with branch-and-price, which is used to achieve integral optimal solutions. The benefits of applying column-and-row generation to solve the integrated recovery problem are demonstrated with a comparison to a standard column generation technique. Y1 - 2015 U6 - https://doi.org/10.1287/trsc.2014.0552 VL - 50 IS - 1 SP - 216 EP - 239 ER - TY - GEN A1 - Arnold, Thomas A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Vigerske, Stefan A1 - Henrion, René A1 - Grötschel, Martin A1 - Koch, Thorsten A1 - Tischendorf, Caren A1 - Römisch, Werner ED - Deuflhard, Peter ED - Grötschel, Martin ED - Hömberg, Dietmar ED - Horst, Ulrich ED - Kramer, Jürg ED - Mehrmann, Volker ED - Polthier, Konrad ED - Schmidt, Frank ED - Schütte, Christof ED - Skutella, Martin ED - Sprekels, Jürgen T1 - A Jack of all Trades? Solving stochastic mixed-integer nonlinear constraint programs T2 - MATHEON - Mathematics for Key Technologies N2 - Natural gas is one of the most important energy sources in Germany and Europe. In recent years, political regulations have led to a strict separation of gas trading and gas transport, thereby assigning a central role in energy politics to the transportation and distribution of gas. These newly imposed political requirements influenced the technical processes of gas transport in such a way that the complex task of planning and operating gas networks has become even more intricate. Mathematically, the combination of discrete decisions on the configuration of a gas transport network, the nonlinear equations describing the physics of gas, and the uncertainty in demand and supply yield large-scale and highly complex stochastic mixed-integer nonlinear optimization problems. The Matheon project "Optimization of Gas Transport" takes the key role of making available the necessary core technology to solve the mathematical optimization problems which model the topology planning and the operation of gas networks. An important aspect of the academic impact is the free availability of our framework. As a result of several years of research and development, it is now possible to download a complete state-of-the-art framework for mixed-integer linear and nonlinear programming in source code at http://scip.zib.de Y1 - 2014 U6 - https://doi.org/10.4171/137 VL - 1 SP - 135 EP - 146 PB - European Mathematical Society ER - TY - JOUR A1 - Cook, William A1 - Koch, Thorsten A1 - Steffy, Daniel A1 - Wolter, Kati T1 - A hybrid branch-and-bound approach for exact rational mixed-integer programming JF - Mathematical Programming Computation N2 - We present an exact rational solver for mixed-integer linear programming that avoids the numerical inaccuracies inherent in the floating-point computations used by existing software. This allows the solver to be used for establishing theoretical results and in applications where correct solutions are critical due to legal and financial consequences. Our solver is a hybrid symbolic/numeric implementation of LP-based branch-and-bound, using numerically-safe methods for all binding computations in the search tree. Computing provably accurate solutions by dynamically choosing the fastest of several safe dual bounding methods depending on the structure of the instance, our exact solver is only moderately slower than an inexact floating-point branch-and-bound solver. The software is incorporated into the SCIP optimization framework, using the exact LP solver QSopt_ex and the GMP arithmetic library. Computational results are presented for a suite of test instances taken from the MIPLIB and Mittelmann libraries and for a new collection of numerically difficult instances. Y1 - 2013 U6 - https://doi.org/10.1007/s12532-013-0055-6 VL - 5 IS - 3 SP - 305 EP - 344 ER - TY - GEN A1 - Ralphs, Ted A1 - Shinano, Yuji A1 - Berthold, Timo A1 - Koch, Thorsten T1 - Parallel Solvers for Mixed Integer Linear Programming N2 - In this article, we introduce parallel mixed integer linear programming (MILP) solvers. MILP solving algorithms have been improved tremendously in the last two decades. Currently, commercial MILP solvers are known as a strong optimization tool. Parallel MILP solver development has started in 1990s. However, since the improvements of solving algorithms have much impact to solve MILP problems than application of parallel computing, there were not many visible successes. With the spread of multi-core CPUs, current state-of-the-art MILP solvers have parallel implementations and researches to apply parallelism in the solving algorithm also getting popular. We summarize current existing parallel MILP solver architectures. T3 - ZIB-Report - 16-74 KW - parallel computing KW - integer programming KW - branch-and-bound KW - supercomputing Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-62239 SN - 1438-0064 ER - TY - CHAP A1 - Witzig, Jakob A1 - Berthold, Timo A1 - Heinz, Stefan T1 - Experiments with Conflict Analysis in Mixed Integer Programming T2 - Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2017 N2 - The analysis of infeasible subproblems plays an import role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. There are two fundamentally different concepts to generate valid global constraints from infeasible subproblems. The first is to analyze the sequence of implications obtained by domain propagation that led to infeasibility. The result of the analysis is one or more sets of contradicting variable bounds from which so-called conflict constraints can be generated. This concept has its origin in solving satisfiability problems and is similarly used in constraint programming. The second concept is to analyze infeasible linear programming (LP) relaxations. The dual LP solution provides a set of multipliers that can be used to generate a single new globally valid linear constraint. The main contribution of this short paper is an empirical evaluation of two ways to combine both approaches. Experiments are carried out on general MIP instances from standard public test sets such as Miplib2010; the presented algorithms have been implemented within the non-commercial MIP solver SCIP. Moreover, we present a pool-based approach to manage conflicts which addresses the way a MIP solver traverses the search tree better than aging strategies known from SAT solving. Y1 - 2017 U6 - https://doi.org/10.1007/978-3-319-59776-8_17 VL - 10335 SP - 211 EP - 222 PB - Springer ER - TY - JOUR A1 - Vigerske, Stefan A1 - Gleixner, Ambros T1 - SCIP: Global Optimization of Mixed-Integer Nonlinear Programs in a Branch-and-Cut Framework JF - Optimization Methods & Software N2 - This paper describes the extensions that were added to the constraint integer programming framework SCIP in order to enable it to solve convex and nonconvex mixed-integer nonlinear programs (MINLPs) to global optimality. SCIP implements a spatial branch-and-bound algorithm based on a linear outer-approximation, which is computed by convex over- and underestimation of nonconvex functions. An expression graph representation of nonlinear constraints allows for bound tightening, structure analysis, and reformulation. Primal heuristics are employed throughout the solving process to find feasible solutions early. We provide insights into the performance impact of individual MINLP solver components via a detailed computational study over a large and heterogeneous test set. Y1 - 2018 U6 - https://doi.org/10.1080/10556788.2017.1335312 VL - 33 IS - 3 SP - 563 EP - 593 ER - TY - THES A1 - Viernickel, Jan Merlin T1 - Abschätzung der Suchbaumgröße und Laufzeit für Branch-and-Bound Algorithmen Y1 - 2016 ER - TY - THES A1 - Gottwald, Robert Lion T1 - Experiments with Concurrency and Heuristics in SCIP Y1 - 2016 ER - TY - THES A1 - Roessig, Ansgar T1 - Formulations and algorithms for the USCCSP Y1 - 2016 ER - TY - THES A1 - Teuchert, Andreas T1 - Degeneriertheit im Simplexverfahren Y1 - 2017 ER - TY - GEN A1 - Hendel, Gregor T1 - Exploiting Solving Phases for Mixed-Integer Programs N2 - Modern MIP solving software incorporates dozens of auxiliary algorithmic components for supporting the branch-and-bound search in finding and improving solutions and in strengthening the relaxation. Intuitively, a dynamic solving strategy with an appropriate emphasis on different solving components and strategies is desirable during the search process. We propose an adaptive solver behavior that dynamically reacts on transitions between the three typical phases of a MIP solving process: The first phase objective is to find a feasible solution. During the second phase, a sequence of incumbent solutions gets constructed until the incumbent is eventually optimal. Proving optimality is the central objective of the remaining third phase. Based on the MIP-solver SCIP, we demonstrate the usefulness of the phase concept both with an exact recognition of the optimality of a solution, and provide heuristic alternatives to make use of the concept in practice. T3 - ZIB-Report - 15-64 KW - Branch-and-Bound, Mixed-Integer Programming Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57098 SN - 1438-0064 ER - TY - GEN A1 - Yokoyama, Ryohei A1 - Shinano, Yuji A1 - Taniguchi, Syusuke A1 - Ohkura, Masashi A1 - Wakui, Tetsuya T1 - Optimization of energy supply systems by MILP branch and bound method in consideration of hierarchical relationship between design and operation N2 - To attain the highest performance of energy supply systems, it is necessary to rationally determine types, capacities, and numbers of equipment in consideration of their operational strategies corresponding to seasonal and hourly variations in energy demands. In the combinatorial optimization method based on the mixed-integer linear programming (MILP), integer variables are used to express the selection, numbers, and on/off status of operation of equipment, and the number of these variables increases with those of equipment and periods for variations in energy demands, and affects the computation efficiency significantly. In this paper, a MILP method utilizing the hierarchical relationship between design and operation variables is proposed to solve the optimal design problem of energy supply systems efficiently: At the upper level, the optimal values of design variables are searched by the branch and bound method; At the lower level, the values of operation variables are optimized independently at each period by the branch and bound method under the values of design variables given tentatively during the search at the upper level; Lower bounds for the optimal value of the objective function are evaluated, and are utilized for the bounding operations at both the levels. This method is implemented into open and commercial MILP solvers. Illustrative and practical case studies on the optimal design of cogeneration systems are conducted, and the validity and effectiveness of the proposed method are clarified. T3 - ZIB-Report - 14-09 KW - Energy supply systems KW - Optimal design KW - Optimal operation KW - Mixed-integer linear programming KW - Branch and bound method KW - Hierarchical approach Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-49413 SN - 1438-0064 ER - TY - JOUR A1 - Shinano, Yuji A1 - Inui, Nobuo A1 - Fukagawa, Youzou A1 - Takakura, Noburu T1 - Optimizing Movement Sequences for Step-and-Scan Lithography Equipment JF - Journal of Advanced Mechanical Design, Systems, and Manufacturing N2 - The purpose of this work is to improve the throughput of step-and-scan lithography equipment to shorten the production time of a wafer. For this purpose, we propose a method for solving the MSOP (Movement Sequence Optimization Problem), which is the problem of computing the fastest schedule for visiting all shots on a wafer. It is well-known that the MSOP on step-and-repeat lithography equipment can be modeled as a traveling salesman problem. In contrast to step-and-repeat lithography equipment, a schedule for step-and-scan lithography equipment must also indicate the scanning direction of each shot, in addition to the sequence of the shots. For this reason, the traveling salesman problem formulation for step-and-repeat lithography equipment cannot be applied to solve the MSOP on step-and-scan lithography equipment directly. We overcame this difficulty by introducing auxiliary vertices to model the scanning directions in the traveling salesman problem formulation. By this method, we were able to compute exact optimal sequences considering the scanning directions of shots for several MSOP instances. Our numerical experiments demonstrated that our proposed method was capable of computing exact optimal solutions for real-world MSOP instances having up to 232 shots on a wafer. These optimal solutions gave a 0.25% to 4.66% improvement in productivity over solutions computed by previously known methods. Y1 - 2013 U6 - https://doi.org/10.1299/jamdsm.7.608 VL - 7 IS - 4 SP - 608 EP - 618 ER - TY - GEN A1 - Gleixner, Ambros A1 - Steffy, Daniel A1 - Wolter, Kati T1 - Iterative Refinement for Linear Programming N2 - We describe an iterative refinement procedure for computing extended precision or exact solutions to linear programming problems (LPs). Arbitrarily precise solutions can be computed by solving a sequence of closely related LPs with limited precision arithmetic. The LPs solved share the same constraint matrix as the original problem instance and are transformed only by modification of the objective function, right-hand side, and variable bounds. Exact computation is used to compute and store the exact representation of the transformed problems, while numeric computation is used for solving LPs. At all steps of the algorithm the LP bases encountered in the transformed problems correspond directly to LP bases in the original problem description. We show that this algorithm is effective in practice for computing extended precision solutions and that it leads to a direct improvement of the best known methods for solving LPs exactly over the rational numbers. Our implementation is publically available as an extension of the academic LP solver SoPlex. T3 - ZIB-Report - 15-15 Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-55118 SN - 1438-0064 ER - TY - GEN A1 - Gamrath, Gerald A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Winkler, Michael T1 - Structure-based primal heuristics for mixed integer programming N2 - Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They help to reach optimality faster and provide good feasible solutions early in the solving process. In this paper, we present two new primal heuristics which take into account global structures available within MIP solvers to construct feasible solutions at the beginning of the solving process. These heuristics follow a large neighborhood search (LNS) approach and use global structures to define a neighborhood that is with high probability significantly easier to process while (hopefully) still containing good feasible solutions. The definition of the neighborhood is done by iteratively fixing variables and propagating these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. The neighborhood is solved as a sub-MIP and solutions are transferred back to the original problem. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about every third instance and therewith help to improve the average solving time. T3 - ZIB-Report - 15-26 KW - mixed-integer programming, large neighborhood search, primal heuristics, domain propagation Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-55518 SN - 1438-0064 ER - TY - JOUR A1 - Maher, Stephen J. A1 - Murray, John M. T1 - The unrooted set covering connected subgraph problem differentiating between HIV envelope sequences JF - European Journal of Operational Research N2 - This paper presents a novel application of operations research techniques to the analysis of HIV Env gene sequences, aiming to identify key features that are possible vaccine targets. These targets are identified as being critical to the transmission of HIV by being present in early transmitted (founder) sequences and absent in later chronic sequences. Identifying the key features of Env involves two steps: first, calculating the covariance of amino acid combinations and positions to form a network of related and compensatory mutations; and second, developing an integer program to identify the smallest connected subgraph of the constructed covariance network that exhibits a set covering property. The integer program developed for this analysis, labelled the unrooted set covering connected subgraph problem (USCCSP), integrates a set covering problem and connectivity evaluation, the latter formulated as a network flow problem. The resulting integer program is very large and complex, requiring the use of Benders' decomposition to develop an efficient solution approach. The results will demonstrate the necessity of applying acceleration techniques to the Benders' decomposition solution approach and the effectiveness of these techniques and heuristic approaches for solving the USCCSP. Y1 - 2016 U6 - https://doi.org/doi:10.1016/j.ejor.2015.07.011 VL - 248 IS - 2 SP - 668 EP - 680 ER -