@inproceedings{MexiShamsiBesanconetal.2024, author = {Mexi, Gioni and Shamsi, Somayeh and Besan{\c{c}}on, Mathieu and Bodic, Pierre}, title = {Probabilistic Lookahead Strong Branching via a Stochastic Abstract Branching Model}, volume = {14743}, booktitle = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2024}, doi = {10.1007/978-3-031-60599-4_4}, year = {2024}, abstract = {Strong Branching (SB) is a cornerstone of all modern branching rules used in the Branch-and-Bound (BnB) algorithm, which is at the center of Mixed-Integer Programming solvers. In its full form, SB evaluates all variables to branch on and then selects the one producing the best relaxation, leading to small trees, but high runtimes. State-of-the-art branching rules therefore use SB with working limits to achieve both small enough trees and short run times. So far, these working limits have been established empirically. In this paper, we introduce a theoretical approach to guide how much SB to use at each node within the BnB. We first define an abstract stochastic tree model of the BnB algorithm where the geometric mean dual gains of all variables follow a given probability distribution. This model allows us to relate expected dual gains to tree sizes and explicitly compare the cost of sampling an additional SB candidate with the reward in expected tree size reduction. We then leverage the insight from the abstract model to design a new stopping criterion for SB, which fits a distribution to the dual gains and, at each node, dynamically continues or interrupts SB. This algorithm, which we refer to as Probabilistic Lookahead Strong Branching, improves both the tree size and runtime over MIPLIB instances, providing evidence that the method not only changes the amount of SB, but allocates it better.}, language = {en} } @article{EiflerGleixner2024, author = {Eifler, Leon and Gleixner, Ambros}, title = {Safe and verified Gomory mixed integer cuts in a rational MIP framework}, volume = {34}, journal = {SIAM Journal on Optimization}, number = {1}, doi = {10.1137/23M156046X}, year = {2024}, abstract = {This paper is concerned with the exact solution of mixed-integer programs (MIPs) over the rational numbers, i.e., without any roundoff errors and error tolerances. Here, one computational bottleneck that should be avoided whenever possible is to employ large-scale symbolic computations. Instead it is often possible to use safe directed rounding methods, e.g., to generate provably correct dual bounds. In this work, we continue to leverage this paradigm and extend an exact branch-and-bound framework by separation routines for safe cutting planes, based on the approach first introduced by Cook, Dash, Fukasawa, and Goycoolea in 2009 [INFORMS J. Comput., 21 (2009), pp. 641-649]. Constraints are aggregated safely using approximate dual multipliers from an LP solve, followed by mixed-integer rounding to generate provably valid, although slightly weaker inequalities. We generalize this approach to problem data that is not representable in floating-point arithmetic, add routines for controlling the encoding length of the resulting cutting planes, and show how these cutting planes can be verified according to the VIPR certificate standard. Furthermore, we analyze the performance impact of these cutting planes in the context of an exact MIP framework, showing that we can solve 21.5\% more instances to exact optimality and reduce solving times by 26.8\% on the MIPLIB 2017 benchmark test set.}, language = {en} } @inproceedings{GhannamGleixner2023, author = {Ghannam, Mohammed and Gleixner, Ambros}, title = {Hybrid genetic search for dynamic vehicle routing with time windows}, booktitle = {Proceedings of Conference of the Society for Operations Research in Germany}, year = {2023}, language = {en} } @inproceedings{HoenOertelGleixneretal.2024, author = {Hoen, Alexander and Oertel, Andy and Gleixner, Ambros and Nordstr{\"o}m, Jakob}, title = {Certifying MIP-based presolve reductions for 0-1 integer linear programs}, volume = {14742}, booktitle = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2024}, doi = {10.1007/978-3-031-60597-0_20}, year = {2024}, abstract = {It is well known that reformulating the original problem can be crucial for the performance of mixed-integer programming (MIP) solvers. To ensure correctness, all transformations must preserve the feasibility status and optimal value of the problem, but there is currently no established methodology to express and verify the equivalence of two mixed-integer programs. In this work, we take a first step in this direction by showing how the correctness of MIP presolve reductions on - integer linear programs can be certified by using (and suitably extending) the VeriPB tool for pseudo-Boolean proof logging. Our experimental evaluation on both decision and optimization instances demonstrates the computational viability of the approach and leads to suggestions for future revisions of the proof format that will help to reduce the verbosity of the certificates and to accelerate the certification and verification process further.}, language = {en} } @article{EiflerGleixner2023, author = {Eifler, Leon and Gleixner, Ambros}, title = {A computational status update for exact rational mixed integer programming}, volume = {197}, journal = {Mathematical Programming}, doi = {10.1007/s10107-021-01749-5}, pages = {793 -- 812}, year = {2023}, abstract = {The last milestone achievement for the roundoff-error-free solution of general mixed integer programs over the rational numbers was a hybrid-precision branch-and-bound algorithm published by Cook, Koch, Steffy, and Wolter in 2013. We describe a substantial revision and extension of this framework that integrates symbolic presolving, features an exact repair step for solutions from primal heuristics, employs a faster rational LP solver based on LP iterative refinement, and is able to produce independently verifiable certificates of optimality. We study the significantly improved performance and give insights into the computational behavior of the new algorithmic components. On the MIPLIB 2017 benchmark set, we observe an average speedup of 10.7x over the original framework and 2.9 times as many instances solved within a time limit of two hours.}, language = {en} } @article{BesanconGarciaLegatetal.2023, author = {Besan{\c{c}}on, Mathieu and Garcia, Joaquim Dias and Legat, Beno{\^i}t and Sharma, Akshay}, title = {Flexible Differentiable Optimization via Model Transformations}, volume = {36}, journal = {INFORMS Journal on Computing}, number = {2}, doi = {10.1287/ijoc.2022.0283}, pages = {456 -- 478}, year = {2023}, abstract = {We introduce DiffOpt.jl, a Julia library to differentiate through the solution of optimization problems with respect to arbitrary parameters present in the objective and/or constraints. The library builds upon MathOptInterface, thus leveraging the rich ecosystem of solvers and composing well with modeling languages like JuMP. DiffOpt offers both forward and reverse differentiation modes, enabling multiple use cases from hyperparameter optimization to backpropagation and sensitivity analysis, bridging constrained optimization with end-to-end differentiable programming. DiffOpt is built on two known rules for differentiating quadratic programming and conic programming standard forms. However, thanks to its ability to differentiate through model transformations, the user is not limited to these forms and can differentiate with respect to the parameters of any model that can be reformulated into these standard forms. This notably includes programs mixing affine conic constraints and convex quadratic constraints or objective function.}, language = {en} } @article{BonamiGleixnerLinderothetal.2018, author = {Bonami, Pierre and Gleixner, Ambros and Linderoth, Jeff and Misener, Ruth}, title = {Designing and Implementing Algorithms for Mixed-Integer Nonlinear Optimization (Dagstuhl Seminar 18081)}, volume = {8}, journal = {Dagstuhl Reports}, number = {2}, doi = {10.4230/DagRep.8.2.64}, pages = {64 -- 87}, year = {2018}, abstract = {Mathematical models for optimal decisions often require both nonlinear and discrete components. These mixed-integer nonlinear programs (MINLP) may be used to optimize the energy use of large industrial plants, integrate renewable sources into energy networks, design biological and biomedical systems, and address numerous other applications of societal importance. The first MINLP algorithms and software were designed by application engineers. While these efforts initially proved useful, scientists, engineers, and practitioners have realized that a transformational shift in technology will be required for MINLP to achieve its full potential. MINLP has transitioned to a forefront position in computer science, with researchers actively developing MINLP theory, algorithms, and implementations. Even with their concerted effort, algorithms and available software are often unable to solve practically-sized instances of these important models. Current obstacles include characterizing the computability boundary, effectively exploiting known optimization technologies for specialized classes of MINLP, and effectively using logical formulas holistically throughout algorithms.}, language = {en} } @article{MuellerMunozGasseetal.2022, author = {M{\"u}ller, Benjamin and Mu{\~n}oz, Gonzalo and Gasse, Maxime and Gleixner, Ambros and Lodi, Andrea and Serrano, Felipe}, title = {On generalized surrogate duality in mixed-integer nonlinear programming}, volume = {192}, journal = {Mathematical Programming}, number = {1}, doi = {10.1007/s10107-021-01691-6}, pages = {89 -- 118}, year = {2022}, abstract = {The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global ϵ-optimality with spatial branch and bound is a tight, computationally tractable relaxation. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solvers can often successfully handle a moderate presence of nonconvexities, which opens the door for the use of potentially tighter nonconvex relaxations. In this work, we exploit this fact and make use of a nonconvex relaxation obtained via aggregation of constraints: a surrogate relaxation. These relaxations were actively studied for linear integer programs in the 70s and 80s, but they have been scarcely considered since. We revisit these relaxations in an MINLP setting and show the computational benefits and challenges they can have. Additionally, we study a generalization of such relaxation that allows for multiple aggregations simultaneously and present the first algorithm that is capable of computing the best set of aggregations. We propose a multitude of computational enhancements for improving its practical performance and evaluate the algorithm's ability to generate strong dual bounds through extensive computational experiments.}, language = {en} } @article{Gamrath2014, author = {Gamrath, Gerald}, title = {Improving strong branching by domain propagation}, volume = {2}, journal = {EURO Journal on Computational Optimization}, number = {3}, publisher = {Springer}, address = {Berlin Heidelberg}, doi = {10.1007/s13675-014-0021-8}, pages = {99 -- 122}, year = {2014}, abstract = {One of the essential components of a branch-and-bound based mixed-integer linear programming (MIP) solver is the branching rule. Strong branching is a method used by many state-of-the-art branching rules to select the variable to branch on. It precomputes the dual bounds of potential child nodes by solving auxiliary linear programs (LPs) and thereby helps to take good branching decisions that lead to a small search tree. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Domain propagation is a technique MIP solvers usually apply 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, the state-of-the-art hybrid branching rule can be improved this way as well. This paper extends previous work by the author published in the proceedings of the CPAIOR 2013.}, language = {en} } @misc{ShinanoHeinzVigerskeetal.2013, author = {Shinano, Yuji and Heinz, Stefan and Vigerske, Stefan and Winkler, Michael}, title = {FiberSCIP - A shared memory parallelization of SCIP}, issn = {1438-0064}, doi = {10.1287/ijoc.2017.0762}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42595}, year = {2013}, abstract = {Recently, parallel computing environments have become significantly popular. In order to obtain the benefit of using parallel computing environments, we have to deploy our programs for these effectively. This paper focuses on a parallelization of SCIP (Solving Constraint Integer Programs), which is a MIP solver and constraint integer programming framework available in source code. There is a parallel extension of SCIP named ParaSCIP, which parallelizes SCIP on massively parallel distributed memory computing environments. This paper describes FiberSCIP, which is yet another parallel extension of SCIP to utilize multi-threaded parallel computation on shared memory computing environments, and has the following contributions: First, the basic concept of having two parallel extensions and the relationship between them and the parallelization framework provided by UG (Ubiquity Generator) is presented, including an implementation of deterministic parallelization. Second, the difficulties to achieve a good performance that utilizes all resources on an actual computing environment and the difficulties of performance evaluation of the parallel solvers are discussed. Third, a way to evaluate the performance of new algorithms and parameter settings of the parallel extensions is presented. Finally, current performance of FiberSCIP for solving mixed-integer linear programs (MIPs) and mixed-integer non-linear programs (MINLPs) in parallel is demonstrated.}, language = {en} } @misc{Hendel2014, type = {Master Thesis}, author = {Hendel, Gregor}, title = {Empirical Analysis of Solving Phases in Mixed Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-54270}, pages = {159}, year = {2014}, abstract = {Modern solving software for mixed-integer programming (MIP) incorporates numerous algorithmic components whose behavior is controlled by user parameter choices, and whose usefulness dramatically varies depending on the progress of the solving process. In this thesis, our aim is to construct a phase-based solver that dynamically reacts on phase transitions with an appropriate change of its component behavior. Therefore, we decompose the branch-and-bound solving process into three distinct phases: 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 construct a phase-based solver to make use of the phase concept in two steps: First, we identify promising components for every solving phase individually and show that their combination is beneficial on a test bed of practical MIP instances. We then present and evaluate three heuristic criteria to make use of the phase-based solver in practice, where it is infeasible to distinguish between the last two phases before the termination of the solving process.}, language = {en} } @misc{Witzig2014, type = {Master Thesis}, author = {Witzig, Jakob}, title = {Reoptimization Techniques in MIP Solvers}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-54067}, pages = {176}, year = {2014}, abstract = {Many optimization problems can be modeled as Mixed Integer Programs (MIPs). In general, MIPs cannot be solved efficiently, since solving MIPs is NP-hard, see, e.g., Schrijver, 2003. Common methods for solving NP-hard problems are branch-and-bound and column generation. In the case of column generation, the original problem becomes decomposed or re-formulated into one ore more smaller subproblems, which are easier to solve. Each of these subproblems is solved separately and recurrently, which can be interpreted as solving a sequence of optimization problems. In this thesis, we consider a sequence of MIPs which only differ in the respective objective functions. Furthermore, we assume each of these MIPs get solved with a branch-and-bound algorithm. This thesis aims to figure out whether the solving process of a given sequence of MIPs can be accelerated by reoptimization. As reoptimization we understand starting the solving process of a MIP of this sequence at a given frontier of a search tree corresponding to another MIP of this sequence. At the beginning we introduce an LP-based branch-and-bound algorithm. This algorithm is inspired by the reoptimizing algorithm of Hiller, Klug, and the author of this thesis, 2013. Since most of the state-of-the-art MIP solvers come to decisions based on dual information, which leads to the loss of feasible solutions after changing the objective function, we present a technique to guarantee optimality despite using these information. A decision is based on a dual information if this decision is valid for at least one feasible solution, whereas a decision is based on a primal information if this decision is valid for all feasible solutions. Afterwards, we consider representing the search frontier of the tree by a set of nodes of a given size. We call this the Tree Compression Problem. Moreover, we present a criterion characterizing the similarity of two objective functions. To evaluate our approach of reoptimization we extend the well-known and well-maintained MIP solver SCIP to an LP-based branch-and-bound framework, introduce two heuristics for solving the Tree Compression Problem, and a primal heuristic which is especially fitted to column generation. Finally, we present computational experiments on several problem classes, e.g., the Vertex Coloring and k-Constrained Shortest Path. Our experiments show, that a straightforward reoptimization, i.e., without additional heuristics, provides no benefit in general. However, in combination with the techniques and methods presented in this thesis, we can accelerate the solving of a given sequence up to the factor 14. For this purpose it is essential to take the differences of the objective functions into account and to restart the reoptimization, i.e., solve the subproblem from scratch, if the objective functions are not similar enough. Finally, we discuss the possibility to parallelize the solving process of the search frontier at the beginning of each solving process.}, language = {en} } @misc{GamrathMelchioriBertholdetal.2015, author = {Gamrath, Gerald and Melchiori, Anna and Berthold, Timo and Gleixner, Ambros and Salvagnin, Domenico}, title = {Branching on multi-aggregated variables}, issn = {1438-0064}, doi = {10.1007/978-3-319-18008-3_10}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-53829}, year = {2015}, abstract = {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.}, language = {en} } @misc{WitzigGamrathHiller2015, author = {Witzig, Jakob and Gamrath, Gerald and Hiller, Benjamin}, title = {Reoptimization Techniques in MIP Solvers}, issn = {1438-0064}, doi = {10.1007/978-3-319-20086-6_14}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-54375}, year = {2015}, abstract = {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.}, language = {en} } @misc{MaherFischerGallyetal.2017, author = {Maher, Stephen J. and Fischer, Tobias and Gally, Tristan and Gamrath, Gerald and Gleixner, Ambros and Gottwald, Robert Lion and Hendel, Gregor and Koch, Thorsten and L{\"u}bbecke, Marco 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 Weninger, Dieter and Witt, Jonas T. and Witzig, Jakob}, title = {The SCIP Optimization Suite 4.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-62170}, year = {2017}, abstract = {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.}, language = {en} } @article{YokoyamaShinanoTaniguchietal.2015, author = {Yokoyama, Ryohei and Shinano, Yuji and Taniguchi, Syusuke and Ohkura, Masashi and Wakui, Tetsuya}, title = {Optimization of energy supply systems by MILP branch and bound method in consideration of hierarchical relationship between design and operation}, volume = {92}, journal = {Energy Conversion and Management}, doi = {10.1016/j.enconman.2014.12.020}, pages = {92 -- 104}, year = {2015}, abstract = {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.}, language = {en} } @incollection{YokoyamaShinano2015, author = {Yokoyama, Ryohei and Shinano, Yuji}, title = {MILP Approaches to Optimal Design and Operation of Distributed Energy Systems}, volume = {Volume 13}, booktitle = {Optimization in the Real World}, publisher = {Springer}, isbn = {978-4-431-55419-6}, doi = {10.1007/978-4-431-55420-2_9}, pages = {157 -- 176}, year = {2015}, abstract = {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.}, language = {en} } @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{GottwaldMaherShinano2017, author = {Gottwald, Robert Lion and Maher, Stephen J. and Shinano, Yuji}, title = {Distributed Domain Propagation}, volume = {75}, booktitle = {16th International Symposium on Experimental Algorithms (SEA 2017)}, doi = {10.4230/LIPIcs.SEA.2017.6}, pages = {6:1 -- 6:11}, year = {2017}, 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 its 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 the domain of a variable has been reduced. In this paper we introduce distributed domain propagation, a technique that shares bound tightenings across solvers to trigger further domain propagations. We investigate its impact 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} } @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} } @misc{Shinano2017, author = {Shinano, Yuji}, title = {The Ubiquity Generator Framework: 7 Years of Progress in Parallelizing Branch-and-Bound}, issn = {1438-0064}, doi = {10.1007/978-3-319-89920-6_20}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-65545}, year = {2017}, 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{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{SchenkerBorndoerferSkutella2016, author = {Schenker, Sebastian and Bornd{\"o}rfer, Ralf and Skutella, Martin}, title = {A novel partitioning of the set of non-dominated points}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61286}, year = {2016}, abstract = {We consider a novel partitioning of the set of non-dominated points for general multi-objective integer programs with \$k\$ objectives. The set of non-dominated points is partitioned into a set of non-dominated points whose efficient solutions are also efficient for some restricted subproblem with one less objective; the second partition comprises the non-dominated points whose efficient solutions are inefficient for any of the restricted subproblems. We show that the first partition has the nice property that it yields finite rectangular boxes in which the points of the second partition are located.}, 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} } @phdthesis{Berthold2014, author = {Berthold, Timo}, title = {Heuristic algorithms in global MINLP solvers}, publisher = {Dr. Hut Verlag}, isbn = {978-3-8439-1931-9}, pages = {366}, year = {2014}, abstract = {In the literature for mixed integer programming, heuristic algorithms (particularly primal heuristics) are often considered as stand-alone procedures; in that context, heuristics are treated as an alternative to solving a problem to proven optimality. This conceals the fact that heuristic algorithms are a fundamental component of state-of-the-art global solvers for mixed integer linear programming (MIP) and mixed integer nonlinear programming (MINLP). In the present thesis, we focus on this latter aspect; we study heuristic algorithms that are tightly integrated within global MINLP solvers and analyze their impact on the overall solution process. Our contributions comprise generalizations of primal heuristics for MIP towards MINLP as well as novel ideas for MINLP primal heuristics and for heuristic algorithms to take branching decisions and to collect global information in MIP. These are: - Shift-and-Propagate, a novel propagation heuristic for MIP that does not require the solution to an LP relaxation, - a generic way to generalize large neighborhood search (LNS) heuristics from MIP to MINLP, - an Objective Feasibility Pump heuristic for nonconvex MINLP that uses second-order information and a dynamic selection of rounding procedures, - RENS, an LNS start heuristic for MINLP that optimizes over the set of feasible roundings of an LP solution, - Undercover, an LNS start heuristic for MINLP that solves a largest sub-MIP of a given MINLP, - Rapid Learning, a heuristic algorithm to generate globally valid conflict constraints for MIPs, - Cloud Branching, a heuristic algorithm that exploits dual degeneracy to reduce the number of candidates for branching variable selection. Additionally, we propose a new performance measure, the primal integral, that captures the benefits of primal heuristics better than traditional methods. In our computational study, we compare the performance of the MIP and MINLP solver SCIP with and without primal heuristics on six test sets with altogether 983 instances from academic and industrial sources, including our project partners ForNe, SAP, and Siemens. We observe that heuristics improve the solver performance regarding all measures that we used - by different orders of magnitude. We further see that the harder a problem is to solve to global optimality, the more important the deployment of primal heuristics becomes. The algorithms presented in this thesis are available in source code as part of the solver SCIP, of which the author has been a main developer for the last years. Methods described in this thesis have also been re-implemented within several commercial and noncommercial MIP and MINLP software packages, including Bonmin, CBC, Cplex, Gams, Sulum, and Xpress.}, 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} }