@misc{GamrathFischerGallyetal.2016, author = {Gamrath, Gerald and Fischer, Tobias and Gally, Tristan and Gleixner, Ambros and Hendel, Gregor and Koch, Thorsten and Maher, Stephen J. and Miltenberger, Matthias and M{\"u}ller, Benjamin and Pfetsch, Marc and Puchert, Christian and Rehfeldt, Daniel and Schenker, Sebastian and Schwarz, Robert and Serrano, Felipe and Shinano, Yuji and Vigerske, Stefan and Weninger, Dieter and Winkler, Michael and Witt, Jonas T. and Witzig, Jakob}, title = {The SCIP Optimization Suite 3.2}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-57675}, year = {2016}, abstract = {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.}, language = {en} } @misc{BallersteinMichaelsVigerske2013, author = {Ballerstein, Martin and Michaels, Dennis and Vigerske, Stefan}, title = {Linear Underestimators for bivariate functions with a fixed convexity behavior}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17641}, year = {2013}, abstract = {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.}, language = {en} } @misc{BertholdHendel2013, author = {Berthold, Timo and Hendel, Gregor}, title = {Shift-And-Propagate}, issn = {1438-0064}, doi = {10.1007/s10732-014-9271-0}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17596}, year = {2013}, abstract = {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.}, language = {en} } @article{GamrathKochMaheretal.2017, author = {Gamrath, Gerald and Koch, Thorsten and Maher, Stephen J. and Rehfeldt, Daniel and Shinano, Yuji}, title = {SCIP-Jack - A solver for STP and variants with parallelization extensions}, volume = {9}, journal = {Mathematical Programming Computation}, number = {2}, doi = {10.1007/s12532-016-0114-x}, pages = {231 -- 296}, year = {2017}, abstract = {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.}, language = {en} } @inproceedings{ShinanoBertholdHeinz2016, author = {Shinano, Yuji and Berthold, Timo and Heinz, Stefan}, title = {A First Implementation of ParaXpress: Combining Internal and External Parallelization to Solve MIPs on Supercomputers}, booktitle = {Mathematical Software - ICMS 2016, 5th International Conference Berlin, Germany, July 11-14, 2016 Proceedings}, doi = {10.1007/978-3-319-42432-3_38}, pages = {308 -- 316}, year = {2016}, language = {en} } @book{GreuelKochPauleetal.2016, author = {Greuel, Martin and Koch, Thorsten and Paule, Peter and Sommese, Andrew}, title = {Mathematical Software - ICMS 2016, 5th Int. Conf. Berlin, Germany, July 11-14, 2016, Proceedings}, volume = {9725}, journal = {Lecture Notes in Computer Science (LNCS)}, publisher = {Springer}, isbn = {978-3-319-42431-6}, doi = {10.1007/978-3-319-42432-3}, pages = {XXIV, 532}, year = {2016}, language = {en} } @inproceedings{BertholdFarmerHeinzetal.2016, author = {Berthold, Timo and Farmer, James and Heinz, Stefan and Perregaard, Michael}, title = {Parallelization of the FICO Xpress-Optimizer}, booktitle = {Mathematical Software - ICMS 2016, 5th International Conference Berlin, Germany, July 11-14, 2016 Proceedings}, doi = {10.1007/978-3-319-42432-3_31}, pages = {251 -- 258}, year = {2016}, language = {en} } @inproceedings{ChraparyRen2016, author = {Chrapary, Hagen and Ren, Yue}, title = {The Software Portal swMATH: A State of the Art Report and Next Steps}, booktitle = {Mathematical Software - ICMS 2016, 5th International Conference Berlin, Germany, July 11-14, 2016 Proceedings}, doi = {10.1007/978-3-319-42432-3_49}, pages = {397 -- 402}, year = {2016}, language = {en} } @incollection{WuMaher2017, author = {Wu, Cheng-Lung and Maher, Stephen J.}, title = {Airline scheduling and disruption management}, booktitle = {L. Budd, S. Ison, eds., Air transportation management: an international perspective}, publisher = {Routledge}, address = {New York}, isbn = {9781472451064}, pages = {151 -- 167}, year = {2017}, language = {en} } @article{GleixnerBertholdMuelleretal.2017, author = {Gleixner, Ambros and Berthold, Timo and M{\"u}ller, Benjamin and Weltge, Stefan}, title = {Three Enhancements for Optimization-Based Bound Tightening}, volume = {67}, journal = {Journal of Global Optimization}, number = {4}, doi = {10.1007/s10898-016-0450-4}, pages = {731 -- 757}, year = {2017}, abstract = {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.}, language = {en} } @inproceedings{YokoyamaNakamuraWakuietal.2016, author = {Yokoyama, Ryohei and Nakamura, Ryo and Wakui, Tetsuya and Shinano, Yuji}, title = {Evaluation of Performance Robustness of a Gas Turbine Cogeneration Plant Based on a Mixed-Integer Linear Model}, volume = {3}, booktitle = {ASME Turbo Expo 2016: Turbomachinery Technical Conference and Exposition}, doi = {doi:10.1115/GT2016-56217}, pages = {1 -- 9}, year = {2016}, abstract = {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.}, language = {en} } @article{MaherDesaulniersSoumis2018, author = {Maher, Stephen J. and Desaulniers, Guy and Soumis, Francois}, title = {The daily tail assignment problem under operational uncertainty using look-ahead maintenance constraints}, volume = {264}, journal = {European Journal of Operational Research}, number = {2}, doi = {10.1016/j.ejor.2017.06.041}, pages = {534 -- 547}, year = {2018}, abstract = {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.}, language = {en} } @article{ShinanoHeinzVigerskeetal.2018, author = {Shinano, Yuji and Heinz, Stefan and Vigerske, Stefan and Winkler, Michael}, title = {FiberSCIP - A shared memory parallelization of SCIP}, volume = {30}, journal = {INFORMS Journal on Computing}, number = {1}, doi = {10.1287/ijoc.2017.0762}, pages = {11 -- 30}, year = {2018}, abstract = {Recently, parallel computing environments have become significantly popular. In order to obtain the benefit of using parallel computing environments, we have to deploy our programs for these effectively. This paper focuses on a parallelization of SCIP (Solving Constraint Integer Programs), which is a 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.}, language = {en} } @inproceedings{YokoyamaShinanoWakayamaetal.2017, author = {Yokoyama, Ryohei and Shinano, Yuji and Wakayama, Yuki and Wakui, Tetsuya}, title = {Multiobjective Optimal Design of a Gas Turbine Cogeneration Plant by a Revised Hierarchical Optimization Method}, volume = {3}, booktitle = {ASME Turbo Expo 2017: Turbomachinery Technical Conference and Exposition}, doi = {doi:10.1115/GT2017-64296}, pages = {1 -- 14}, year = {2017}, abstract = {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.}, language = {en} } @inproceedings{Shinano2018, author = {Shinano, Yuji}, title = {The Ubiquity Generator Framework: 7 Years of Progress in Parallelizing Branch-and-Bound}, booktitle = {Operations Research Proceedings 2017}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-319-89920-6_20}, pages = {143 -- 149}, year = {2018}, abstract = {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.}, language = {en} } @inproceedings{GamrathSchubert2018, author = {Gamrath, Gerald and Schubert, Christoph}, title = {Measuring the impact of branching rules for mixed-integer programming}, booktitle = {Operations Research Proceedings 2017}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-319-89920-6_23}, pages = {165 -- 170}, year = {2018}, abstract = {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.}, language = {en} } @article{ShinanoBertholdHeinz2018, author = {Shinano, Yuji and Berthold, Timo and Heinz, Stefan}, title = {ParaXpress: An Experimental Extension of the FICO Xpress-Optimizer to Solve Hard MIPs on Supercomputers}, volume = {33}, journal = {Optimization Methods \& Software}, number = {3}, doi = {10.1080/10556788.2018.1428602}, pages = {530 -- 539}, year = {2018}, abstract = {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.}, language = {en} } @misc{Schubert2017, type = {Master Thesis}, author = {Schubert, Christoph}, title = {Multi-Level Lookahead Branching}, year = {2017}, language = {en} } @misc{GamrathGleixnerKochetal.2016, author = {Gamrath, Gerald and Gleixner, Ambros and Koch, Thorsten and Miltenberger, Matthias and Kniasew, Dimitri and Schl{\"o}gel, Dominik and Martin, Alexander and Weninger, Dieter}, title = {Tackling Industrial-Scale Supply Chain Problems by Mixed-Integer Programming}, issn = {1438-0064}, doi = {10.4208/jcm.1905-m2019-0055}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61107}, year = {2016}, abstract = {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.}, language = {en} } @misc{GottwaldMaherShinano2016, author = {Gottwald, Robert Lion and Maher, Stephen J. and Shinano, Yuji}, title = {Distributed domain propagation}, issn = {1438-0064}, doi = {10.4230/LIPIcs.SEA.2017.6}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61380}, year = {2016}, abstract = {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.}, language = {en} } @misc{GamrathKochMaheretal.2015, author = {Gamrath, Gerald and Koch, Thorsten and Maher, Stephen J. and Rehfeldt, Daniel and Shinano, Yuji}, title = {SCIP-Jack - A solver for STP and variants with parallelization extensions}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-54648}, year = {2015}, abstract = {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.}, language = {en} } @misc{Hendel2015, author = {Hendel, Gregor}, title = {Enhancing MIP branching decisions by using the sample variance of pseudo-costs}, issn = {1438-0064}, doi = {10.1007/978-3-319-18008-3_14}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-54591}, year = {2015}, abstract = {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.}, language = {en} } @inproceedings{Hendel2015, author = {Hendel, Gregor}, title = {Enhancing MIP Branching Decisions by Using the Sample Variance of Pseudo Costs}, volume = {9075}, booktitle = {Integration of AI and OR Techniques in Constraint Programming}, doi = {10.1007/978-3-319-18008-3_14}, pages = {199 -- 214}, year = {2015}, abstract = {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.}, language = {en} } @misc{GamrathSchubert2017, author = {Gamrath, Gerald and Schubert, Christoph}, title = {Measuring the impact of branching rules for mixed-integer programming}, issn = {1438-0064}, doi = {10.1007/978-3-319-89920-6_23}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64722}, year = {2017}, abstract = {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.}, language = {en} } @misc{RehfeldtKoch2017, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {Generalized preprocessing techniques for Steiner tree and maximum-weight connected subgraph problems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-65439}, year = {2017}, abstract = {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.}, language = {en} } @misc{BertholdPerregaardMeszaros2017, author = {Berthold, Timo and Perregaard, Michael and M{\´e}sz{\´a}ros, Csaba}, title = {Four good reasons to use an Interior Point solver within a MIP solver}, issn = {1438-0064}, doi = {10.1007/978-3-319-89920-6_22}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64599}, year = {2017}, abstract = {"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.}, language = {en} } @misc{MiltenbergerRalphsSteffy2017, author = {Miltenberger, Matthias and Ralphs, Ted and Steffy, Daniel}, title = {Exploring the Numerics of Branch-and-Cut for Mixed Integer Linear Optimization}, journal = {Operations Research Proceedings 2017}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64645}, year = {2017}, abstract = {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.}, language = {en} } @misc{SchadeSchlechteWitzig2017, author = {Schade, Stanley and Schlechte, Thomas and Witzig, Jakob}, title = {Structure-based Decomposition for Pattern-Detection for Railway Timetables}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64525}, year = {2017}, abstract = {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.}, language = {en} } @inproceedings{MiltenbergerRalphsSteffy2018, author = {Miltenberger, Matthias and Ralphs, Ted and Steffy, Daniel}, title = {Exploring the Numerics of Branch-and-Cut for Mixed Integer Linear Optimization}, booktitle = {Operations Research Proceedings 2017}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-319-89920-6}, pages = {151 -- 157}, year = {2018}, abstract = {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.}, language = {en} } @inproceedings{YokoyamaShinanoTaniguchietal.2015, author = {Yokoyama, Ryohei and Shinano, Yuji and Taniguchi, Syusuke and Ohkura, Masashi and Wakui, Tetsuya}, title = {Generation of multiple best solutions in multiobjective optimal design of energy supply systems}, booktitle = {Proceedings of the 15th International Conference on Power Engineering. ICOPE 2015}, doi = {10.1299/jsmeicope.2015.12._ICOPE-15-_56}, year = {2015}, abstract = {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.}, language = {en} } @article{GleixnerSteffyWolter2016, author = {Gleixner, Ambros and Steffy, Daniel and Wolter, Kati}, title = {Iterative Refinement for Linear Programming}, volume = {28}, journal = {INFORMS Journal on Computing}, number = {3}, doi = {10.1287/ijoc.2016.0692}, pages = {449 -- 464}, year = {2016}, abstract = {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.}, language = {en} } @inproceedings{Hendel2016, author = {Hendel, Gregor}, title = {Exploiting Solving Phases for Mixed-Integer Programs}, booktitle = {Operations Research Proceedings 2015}, doi = {10.1007/978-3-319-42902-1_1}, pages = {3 -- 9}, year = {2016}, abstract = {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.}, language = {en} } @inproceedings{ShinanoAchterbergBertholdetal.2016, author = {Shinano, Yuji and Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten and Winkler, Michael}, title = {Solving Open MIP Instances with ParaSCIP on Supercomputers using up to 80,000 Cores}, booktitle = {Proc. of 30th IEEE International Parallel \& Distributed Processing Symposium}, doi = {10.1109/IPDPS.2016.56}, year = {2016}, abstract = {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.}, language = {en} } @misc{Witzig2017, author = {Witzig, Jakob}, title = {Conflict Driven Diving for Mixed Integer Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-66116}, year = {2017}, abstract = {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.}, language = {en} } @misc{AchterbergBixbyGuetal.2016, author = {Achterberg, Tobias and Bixby, Robert E. and Gu, Zonghao and Rothberg, Edward and Weninger, Dieter}, title = {Presolve Reductions in Mixed Integer Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-60370}, year = {2016}, abstract = {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.}, language = {en} } @misc{RehfeldtKochMaher2016, author = {Rehfeldt, Daniel and Koch, Thorsten and Maher, Stephen J.}, title = {Reduction Techniques for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem}, issn = {1438-0064}, doi = {10.1002/net.21857}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-60420}, year = {2016}, abstract = {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.}, language = {en} } @misc{Pulaj2016, author = {Pulaj, Jonad}, title = {Cutting Planes for Families Implying Frankl's Conjecture}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-60626}, year = {2016}, abstract = {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.}, language = {en} } @misc{WitzigBeckenbachEifleretal.2016, author = {Witzig, Jakob and Beckenbach, Isabel and Eifler, Leon and Fackeldey, Konstantin and Gleixner, Ambros and Grever, Andreas and Weber, Marcus}, title = {Mixed-Integer Programming for Cycle Detection in Non-reversible Markov Processes}, issn = {1438-0064}, doi = {10.1137/16M1091162}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-60353}, year = {2016}, abstract = {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.}, language = {en} } @article{WitzigBeckenbachEifleretal.2018, author = {Witzig, Jakob and Beckenbach, Isabel and Eifler, Leon and Fackeldey, Konstantin and Gleixner, Ambros and Grever, Andreas and Weber, Marcus}, title = {Mixed-Integer Programming for Cycle Detection in Non-reversible Markov Processes}, volume = {16}, journal = {Multiscale Modeling and Simulation}, number = {1}, issn = {1438-0064}, doi = {10.1137/16M1091162}, pages = {248 -- 265}, year = {2018}, abstract = {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.}, language = {en} } @article{Maher2015, author = {Maher, Stephen J.}, title = {A novel passenger recovery approach for the integrated airline recovery problem}, volume = {57}, journal = {Computers \& Operations Research}, doi = {10.1016/j.cor.2014.11.005}, pages = {123 -- 137}, year = {2015}, abstract = {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.}, language = {en} } @misc{AchterbergBertholdHendel2011, author = {Achterberg, Tobias and Berthold, Timo and Hendel, Gregor}, title = {Rounding and Propagation Heuristics for Mixed Integer Programming}, doi = {10.1007/978-3-642-29210-1_12}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-13255}, number = {11-29}, year = {2011}, abstract = {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.}, language = {en} } @inproceedings{BertholdFeydyStuckey2010, author = {Berthold, Timo and Feydy, Thibaut and Stuckey, Peter}, title = {Rapid Learning for Binary Programs}, volume = {6140}, booktitle = {Proc. of CPAIOR 2010}, editor = {Lodi, Andrea and Milano, Michela and Toth, Paolo}, publisher = {Springer}, pages = {51 -- 55}, year = {2010}, language = {en} } @inproceedings{Berthold2008, author = {Berthold, Timo}, title = {Heuristics of the Branch-Cut-and-Price-Framework SCIP}, booktitle = {Operations Research Proceedings 2007}, editor = {Kalcsics, J{\"o}rg and Nickel, Stefan}, publisher = {Springer-Verlag}, pages = {31 -- 36}, year = {2008}, language = {en} } @misc{Berthold2006, type = {Master Thesis}, author = {Berthold, Timo}, title = {Primal Heuristics for Mixed Integer Programs}, year = {2006}, language = {en} } @inproceedings{BertholdHeinzLuebbeckeetal.2010, author = {Berthold, Timo and Heinz, Stefan and L{\"u}bbecke, Marco and M{\"o}hring, Rolf and Schulz, Jens}, title = {A Constraint Integer Programming Approach for Resource-Constrained Project Scheduling}, volume = {6140}, booktitle = {Proc. of CPAIOR 2010}, editor = {Lodi, Andrea and Milano, Michela and Toth, Paolo}, publisher = {Springer}, pages = {313 -- 317}, year = {2010}, language = {en} } @inproceedings{BertholdHeinzPfetsch2009, author = {Berthold, Timo and Heinz, Stefan and Pfetsch, Marc}, title = {Nonlinear pseudo-Boolean optimization}, volume = {5584}, booktitle = {Theory and Applications of Satisfiability Testing - SAT 2009}, editor = {Kullmann, Oliver}, publisher = {Springer}, pages = {441 -- 446}, year = {2009}, language = {en} } @inproceedings{AchterbergBerthold2009, author = {Achterberg, Tobias and Berthold, Timo}, title = {Hybrid Branching}, volume = {5547}, booktitle = {Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 6th International Conference, CPAIOR 2009}, editor = {van Hoeve, Willem and Hooker, John}, publisher = {Springer}, pages = {309 -- 311}, year = {2009}, language = {en} } @inproceedings{BertholdPfetsch2009, author = {Berthold, Timo and Pfetsch, Marc}, title = {Detecting Orbitopal Symmetries}, booktitle = {Operations Research Proceedings 2008}, editor = {Fleischmann, Bernhard and Borgwardt, Karl and Klein, Robert and Tuma, Axel}, publisher = {Springer-Verlag}, pages = {433 -- 438}, year = {2009}, language = {en} } @misc{Gamrath2010, type = {Master Thesis}, author = {Gamrath, Gerald}, title = {Generic Branch-Cut-and-Price}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-57543}, pages = {208}, year = {2010}, abstract = {In this thesis, we present the theoretical background, implementational details and computational results concerning the generic branch-cut-and-price solver GCG.}, language = {en} } @misc{MaherMiltenbergerPedrosoetal.2016, author = {Maher, Stephen J. and Miltenberger, Matthias and Pedroso, Jo{\~a}o Pedro and Rehfeldt, Daniel and Schwarz, Robert and Serrano, Felipe}, title = {PySCIPOpt: Mathematical Programming in Python with the SCIP Optimization Suite}, issn = {1438-0064}, doi = {10.1007/978-3-319-42432-3_37}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61348}, year = {2016}, abstract = {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.}, language = {en} }