@article{BestuzhevaHijaziCoffrin2019, author = {Bestuzheva, Ksenia and Hijazi, Hassan and Coffrin, Carleton}, title = {Convex Relaxations for Quadratic On/Off Constraints and Applications to Optimal Transmission Switching}, volume = {32}, journal = {INFORMS Journal on Computing}, number = {3}, publisher = {INFORMS Institute for Operations Research and the Management Sciences}, address = {5521 Research Park Drive, Suite 200, Catonsville, MD 21228 USA}, doi = {https://doi.org/10.1287/ijoc.2019.0900}, pages = {682 -- 696}, year = {2019}, abstract = {This paper studies mixed-integer nonlinear programs featuring disjunctive constraints and trigonometric functions and presents a strengthened version of the Convex Quadratic relaxation of the Optimal Transmission Switching problem. We first characterize the convex hull of univariate quadratic on/off constraints in the space of original variables using perspective functions. We then introduce new tight quadratic relaxations for trigonometric functions featuring variables with asymmetrical bounds. These results are used to further tighten recent convex relaxations introduced for the Optimal Transmission Switching problem in Power Systems. Using the proposed improvements, along with bound propagation, on 23 medium-size test cases in the PGLib benchmark library with a relaxation gap of more than 1\%, we reduce the gap to less than 1\% on 5 instances. The tightened model has promising computational results when compared to state-of-the-art formulations.}, language = {en} } @inproceedings{AndersonHendelLeBodicetal.2018, author = {Anderson, Daniel and Hendel, Gregor and Le Bodic, Pierre and Viernickel, Jan Merlin}, title = {Clairvoyant Restarts in Branch-and-Bound Search Using Online Tree-Size Estimation}, booktitle = {AAAI-19: Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence}, year = {2018}, abstract = {We propose a simple and general online method to measure the search progress within the branch-and-bound algorithm, from which we estimate the size of the remaining search tree. We then show how this information can help solvers algorithmically at runtime by designing a restart strategy for Mixed-Integer Programming (MIP) solvers that decides whether to restart the search based on the current estimate of the number of remaining nodes in the tree. We refer to this type of algorithm as clairvoyant. Our clairvoyant restart strategy outperforms a state-of-the-art solver on a large set of publicly available MIP benchmark instances. It is implemented in the MIP solver SCIP and will be available in future releases.}, language = {de} } @inproceedings{GleixnerSteffy2019, author = {Gleixner, Ambros and Steffy, Daniel}, title = {Linear Programming using Limited-Precision Oracles}, booktitle = {A. Lodi, V. Nagarajan (eds), Integer Programming and Combinatorial Optimization: 20th International Conference, IPCO 2019}, doi = {10.1007/978-3-030-17953-3_30}, pages = {399 -- 412}, year = {2019}, abstract = {Linear programming is a foundational tool for many aspects of integer and combinatorial optimization. This work studies the complexity of solving linear programs exactly over the rational numbers through use of an oracle capable of returning limited-precision LP solutions. It is shown that a polynomial number of calls to such an oracle and a polynomial number of bit operations, is sufficient to compute an exact solution to an LP. Previous work has often considered oracles that provide solutions of an arbitrary specified precision. While this leads to polynomial-time algorithms, the level of precision required is often unrealistic for practical computation. In contrast, our work provides a foundation for understanding and analyzing the behavior of the methods that are currently most effective in practice for solving LPs exactly.}, language = {en} } @inproceedings{Serrano2019, author = {Serrano, Felipe}, title = {Intersection cuts for factorable MINLP}, volume = {11480}, booktitle = {A. Lodi, V. Nagarajan (eds), Integer Programming and Combinatorial Optimization: 20th International Conference, IPCO 2019}, doi = {10.1007/978-3-030-17953-3_29}, pages = {385 -- 398}, year = {2019}, abstract = {Given a factorable function f, we propose a procedure that constructs a concave underestimor of f that is tight at a given point. These underestimators can be used to generate intersection cuts. A peculiarity of these underestimators is that they do not rely on a bounded domain. We propose a strengthening procedure for the intersection cuts that exploits the bounds of the domain. Finally, we propose an extension of monoidal strengthening to take advantage of the integrality of the non-basic variables.}, language = {en} } @misc{ShinanoAchterbergBertholdetal.2015, 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}, issn = {1438-0064}, doi = {10.1109/IPDPS.2016.56}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-56404}, year = {2015}, 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{MunguiaOxberryRajanetal.2017, author = {Munguia, Lluis-Miquel and Oxberry, Geoffrey and Rajan, Deepak and Shinano, Yuji}, title = {Parallel PIPS-SBB: Multi-Level Parallelism For Stochastic Mixed-Integer Programs}, number = {ZIB-Report 17-58}, issn = {1438-0064}, doi = {10.1007/s10589-019-00074-0}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-65517}, year = {2017}, abstract = {PIPS-SBB is a distributed-memory parallel solver with a scalable data distribution paradigm. It is designed to solve MIPs with a dual-block angular structure, which is characteristic of deterministic-equivalent Stochastic Mixed-Integer Programs (SMIPs). In this paper, we present two different parallelizations of Branch \& Bound (B\&B), implementing both as extensions of PIPS-SBB, thus adding an additional layer of parallelism. In the first of the proposed frameworks, PIPS-PSBB, the coordination and load-balancing of the different optimization workers is done in a decentralized fashion. This new framework is designed to ensure all available cores are processing the most promising parts of the B\&B tree. The second, ug[PIPS-SBB,MPI], is a parallel implementation using the Ubiquity Generator (UG), a universal framework for parallelizing B\&B tree search that has been successfully applied to other MIP solvers. We show the effects of leveraging multiple levels of parallelism in potentially improving scaling performance beyond thousands of cores.}, language = {en} } @article{GamrathBertholdHeinzetal.2019, author = {Gamrath, Gerald and Berthold, Timo and Heinz, Stefan and Winkler, Michael}, title = {Structure-driven fix-and-propagate heuristics for mixed integer programming}, volume = {11}, journal = {Mathematical Programming Computation}, number = {4}, publisher = {Springer}, address = {Berlin Heidelberg}, doi = {10.1007/s12532-019-00159-1}, pages = {675 -- 702}, year = {2019}, abstract = {Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They often provide good feasible solutions early and help to reduce the time needed to prove optimality. In this paper, we present a scheme for start heuristics that can be executed without previous knowledge of an LP solution or a previously found integer feasible solution. It uses global structures available within MIP solvers to iteratively fix integer variables and propagate these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. If sufficiently many variables can be fixed that way, the resulting problem is solved first as an LP, and then as an auxiliary MIP if the rounded LP solution does not provide a feasible solution already. We present three primal heuristics that use this scheme based on different global structures. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about 60 \% of the instances and by this, help to improve several performance measures for MIP solvers, including the primal integral and the average solving time.}, language = {en} } @misc{BertholdStuckeyWitzig2018, author = {Berthold, Timo and Stuckey, Peter and Witzig, Jakob}, title = {Local Rapid Learning for Integer Programs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71190}, year = {2018}, abstract = {Conflict learning algorithms are an important component of modern MIP and CP solvers. But strong conflict information is typically gained by depth-first search. While this is the natural mode for CP solving, it is not for MIP solving. Rapid Learning is a hybrid CP/MIP approach where CP search is applied at the root to learn information to support the remaining MIP solve. This has been demonstrated to be beneficial for binary programs. In this paper, we extend the idea of Rapid Learning to integer programs, where not all variables are restricted to the domain {0, 1}, and rather than just running a rapid CP search at the root, we will apply it repeatedly at local search nodes within the MIP search tree. To do so efficiently, we present six heuristic criteria to predict the chance for local Rapid Learning to be successful. Our computational experiments indicate that our extended Rapid Learning algorithm significantly speeds up MIP search and is particularly beneficial on highly dual degenerate problems.}, language = {en} } @misc{Hendel2018, author = {Hendel, Gregor}, title = {Adaptive Large Neighborhood Search for Mixed Integer Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71167}, year = {2018}, abstract = {Large Neighborhood Search (LNS) heuristics are among the most powerful but also most expensive heuristics for mixed integer programs (MIP). Ideally, a solver learns adaptively which LNS heuristics work best for the MIP problem at hand in order to concentrate its limited computational budget. To this end, this work introduces Adaptive Large Neighborhood Search (ALNS) for MIP, a primal heuristic that acts a framework for eight popular LNS heuristics such as Local Branching and Relaxation Induced Neighborhood Search (RINS). We distinguish the available LNS heuristics by their individual search domains, which we call neighborhoods. The decision which neighborhood should be executed is guided by selection strategies for the multi armed bandit problem, a related optimization problem during which suitable actions have to be chosen to maximize a reward function. In this paper, we propose an LNS-specific reward function to learn to distinguish between the available neighborhoods based on successful calls and failures. A second, algorithmic enhancement is a generic variable fixing priorization, which ALNS employs to adjust the subproblem complexity as needed. This is particularly useful for some neighborhoods which do not fix variables by themselves. The proposed primal heuristic has been implemented within the MIP solver SCIP. An extensive computational study is conducted to compare different LNS strategies within our ALNS framework on a large set of publicly available MIP instances from the MIPLIB and Coral benchmark sets. The results of this simulation are used to calibrate the parameters of the bandit selection strategies. A second computational experiment shows the computational benefits of the proposed ALNS framework within the MIP solver SCIP.}, language = {en} } @misc{WitzigBertholdHeinz2018, author = {Witzig, Jakob and Berthold, Timo and Heinz, Stefan}, title = {A Status Report on Conflict Analysis in Mixed Integer Nonlinear Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71170}, year = {2018}, abstract = {Mixed integer nonlinear programs (MINLPs) are arguably among the hardest optimization problems, with a wide range of applications. MINLP solvers that are based on linear relaxations and spatial branching work similar as mixed integer programming (MIP) solvers in the sense that they are based on a branch-and-cut algorithm, enhanced by various heuristics, domain propagation, and presolving techniques. However, the analysis of infeasible subproblems, which is an important component of most major MIP solvers, has been hardly studied in the context of MINLPs. There are two main approaches for infeasibility analysis in MIP solvers: conflict graph analysis, which originates from artificial intelligence and constraint programming, and dual ray analysis. The main contribution of this short paper is twofold. Firstly, we present the first computational study regarding the impact of dual ray analysis on convex and nonconvex MINLPs. In that context, we introduce a modified generation of infeasibility proofs that incorporates linearization cuts that are only locally valid. Secondly, we describe an extension of conflict analysis that works directly with the nonlinear relaxation of convex MINLPs instead of considering a linear relaxation. This is work-in-progress, and this short paper is meant to present first theoretical considerations without a computational study for that part.}, language = {en} } @misc{Serrano2018, author = {Serrano, Felipe}, title = {Intersection cuts for factorable MINLP}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71105}, year = {2018}, abstract = {Given a factorable function f, we propose a procedure that constructs a concave underestimor of f that is tight at a given point. These underestimators can be used to generate intersection cuts. A peculiarity of these underestimators is that they do not rely on a bounded domain. We propose a strengthening procedure for the intersection cuts that exploits the bounds of the domain. Finally, we propose an extension of monoidal strengthening to take advantage of the integrality of the non-basic variables.}, language = {en} } @article{WitzigGleixner2020, author = {Witzig, Jakob and Gleixner, Ambros}, title = {Conflict-Driven Heuristics for Mixed Integer Programming}, volume = {33}, journal = {INFORMS Journal on Computing}, number = {2}, doi = {10.1287/ijoc.2020.0973}, pages = {706 -- 720}, year = {2020}, abstract = {Two essential ingredients of modern mixed-integer programming (MIP) solvers are diving heuristics that simulate a partial depth-first search in a branch-and-bound search tree and conflict analysis of infeasible subproblems to learn valid constraints. So far, these techniques have mostly been studied independently: primal heuristics under the aspect of finding high-quality feasible solutions early during the solving process and conflict analysis for fathoming nodes of the search tree and improving the dual bound. Here, we combine both concepts in two different ways. First, we develop a diving heuristic that targets the generation of valid conflict constraints from the Farkas dual. We show that in the primal this is equivalent to the optimistic strategy of diving towards the best bound with respect to the objective function. Secondly, we use information derived from conflict analysis to enhance the search of a diving heuristic akin to classical coefficient diving. The computational performance of both methods is evaluated using an implementation in the source-open MIP solver SCIP. Experiments are carried out on publicly available test sets including Miplib 2010 and Cor@l.}, language = {en} } @article{GleixnerHendelGamrathetal.2021, author = {Gleixner, Ambros and Hendel, Gregor and Gamrath, Gerald and Achterberg, Tobias and Bastubbe, Michael and Berthold, Timo and Christophel, Philipp M. and Jarck, Kati and Koch, Thorsten and Linderoth, Jeff and L{\"u}bbecke, Marco and Mittelmann, Hans and Ozyurt, Derya and Ralphs, Ted and Salvagnin, Domenico and Shinano, Yuji}, title = {MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library}, volume = {13}, journal = {Mathematical Programming Computation}, number = {3}, doi = {10.1007/s12532-020-00194-3}, pages = {443 -- 490}, year = {2021}, abstract = {We report on the selection process leading to the sixth version of the Mixed Integer Programming Library. Selected from an initial pool of over 5,000 instances, the new MIPLIB 2017 collection consists of 1,065 instances. A subset of 240 instances was specially selected for benchmarking solver performance. For the first time, the compilation of these sets was done using a data-driven selection process supported by the solution of a sequence of mixed integer optimization problems, which encoded requirements on diversity and balancedness with respect to instance features and performance data.}, language = {en} } @misc{GleixnerSteffy2019, author = {Gleixner, Ambros and Steffy, Daniel}, title = {Linear Programming using Limited-Precision Oracles}, issn = {1438-0064}, doi = {10.1007/s10107-019-01444-6}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-75316}, year = {2019}, abstract = {Since the elimination algorithm of Fourier and Motzkin, many different methods have been developed for solving linear programs. When analyzing the time complexity of LP algorithms, it is typically either assumed that calculations are performed exactly and bounds are derived on the number of elementary arithmetic operations necessary, or the cost of all arithmetic operations is considered through a bit-complexity analysis. Yet in practice, implementations typically use limited-precision arithmetic. In this paper we introduce the idea of a limited-precision LP oracle and study how such an oracle could be used within a larger framework to compute exact precision solutions to LPs. Under mild assumptions, it is shown that a polynomial number of calls to such an oracle and a polynomial number of bit operations, is sufficient to compute an exact solution to an LP. This work provides a foundation for understanding and analyzing the behavior of the methods that are currently most effective in practice for solving LPs exactly.}, language = {en} } @misc{GeorgesGleixnerGojicetal.2018, author = {Georges, Alexander and Gleixner, Ambros and Gojic, Gorana and Gottwald, Robert Lion and Haley, David and Hendel, Gregor and Matejczyk, Bartlomiej}, title = {Feature-Based Algorithm Selection for Mixed Integer Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-68362}, year = {2018}, abstract = {Mixed integer programming is a versatile and valuable optimization tool. However, solving specific problem instances can be computationally demanding even for cutting-edge solvers. Such long running times are often significantly reduced by an appropriate change of the solver's parameters. In this paper we investigate "algorithm selection", the task of choosing among a set of algorithms the ones that are likely to perform best for a particular instance. In our case, we treat different parameter settings of the MIP solver SCIP as different algorithms to choose from. Two peculiarities of the MIP solving process have our special attention. We address the well-known problem of performance variability by using multiple random seeds. Besides solving time, primal dual integrals are recorded as a second performance measure in order to distinguish solvers that timed out. We collected feature and performance data for a large set of publicly available MIP instances. The algorithm selection problem is addressed by several popular, feature-based methods, which have been partly extended for our purpose. Finally, an analysis of the feature space and performance results of the selected algorithms are presented.}, language = {en} } @inproceedings{CaoGleixnerMiltenberger2016, author = {Cao, Karl-Ki{\^e}n and Gleixner, Ambros and Miltenberger, Matthias}, title = {Methoden zur Reduktion der Rechenzeit linearer Optimierungsmodelle in der Energiewirtschaft - Eine Performance-Analyse}, booktitle = {EnInnov 2016: 14. Symposium Energieinnovation 2016}, year = {2016}, abstract = {Dieser Beitrag stellt m{\"o}gliche Ans{\"a}tze zur Reduktion der Rechenzeit von linearen Optimierungsproblemen mit energiewirtschaftlichem Anwendungshintergrund vor. Diese Ans{\"a}tze bilden im Allgemeinen die Grundlage f{\"u}r konzeptionelle Strategien zur Beschleunigung von Energiesystemmodellen. Zu den einfachsten Beschleunigungsstrategien z{\"a}hlt die Verkleinerung der Modelldimensionen, was beispielsweise durch {\"A}ndern der zeitlichen, r{\"a}umlichen oder technologischen Aufl{\"o}sung eines Energiesystemmodells erreicht werden kann. Diese Strategien sind zwar h{\"a}ufig ein Teil der Methodik in der Energiesystemanalyse, systematische Benchmarks zur Bewertung ihrer Effektivit{\"a}t werden jedoch meist nicht durchgef{\"u}hrt. Die vorliegende Arbeit adressiert genau diesen Sachverhalt. Hierzu werden Modellinstanzen des Modells REMix in verschiedenen Gr{\"o}ßenordnungen mittels einer Performance-Benchmark-Analyse untersucht. Die Ergebnisse legen zum einen den Schluss nahe, dass verk{\"u}rzte Betrachtungszeitr{\"a}ume das gr{\"o}ßte Potential unter den hier analysierten Strategien zur Reduktion von Rechenzeit bieten. Zum anderen empfiehlt sich die Verwendung des Barrier-L{\"o}sungsverfahrens mit multiplen Threads unter Vernachl{\"a}ssigung des Cross-Over.}, language = {de} } @inproceedings{D'AndreagiovanniGleixner2016, author = {D'Andreagiovanni, Fabio and Gleixner, Ambros}, title = {Towards an accurate solution of wireless network design problems}, booktitle = {Cerulli R., Fujishige S., Mahjoub A. (eds) Combinatorial Optimization. ISCO 2016}, doi = {10.1007/978-3-319-45587-7_12}, pages = {135 -- 147}, year = {2016}, abstract = {The optimal design of wireless networks has been widely studied in the literature and many optimization models have been proposed over the years. However, most models directly include the signal-to-interference ratios representing service coverage conditions. This leads to mixed-integer linear programs with constraint matrices containing tiny coefficients that vary widely in their order of magnitude. These formulations are known to be challenging even for state-of-the-art solvers: the standard numerical precision supported by these solvers is usually not sufficient to reliably guarantee feasible solutions. Service coverage errors are thus commonly present. Though these numerical issues are known and become evident even for small-sized instances, just a very limited number of papers has tried to tackle them, by mainly investigating alternative non-compact formulations in which the sources of numerical instabilities are eliminated. In this work, we explore a new approach by investigating how recent advances in exact solution algorithms for linear and mixed-integer programs over the rational numbers can be applied to analyze and tackle the numerical difficulties arising in wireless network design models.}, language = {en} } @inproceedings{DevriendtGleixnerNordstroem2020, author = {Devriendt, Jo and Gleixner, Ambros and Nordstr{\"o}m, Jakob}, title = {Learn to Relax: Integrating 0-1 Integer Linear Programming with Pseudo-Boolean Conflict-Driven Search}, volume = {12296}, booktitle = {Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2020}, publisher = {Springer}, pages = {xxiv -- xxvi}, year = {2020}, abstract = {Conflict-driven Pseudo-Boolean (PB) solvers optimize 0-1 integer linear programs by extending the conflict-driven clause learning (CDCL) paradigm from SAT solving. Though PB solvers have the potential to be exponentially more efficient than CDCL solvers in theory, in practice they can sometimes get hopelessly stuck even when the linear program (LP) relaxation is infeasible over the reals. Inspired by mixed integer programming (MIP), we address this problem by interleaving incremental LP solving with cut generation within the conflict-driven PB search. This hybrid approach, which for the first time combines MIP techniques with full-blown conflict analysis over linear inequalities using the cutting planes method, significantly improves performance on a wide range of benchmarks, approaching a "best of two worlds" scenario between SAT-style conflict-driven search and MIP-style branch-and-cut.}, language = {en} } @inproceedings{BertholdGleixner2010, author = {Berthold, Timo and Gleixner, Ambros}, title = {Undercover - a primal heuristic for MINLP based on sub-MIPs generated by set covering}, booktitle = {Proceedings of the European Workshop on Mixed Integer Nonlinear Programming, April 12-16, 2010, Marseilles, France}, editor = {Bonami, Pierre and Liberti, Leo and Miller, Andrew J. and Sartenaer, Annick}, pages = {103 -- 112}, year = {2010}, abstract = {We present Undercover, a primal heuristic for mixed-integer nonlinear programming (MINLP). The heuristic constructs a mixed-integer linear subproblem (sub-MIP) of a given MINLP by fixing a subset of the variables. We solve a set covering problem to identify a minimal set of variables which need to be fixed in order to linearise each constraint. Subsequently, these variables are fixed to approximate values, e.g. obtained from a linear outer approximation. The resulting sub-MIP is solved by a mixed-integer linear programming solver. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem. Although general in nature, the heuristic seems most promising for mixed-integer quadratically constrained programmes (MIQCPs). We present computational results on a general test set of MIQCPs selected from the MINLPLib.}, language = {en} } @misc{MuellerKuhlmannVigerske2017, author = {M{\"u}ller, Benjamin and Kuhlmann, Renke and Vigerske, Stefan}, title = {On the performance of NLP solvers within global MINLP solvers}, issn = {1438-0064}, doi = {10.1007/978-3-319-89920-6_84}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64504}, year = {2017}, abstract = {Solving mixed-integer nonlinear programs (MINLPs) to global optimality efficiently requires fast solvers for continuous sub-problems. These appear in, e.g., primal heuristics, convex relaxations, and bound tightening methods. Two of the best performing algorithms for these sub-problems are Sequential Quadratic Programming (SQP) and Interior Point Methods. In this paper we study the impact of different SQP and Interior Point implementations on important MINLP solver components that solve a sequence of similar NLPs. We use the constraint integer programming framework SCIP for our computational studies.}, language = {en} } @inproceedings{HendelMiltenbergerWitzig2018, author = {Hendel, Gregor and Miltenberger, Matthias and Witzig, Jakob}, title = {Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms}, booktitle = {OR 2018: International Conference on Operations Research}, year = {2018}, abstract = {State-of-the-art solvers for mixed integer programs (MIP) govern a variety of algorithmic components. Ideally, the solver adaptively learns to concentrate its computational budget on those components that perform well on a particular problem, especially if they are time consuming. We focus on three such algorithms, namely the classes of large neighborhood search and diving heuristics as well as Simplex pricing strategies. For each class we propose a selection strategy that is updated based on the observed runtime behavior, aiming to ultimately select only the best algorithms for a given instance. We review several common strategies for such a selection scenario under uncertainty, also known as Multi Armed Bandit Problem. In order to apply those bandit strategies, we carefully design reward functions to rank and compare each individual heuristic or pricing algorithm within its respective class. Finally, we discuss the computational benefits of using the proposed adaptive selection within the SCIP Optimization Suite on publicly available MIP instances.}, language = {en} } @inproceedings{MuellerKuhlmannVigerske2018, author = {M{\"u}ller, Benjamin and Kuhlmann, Renke and Vigerske, Stefan}, title = {On the performance of NLP solvers within global MINLP solvers}, booktitle = {Operations Research Proceedings 2017}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-319-89920-6_84}, pages = {633 -- 639}, year = {2018}, abstract = {Solving mixed-integer nonlinear programs (MINLPs) to global optimality efficiently requires fast solvers for continuous sub-problems. These appear in, e.g., primal heuristics, convex relaxations, and bound tightening methods. Two of the best performing algorithms for these sub-problems are Sequential Quadratic Programming (SQP) and Interior Point Methods. In this paper we study the impact of different SQP and Interior Point implementations on important MINLP solver components that solve a sequence of similar NLPs. We use the constraint integer programming framework SCIP for our computational studies.}, language = {en} } @inproceedings{MuellerMuñozGasseetal.2020, author = {M{\"u}ller, Benjamin and Muñoz, Gonzalo and Gasse, Maxime and Gleixner, Ambros and Lodi, Andrea and Serrano, Felipe}, title = {On Generalized Surrogate Duality in Mixed-Integer Nonlinear Programming}, booktitle = {Integer Programming and Combinatorial Optimization: 21th International Conference, IPCO 2020}, doi = {10.1007/978-3-030-45771-6_25}, pages = {322 -- 337}, year = {2020}, abstract = {The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global epsilon-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 solver 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{HoppmannBaumHenningsZitteletal.2021, author = {Hoppmann-Baum, Kai and Hennings, Felix and Zittel, Janina and Gotzes, Uwe and Spreckelsen, Eva-Maria and Spreckelsen, Klaus and Koch, Thorsten}, title = {An Optimization Approach for the Transient Control of Hydrogen Transport Networks}, journal = {Mathematical Methods of Operations Research}, number = {Special Issue on Energy Networks}, year = {2021}, language = {en} } @misc{WitzigGleixner2019, author = {Witzig, Jakob and Gleixner, Ambros}, title = {Conflict-Driven Heuristics for Mixed Integer Programming}, issn = {1438-0064}, doi = {10.1287/ijoc.2020.0973}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-72204}, year = {2019}, abstract = {Two essential ingredients of modern mixed-integer programming (MIP) solvers are diving heuristics that simulate a partial depth-first search in a branch-and-bound search tree and conflict analysis of infeasible subproblems to learn valid constraints. So far, these techniques have mostly been studied independently: primal heuristics under the aspect of finding high-quality feasible solutions early during the solving process and conflict analysis for fathoming nodes of the search tree and improving the dual bound. Here, we combine both concepts in two different ways. First, we develop a diving heuristic that targets the generation of valid conflict constraints from the Farkas dual. We show that in the primal this is equivalent to the optimistic strategy of diving towards the best bound with respect to the objective function. Secondly, we use information derived from conflict analysis to enhance the search of a diving heuristic akin to classical coefficient diving. The computational performance of both methods is evaluated using an implementation in the source-open MIP solver SCIP. Experiments are carried out on publicly available test sets including Miplib 2010 and Cor@l.}, language = {en} } @misc{HendelMiltenbergerWitzig2018, author = {Hendel, Gregor and Miltenberger, Matthias and Witzig, Jakob}, title = {Adaptive Algorithmic Behavior for Solving Mixed Integer Programs Using Bandit Algorithms}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69563}, year = {2018}, abstract = {State-of-the-art solvers for mixed integer programs (MIP) govern a variety of algorithmic components. Ideally, the solver adaptively learns to concentrate its computational budget on those components that perform well on a particular problem, especially if they are time consuming. We focus on three such algorithms, namely the classes of large neighborhood search and diving heuristics as well as Simplex pricing strategies. For each class we propose a selection strategy that is updated based on the observed runtime behavior, aiming to ultimately select only the best algorithms for a given instance. We review several common strategies for such a selection scenario under uncertainty, also known as Multi Armed Bandit Problem. In order to apply those bandit strategies, we carefully design reward functions to rank and compare each individual heuristic or pricing algorithm within its respective class. Finally, we discuss the computational benefits of using the proposed adaptive selection within the \scip Optimization Suite on publicly available MIP instances.}, language = {en} } @misc{GamrathKochMartinetal.2013, author = {Gamrath, Gerald and Koch, Thorsten and Martin, Alexander and Miltenberger, Matthias and Weninger, Dieter}, title = {Progress in Presolving for Mixed Integer Programming}, issn = {1438-0064}, doi = {10.1007/s12532-015-0083-5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42530}, year = {2013}, abstract = {Presolving attempts to eliminate redundant information from the problem formulation and simultaneously tries to strengthen the formulation. It can be very effective and is often essential for solving instances. Especially for mixed integer programming problems, fast and effective presolving algorithms are very important. In this paper, we report on three new presolving techniques. The first method searches for singleton continuous columns and tries to fix the corresponding variables. Then we present a presolving technique which exploits a partial order of the variables to induce fixings. Finally, we show an approach based on connected components in graphs. Our computational results confirm the profitable use of the algorithms in practice.}, language = {en} } @incollection{GamrathBertholdHeinzetal.2015, author = {Gamrath, Gerald and Berthold, Timo and Heinz, Stefan and Winkler, Michael}, title = {Structure-Based Primal Heuristics for Mixed Integer Programming}, volume = {13}, booktitle = {Optimization in the Real World}, publisher = {Springer Japan}, isbn = {978-4-431-55419-6}, doi = {10.1007/978-4-431-55420-2_3}, pages = {37 -- 53}, year = {2015}, abstract = {Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They help to reach optimality faster and provide good feasible solutions early in the solving process. In this paper, we present two new primal heuristics which take into account global structures available within MIP solvers to construct feasible solutions at the beginning of the solving process. These heuristics follow a large neighborhood search (LNS) approach and use global structures to define a neighborhood that is with high probability significantly easier to process while (hopefully) still containing good feasible solutions. The definition of the neighborhood is done by iteratively fixing variables and propagating these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. The neighborhood is solved as a sub-MIP and solutions are transferred back to the original problem. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about every third instance and therewith help to improve the average solving time.}, language = {en} } @misc{WitzigBertholdHeinz2016, author = {Witzig, Jakob and Berthold, Timo and Heinz, Stefan}, title = {Experiments with Conflict Analysis in Mixed Integer Programming}, issn = {1438-0064}, doi = {10.1007/978-3-319-59776-8_17}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61087}, year = {2016}, abstract = {The analysis of infeasible subproblems plays an import role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. There are two fundamentally different concepts to generate valid global constraints from infeasible subproblems. The first is to analyze the sequence of implications obtained by domain propagation that led to infeasibility. The result of the analysis is one or more sets of contradicting variable bounds from which so-called conflict constraints can be generated. This concept has its origin in solving satisfiability problems and is similarly used in constraint programming. The second concept is to analyze infeasible linear programming (LP) relaxations. The dual LP solution provides a set of multipliers that can be used to generate a single new globally valid linear constraint. The main contribution of this short paper is an empirical evaluation of two ways to combine both approaches. Experiments are carried out on general MIP instances from standard public test sets such as Miplib2010; the presented algorithms have been implemented within the non-commercial MIP solver SCIP. Moreover, we present a pool-based approach to manage conflicts which addresses the way a MIP solver traverses the search tree better than aging strategies known from SAT solving.}, language = {en} } @misc{GleixnerMaherMuelleretal.2017, author = {Gleixner, Ambros and Maher, Stephen J. and M{\"u}ller, Benjamin and Pedroso, Jo{\~a}o Pedro}, title = {Exact Methods for Recursive Circle Packing}, doi = {10.1007/s10479-018-3115-5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-62039}, year = {2017}, abstract = {Packing rings into a minimum number of rectangles is an optimization problem which appears naturally in the logistics operations of the tube industry. It encompasses two major difficulties, namely the positioning of rings in rectangles and the recursive packing of rings into other rings. This problem is known as the Recursive Circle Packing Problem (RCPP). We present the first dedicated method for solving RCPP that provides strong dual bounds based on an exact Dantzig-Wolfe reformulation of a nonconvex mixed-integer nonlinear programming formulation. The key idea of this reformulation is to break symmetry on each recursion level by enumerating one-level packings, i.e., packings of circles into other circles, and by dynamically generating packings of circles into rectangles. We use column generation techniques to design a "price-and-verify" algorithm that solves this reformulation to global optimality. Extensive computational experiments on a large test set show that our method not only computes tight dual bounds, but often produces primal solutions better than those computed by heuristics from the literature.}, language = {en} } @misc{CheungGleixnerSteffy2016, author = {Cheung, Kevin K. H. and Gleixner, Ambros and Steffy, Daniel}, title = {Verifying Integer Programming Results}, issn = {1438-0064}, doi = {10.1007/978-3-319-59250-3_13}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61044}, year = {2016}, abstract = {Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from programming or algorithmic errors, motivating the desire for a way to produce independently verifiable certificates of claimed results. Due to the complex nature of state-of-the-art MILP solution algorithms, the ideal form of such a certificate is not entirely clear. This paper proposes such a certificate format, illustrating its capabilities and structure through examples. The certificate format is designed with simplicity in mind and is composed of a list of statements that can be sequentially verified using a limited number of simple yet powerful inference rules. We present a supplementary verification tool for compressing and checking these certificates independently of how they were created. We report computational results on a selection of mixed-integer linear programming instances from the literature. To this end, we have extended the exact rational version of the MIP solver SCIP to produce such certificates.}, language = {en} } @article{RehfeldtKoch2019, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem}, volume = {29}, journal = {SIAM Journal on Optimization}, number = {1}, publisher = {Society for Industrial and Applied Mathematics}, doi = {10.1137/17M1145963}, pages = {369 -- 398}, year = {2019}, abstract = {Borne out of a surprising variety of practical applications, the maximum-weight connected subgraph problem has attracted considerable interest during the past years. This interest has not only led to notable research on theoretical properties, but has also brought about several (exact) solvers-with steadily increasing performance. Continuing along this path, the following article introduces several new algorithms such as reduction techniques and heuristics and describes their integration into an exact solver. The new methods are evaluated with respect to both their theoretical and practical properties. Notably, the new exact framework allows to solve common problem instances from the literature faster than all previous approaches. Moreover, one large-scale benchmark instance from the 11th DIMACS Challenge can be solved for the first time to optimality and the primal-dual gap for two other ones can be significantly reduced.}, language = {en} } @misc{FujisawaShinanoWaki2015, author = {Fujisawa, Katsuki and Shinano, Yuji and Waki, Hayato}, title = {Optimization in the Real World}, volume = {13}, journal = {Mathematics for Industry (MFI)}, publisher = {Springer Tokyo Heidelberg New York Dordrecht London}, isbn = {978-4-431-55419-6}, doi = {10.1007/978-4-431-55420-2}, year = {2015}, language = {en} } @inproceedings{BreuerBussieckCaoetal.2018, author = {Breuer, Thomas and Bussieck, Michael and Cao, Karl-Kien and Cebulla, Felix and Fiand, Frederik and Gils, Hans Christian and Gleixner, Ambros and Khabi, Dmitry and Koch, Thorsten and Rehfeldt, Daniel and Wetzel, Manuel}, title = {Optimizing Large-Scale Linear Energy System Problems with Block Diagonal Structure by Using Parallel Interior-Point Methods}, booktitle = {Operations Research Proceedings 2017}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-319-89920-6_85}, pages = {641 -- 647}, year = {2018}, abstract = {Current linear energy system models (ESM) acquiring to provide sufficient detail and reliability frequently bring along problems of both high intricacy and increasing scale. Unfortunately, the size and complexity of these problems often prove to be intractable even for commercial state-of-the-art linear programming solvers. This article describes an interdisciplinary approach to exploit the intrinsic structure of these large-scale linear problems to be able to solve them on massively parallel high-performance computers. A key aspect are extensions to the parallel interior-point solver PIPS-IPM originally developed for stochastic optimization problems. Furthermore, a newly developed GAMS interface to the solver as well as some GAMS language extensions to model block-structured problems will be described.}, language = {en} } @article{FuriniTraversiBelottietal.2019, author = {Furini, Fabio and Traversi, Emiliano and Belotti, Pietro and Frangioni, Antonio and Gleixner, Ambros and Gould, Nick and Liberti, Leo and Lodi, Andrea and Misener, Ruth and Mittelmann, Hans and Sahinidis, Nikolaos V. and Vigerske, Stefan and Wiegele, Angelika}, title = {QPLIB: A Library of Quadratic Programming Instances}, volume = {11}, journal = {Mathematical Programming Computation}, number = {2}, doi = {10.1007/s12532-018-0147-4}, pages = {237 -- 265}, year = {2019}, abstract = {This paper describes a new instance library for Quadratic Programming (QP), i.e., the family of continuous and (mixed)-integer optimization problems where the objective function, the constrains, or both are quadratic. QP is a very diverse class of problems, comprising sub-classes of problems ranging from trivial to undecidable. This diversity is reflected in the variety of solution methods for QP, ranging from entirely combinatorial ones to completely continuous ones, including many for which both aspects are fundamental. Selecting a set of instances of QP that is at the same time not overwhelmingly onerous but sufficiently challenging for the many different interested communities is therefore important. We propose a simple taxonomy for QP instances that leads to a systematic problem selection mechanism. We then briefly survey the field of QP, giving an overview of theory, methods and solvers. Finally, we describe how the library was put together, and detail its final contents.}, language = {en} } @phdthesis{Pulaj2017, author = {Pulaj, Jonad}, title = {Cutting Planes for Union-Closed Families}, year = {2017}, abstract = {Frankl's (union-closed sets) conjecture states that for any nonempty finite union-closed (UC) family of distinct sets there exists an element in at least half of the sets. Poonen's Theorem characterizes the existence of weights which determine whether a given UC family ensures Frankl's conjecture holds for all UC families which contain it. The weight systems are nontrivial to identify for a given UC family, and methods to determine such weight systems have led to several other open questions and conjectures regarding structures in UC families. We design a cutting-plane method that computes the explicit weights which imply the existence conditions of Poonen's Theorem using computational integer programming coupled with redundant verification routines that ensure correctness. We find over one hundred previously unknown families of sets which ensure Frankl's conjecture holds for all families that contain any of them. This improves significantly on all previous results of the kind. Our framework allows us to answer several open questions and conjectures regarding structural properties of UC families, including proving the 3-sets conjecture of Morris from 2006 which characterizes the minimum number of 3-sets that ensure Frankl's conjecture holds for all families that contain them. Furthermore, our method provides a general algorithmic road-map for improving other known results and uncovering structures in UC families.}, language = {en} } @inproceedings{CheungGleixnerSteffy2017, author = {Cheung, Kevin K. H. and Gleixner, Ambros and Steffy, Daniel}, title = {Verifying Integer Programming Results}, volume = {10328}, booktitle = {F. Eisenbrand and J. Koenemann, eds., Integer Programming and Combinatorial Optimization: 19th International Conference, IPCO 2017}, doi = {10.1007/978-3-319-59250-3_13}, pages = {148 -- 160}, year = {2017}, abstract = {Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from programming or algorithmic errors, motivating the desire for a way to produce independently verifiable certificates of claimed results. Due to the complex nature of state-of-the-art MIP solution algorithms, the ideal form of such a certificate is not entirely clear. This paper proposes such a certificate format designed with simplicity in mind, which is composed of a list of statements that can be sequentially verified using a limited number of inference rules. We present a supplementary verification tool for compressing and checking these certificates independently of how they were created. We report computational results on a selection of MIP instances from the literature. To this end, we have extended the exact rational version of the MIP solver SCIP to produce such certificates.}, language = {en} } @inproceedings{RehfeldtKoch2018, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {SCIP-Jack—a solver for STP and variants with parallelization extensions: An update}, booktitle = {Operations Research Proceedings 2017}, pages = {191 -- 196}, year = {2018}, abstract = {The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. Although the different Steiner tree problem variants are usually strongly related, solution approaches employed so far have been prevalently problem-specific. Against this backdrop, the solver SCIP-Jack was created as a general-purpose framework that can be used to solve the classical Steiner tree problem and 11 of its variants. This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. Furthermore, SCIP-Jack includes various newly developed algorithmic components such as preprocessing routines and heuristics. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances. After the introduction of SCIP-Jack at the 2014 DIMACS Challenge on Steiner problems, the overall performance of the solver has considerably improved. This article provides an overview on the current state.}, language = {en} } @article{VierhausFuegenschuhGottwaldetal.2017, author = {Vierhaus, Ingmar and F{\"u}genschuh, Armin and Gottwald, Robert Lion and Gr{\"o}sser, Stefan}, title = {Using white-box nonlinear optimization methods in system dynamics policy improvement}, volume = {33}, journal = {System Dynamics Review}, number = {2}, doi = {10.1002/sdr.1583}, pages = {138 -- 168}, year = {2017}, abstract = {We present a new strategy for the direct optimization of the values of policy functions. This approach is particularly well suited to model actors with a global perspective on the system and relies heavily on modern mathematical white-box optimization methods. We demonstrate our strategy on two classical models: market growth and World2. Each model is first transformed into an optimization problem by defining how the actor can influence the models' dynamics and by choosing objective functions to measure improvements. To improve comparability between different runs, we also introduce a comparison measure for possible interventions. We solve the optimization problems, discuss the resulting policies and compare them to the existing results from the literature. In particular, we present a run of the World2 model which significantly improves the published "towards a global equilibrium" run with equal cost of intervention.}, language = {en} } @inproceedings{SchadeSchlechteWitzig2018, author = {Schade, Stanley and Schlechte, Thomas and Witzig, Jakob}, title = {Structure-based Decomposition for Pattern-Detection for Railway Timetables}, booktitle = {Operations Research Proceedings 2017}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-319-89920-6_95}, pages = {715 -- 721}, year = {2018}, 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} } @masterthesis{Wischlinsky2017, type = {Bachelor Thesis}, author = {Wischlinsky, William}, title = {Feasibility-based bound tightening via linear programming}, year = {2017}, language = {en} } @misc{GleixnerBastubbeEifleretal.2018, author = {Gleixner, Ambros and Bastubbe, Michael and Eifler, Leon and Gally, Tristan and Gamrath, Gerald and Gottwald, Robert Lion and Hendel, Gregor and Hojny, Christopher and Koch, Thorsten and L{\"u}bbecke, Marco and Maher, Stephen J. and Miltenberger, Matthias and M{\"u}ller, Benjamin and Pfetsch, Marc and Puchert, Christian and Rehfeldt, Daniel and Schl{\"o}sser, Franziska and Schubert, Christoph and Serrano, Felipe and Shinano, Yuji and Viernickel, Jan Merlin and Walter, Matthias and Wegscheider, Fabian and Witt, Jonas T. and Witzig, Jakob}, title = {The SCIP Optimization Suite 6.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69361}, year = {2018}, abstract = {The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 6.0 of the SCIP Optimization Suite. Besides performance improvements of the MIP and MINLP core achieved by new primal heuristics and a new selection criterion for cutting planes, one focus of this release are decomposition algorithms. Both SCIP and the automatic decomposition solver GCG now include advanced functionality for performing Benders' decomposition in a generic framework. GCG's detection loop for structured matrices and the coordination of pricing routines for Dantzig-Wolfe decomposition has been significantly revised for greater flexibility. Two SCIP extensions have been added to solve the recursive circle packing problem by a problem-specific column generation scheme and to demonstrate the use of the new Benders' framework for stochastic capacitated facility location. Last, not least, the report presents updates and additions to the other components and extensions of the SCIP Optimization Suite: the LP solver SoPlex, the modeling language Zimpl, the parallelization framework UG, the Steiner tree solver SCIP-Jack, and the mixed-integer semidefinite programming solver SCIP-SDP.}, language = {en} } @misc{WeberSagerGleixner2018, author = {Weber, Tobias and Sager, Sebastian and Gleixner, Ambros}, title = {Solving Quadratic Programs to High Precision using Scaled Iterative Refinement}, issn = {1438-0064}, doi = {10.1007/s12532-019-00154-6}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-68152}, year = {2018}, abstract = {Quadratic optimization problems (QPs) are ubiquitous, and solution algorithms have matured to a reliable technology. However, the precision of solutions is usually limited due to the underlying floating-point operations. This may cause inconveniences when solutions are used for rigorous reasoning. We contribute on three levels to overcome this issue. First, we present a novel refinement algorithm to solve QPs to arbitrary precision. It iteratively solves refined QPs, assuming a floating-point QP solver oracle. We prove linear convergence of residuals and primal errors. Second, we provide an efficient implementation, based on SoPlex and qpOASES that is publicly available in source code. Third, we give precise reference solutions for the Maros and M{\´e}sz{\´a}ros benchmark library.}, language = {en} } @article{WeberSagerGleixner2019, author = {Weber, Tobias and Sager, Sebastian and Gleixner, Ambros}, title = {Solving Quadratic Programs to High Precision using Scaled Iterative Refinement}, volume = {11}, journal = {Mathematical Programming Computation}, publisher = {Springer Berlin Heidelberg}, doi = {10.1007/s12532-019-00154-6}, pages = {421 -- 455}, year = {2019}, abstract = {Quadratic optimization problems (QPs) are ubiquitous, and solution algorithms have matured to a reliable technology. However, the precision of solutions is usually limited due to the underlying floating-point operations. This may cause inconveniences when solutions are used for rigorous reasoning. We contribute on three levels to overcome this issue. First, we present a novel refinement algorithm to solve QPs to arbitrary precision. It iteratively solves refined QPs, assuming a floating-point QP solver oracle. We prove linear convergence of residuals and primal errors. Second, we provide an efficient implementation, based on SoPlex and qpOASES that is publicly available in source code. Third, we give precise reference solutions for the Maros and M{\´e}sz{\´a}ros benchmark library.}, language = {en} } @article{KochAchterbergAndersenetal.2011, author = {Koch, Thorsten and Achterberg, Tobias and Andersen, Erling and Bastert, Oliver and Berthold, Timo and Bixby, Robert E. and Danna, Emilie and Gamrath, Gerald and Gleixner, Ambros and Heinz, Stefan and Lodi, Andrea and Mittelmann, Hans and Ralphs, Ted and Salvagnin, Domenico and Steffy, Daniel and Wolter, Kati}, title = {MIPLIB 2010}, volume = {3}, journal = {Mathematical Programming Computation}, number = {2}, doi = {10.1007/s12532-011-0025-9}, pages = {103 -- 163}, year = {2011}, language = {en} } @article{Gamrath2013, author = {Gamrath, Gerald}, title = {Improving strong branching by propagation}, volume = {7874}, journal = {Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems}, editor = {Gomes, Carla and Sellmann, Meinolf}, publisher = {Springer Berlin Heidelberg}, doi = {10.1007/978-3-642-38171-3_25}, pages = {347 -- 354}, year = {2013}, abstract = {Strong branching is an important component of most variable selection rules in branch-and-bound based mixed-integer linear programming solvers. It predicts the dual bounds of potential child nodes by solving auxiliary LPs and thereby helps to keep the branch-and-bound tree small. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Computational experiments on standard MIP instances indicate that this is beneficial in three aspects: It helps to reduce the average number of LP iterations per strong branching call, the number of branch-and-bound nodes, and the overall solving time.}, language = {en} } @inproceedings{FuegenschuhHillerHumpolaetal.2011, author = {F{\"u}genschuh, Armin and Hiller, Benjamin and Humpola, Jesco and Koch, Thorsten and Lehmann, Thomas and Schwarz, Robert and Schweiger, Jonas and Szabo, Jacint}, title = {Gas Network Topology Optimization for Upcoming Market Requirements}, booktitle = {International Conference on the European Energy Market (EEM)}, doi = {10.1109/EEM.2011.5953035}, pages = {346 -- 351}, year = {2011}, abstract = {Gas distribution networks are complex structures that consist of passive pipes, and active, controllable elements such as valves and compressors. Controlling such network means to find a suitable setting for all active components such that a nominated amount of gas can be transmitted from entries to exits through the network, without violating physical or operational constraints. The control of a large-scale gas network is a challenging task from a practical point of view. In most companies the actual controlling process is supported by means of computer software that is able to simulate the flow of the gas. However, the active settings have to be set manually within such simulation software. The solution quality thus depends on the experience of a human planner. When the gas network is insufficient for the transport then topology extensions come into play. Here a set of new pipes or active elements is determined such that the extended network admits a feasible control again. The question again is how to select these extensions and where to place them such that the total extension costs are minimal. Industrial practice is again to use the same simulation software, determine extensions by experience, add them to the virtual network, and then try to find a feasible control of the active elements. The validity of this approach now depends even more on the human planner. Another weakness of this manual simulation-based approach is that it cannot establish infeasibility of a certain gas nomination, unless all settings of the active elements are tried. Moreover, it is impossible to find a cost-optimal network extension in this way. In order to overcome these shortcomings of the manual planning approach we present a new approach, rigorously based on mathematical optimization. Hereto we describe a model for finding feasible controls and then extend this model such that topology extensions can additionally and simultaneously be covered. Numerical results for real-world instances are presented and discussed.}, 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} } @inproceedings{HeinzSchulz2011, author = {Heinz, Stefan and Schulz, Jens}, title = {Explanations for the Cumulative Constraint: An Experimental Study}, volume = {6630}, booktitle = {Experimental Algorithms}, pages = {400 -- 409}, year = {2011}, language = {en} } @article{GleixnerHeldHuangetal.2012, author = {Gleixner, Ambros and Held, Harald and Huang, Wei and Vigerske, Stefan}, title = {Towards globally optimal operation of water supply networks}, volume = {2}, journal = {Numerical Algebra, Control and Optimization}, number = {4}, doi = {10.3934/naco.2012.2.695}, pages = {695 -- 711}, year = {2012}, abstract = {This paper is concerned with optimal operation of pressurized water supply networks at a fixed point in time. We use a mixed-integer nonlinear programming (MINLP) model incorporating both the nonlinear physical laws and the discrete decisions such as switching pumps on and off. We demonstrate that for instances from our industry partner, these stationary models can be solved to ε-global optimality within small running times using problem-specific presolving and state-of-the-art MINLP algorithms. In our modeling, we emphasize the importance of distinguishing between what we call real and imaginary flow, i.e., taking into account that the law of Darcy-Weisbach correlates pressure difference and flow along a pipe if and only if water is available at the high pressure end of a pipe. Our modeling solution extends to the dynamic operative planning problem.}, language = {en} }