@misc{Gleixner, type = {Master Thesis}, author = {Gleixner, Ambros}, title = {Solving Large-scale Open Pit Mining Production Scheduling Problems by Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11389}, school = {Zuse Institute Berlin (ZIB)}, abstract = {Since the initial application of mathematical optimisation methods to mine planning in 1965, the Lerchs-Grossmann algorithm for computing the ultimate pit limit, operations researchers have worked on a variety of challenging problems in the area of open pit mining. This thesis focuses on the open pit mining production scheduling problem: Given the discretisation of an orebody as a block model, determine the sequence in which the blocks should be removed from the pit, over the lifespan of the mine, such that the net present value of the mining operation is maximised. In practise, when some material has been removed from the pit, it must be processed further in order to extract the valuable elements contained therein. If the concentration of valuable elements is not sufficiently high, the material is discarded as waste or stockpiled. Realistically-sized block models can contain hundreds of thousands of blocks. A common approach to render these problem instances computationally tractable is the aggregation of blocks to larger scheduling units. The thrust of this thesis is the investigation of a new mixed-integer programming formulation for the open pit mining production scheduling problem, which allows for processing decisions to be made at block level, while the actual mining schedule is still computed at aggregate level. A drawback of this model in its full form is the large number of additional variables needed to model the processing decisions. One main result of this thesis shows how these processing variables can be aggregated efficiently to reduce the problem size significantly, while practically incurring no loss in net present value. The second focus is on the application of lagrangean relaxation to the resource constraints. Using a result of M{\"o}hring et al. (2003) for project scheduling, the lagrangean relaxation can be solved efficiently via minimum cut computations in a weighted digraph. Experiments with a bundle algorithm implementation by Helmberg showed how the lagrangean dual can be solved within a small fraction of the time required by standard linear programming algorithms, while yielding practically the same dual bound. Finally, several problem-specific heuristics are presented together with computational results: two greedy sub-MIP start heuristics and a large neighbourhood search heuristic. A combination of a lagrangean-based start heuristic followed by a large neighbourhood search proved to be effective in generating solutions with objective values within a 0.05\% gap of the optimum.}, language = {en} } @misc{BleyGleixnerKochetal., author = {Bley, Andreas and Gleixner, Ambros and Koch, Thorsten and Vigerske, Stefan}, title = {Comparing MIQCP solvers to a specialised algorithm for mine production scheduling}, organization = {ZIB}, issn = {1438-0064}, doi = {10.1007/978-3-642-25707-0}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11507}, number = {09-32}, abstract = {In this paper we investigate the performance of several out-of-the box solvers for mixed-integer quadratically constrained programmes (MIQCPs) on an open pit mine production scheduling problem with mixing constraints. We compare the solvers BARON, Couenne, SBB, and SCIP to a problem-specific algorithm on two different MIQCP formulations. The computational results presented show that general-purpose solvers with no particular knowledge of problem structure are able to nearly match the performance of a hand-crafted algorithm.}, language = {en} } @misc{KochAchterbergAndersenetal.2010, 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}, doi = {10.1007/s12532-011-0025-9}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12953}, number = {10-31}, year = {2010}, abstract = {This paper reports on the fifth version of the Mixed Integer Programming Library. The MIPLIB 2010 is the first MIPLIB release that has been assembled by a large group from academia and from industry, all of whom work in integer programming. There was mutual consent that the concept of the library had to be expanded in order to fulfill the needs of the community. The new version comprises 361 instances sorted into several groups. This includes the main benchmark test set of 87 instances, which are all solvable by today's codes, and also the challenge test set with 164 instances, many of which are currently unsolved. For the first time, we include scripts to run automated tests in a predefined way. Further, there is a solution checker to test the accuracy of provided solutions using exact arithmetic.}, language = {en} } @misc{BertholdGleixner, author = {Berthold, Timo and Gleixner, Ambros}, title = {Undercover Branching}, issn = {1438-0064}, doi = {10.1007/978-3-642-38527-8_20}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-18030}, abstract = {In this paper, we present a new branching strategy for nonconvex MINLP that aims at driving the created subproblems towards linearity. It exploits the structure of a minimum cover of an MINLP, a smallest set of variables that, when fixed, render the remaining system linear: whenever possible, branching candidates in the cover are preferred. Unlike most branching strategies for MINLP, Undercover branching is not an extension of an existing MIP branching rule. It explicitly regards the nonlinearity of the problem while branching on integer variables with a fractional relaxation solution. Undercover branching can be naturally combined with any variable-based branching rule. We present computational results on a test set of general MINLPs from MINLPLib, using the new strategy in combination with reliability branching and pseudocost branching. The computational cost of Undercover branching itself proves negligible. While it turns out that it can influence the variable selection only on a smaller set of instances, for those that are affected, significant improvements in performance are achieved.}, language = {en} } @misc{BertholdGleixner, author = {Berthold, Timo and Gleixner, Ambros}, title = {Undercover: a primal MINLP heuristic exploring a largest sub-MIP}, issn = {1438-0064}, doi = {10.1007/s10107-013-0635-2}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14631}, number = {12-07}, abstract = {We present Undercover, a primal heuristic for nonconvex mixed-integer nonlinear programming (MINLP) that explores a mixed-integer linear subproblem (sub-MIP) of a given MINLP. We solve a vertex covering problem to identify a minimal set of variables that need to be fixed in order to linearize each constraint, a so-called cover. Subsequently, these variables are fixed to values obtained from a reference point, e.g., an optimal solution of a linear relaxation. We apply domain propagation and conflict analysis to try to avoid infeasibilities and learn from them, respectively. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem. We present computational results on a test set of mixed-integer quadratically constrained programs (MIQCPs) and general MINLPs from MINLPLib. It turns out that the majority of these instances allow for small covers. Although general in nature, the heuristic appears most promising for MIQCPs, and complements nicely with existing root node heuristics in different state-of-the-art solvers.}, language = {en} } @misc{Gleixner, author = {Gleixner, Ambros}, title = {Factorization and update of a reduced basis matrix for the revised simplex method}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-16349}, abstract = {In this paper, we describe a method to enhance the FTRAN and BTRAN operations in the revised simplex algorithm by using a reduced basis matrix defined by basic columns and nonbasic rows. This submatrix of the standard basis matrix is potentially much smaller, but may change its dimension dynamically from iteration to iteration. For the classical product form update ("eta update"), the idea has been noted already by Zoutendijk, but only preliminarily tested by Powell in the early 1970s. We extend these ideas to Forrest-Tomlin type update formulas for an LU factorization of the reduced basis matrix, which are suited for efficient implementation within a state-of-the-art simplex solver. The computational advantages of the proposed method apply to pure LP solving as well as to LP-based branch-and-cut algorithms. It can easily be integrated into existing simplex codes.}, language = {en} } @misc{GleixnerWeltge, author = {Gleixner, Ambros and Weltge, Stefan}, title = {Learning and Propagating Lagrangian Variable Bounds for Mixed-Integer Nonlinear Programming}, issn = {1438-0064}, doi = {10.1007/978-3-642-38171-3_26}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17631}, abstract = {Optimization-based bound tightening (OBBT) is a domain reduction technique commonly used in nonconvex mixed-integer nonlinear programming that solves a sequence of auxiliary linear programs. Each variable is minimized and maximized to obtain the tightest bounds valid for a global linear relaxation. This paper shows how the dual solutions of the auxiliary linear programs can be used to learn what we call Lagrangian variable bound constraints. These are linear inequalities that explain OBBT's domain reductions in terms of the bounds on other variables and the objective value of the incumbent solution. Within a spatial branch-and-bound algorithm, they can be learnt a priori (during OBBT at the root node) and propagated within the search tree at very low computational cost. Experiments with an implementation inside the MINLP solver SCIP show that this reduces the number of branch-and-bound nodes and speeds up solution times.}, language = {en} } @misc{BertholdGleixnerHeinzetal., author = {Berthold, Timo and Gleixner, Ambros and Heinz, Stefan and Vigerske, Stefan}, title = {Analyzing the computational impact of MIQCP solver components}, issn = {1438-0064}, doi = {10.3934/naco.2012.2.739}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17754}, abstract = {We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on a linear relaxation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances.}, language = {en} } @article{BolandDumitrescuFroylandetal.2009, author = {Boland, Natashia and Dumitrescu, Irina and Froyland, Gary and Gleixner, Ambros}, title = {LP-based disaggregation approaches to solving the open pit mining production scheduling problem with block processing selectivity}, series = {Computers \& Operations Research}, volume = {36}, journal = {Computers \& Operations Research}, pages = {1064 -- 1089}, year = {2009}, language = {en} } @misc{Gleixner2008, type = {Master Thesis}, author = {Gleixner, Ambros}, title = {Solving Large-scale Open Pit Mining Production Scheduling Problems by Integer Programming}, year = {2008}, language = {en} } @article{BertholdGleixner2014, author = {Berthold, Timo and Gleixner, Ambros}, title = {Undercover: a primal MINLP heuristic exploring a largest sub-MIP}, series = {Mathematical Programming}, volume = {144}, journal = {Mathematical Programming}, number = {1-2}, doi = {10.1007/s10107-013-0635-2}, pages = {315 -- 346}, year = {2014}, abstract = {We present Undercover, a primal heuristic for nonconvex mixed-integer nonlinear programming (MINLP) that explores a mixed-integer linear subproblem (sub-MIP) of a given MINLP. We solve a vertex covering problem to identify a minimal set of variables that need to be fixed in order to linearize each constraint, a so-called cover. Subsequently, these variables are fixed to values obtained from a reference point, e.g., an optimal solution of a linear relaxation. We apply domain propagation and conflict analysis to try to avoid infeasibilities and learn from them, respectively. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem. We present computational results on a test set of mixed-integer quadratically constrained programs (MIQCPs) and general MINLPs from MINLPLib. It turns out that the majority of these instances allow for small covers. Although general in nature, the heuristic appears most promising for MIQCPs, and complements nicely with existing root node heuristics in different state-of-the-art solvers.}, language = {en} } @inproceedings{GamrathMelchioriBertholdetal., author = {Gamrath, Gerald and Melchiori, Anna and Berthold, Timo and Gleixner, Ambros and Salvagnin, Domenico}, title = {Branching on Multi-aggregated Variables}, series = {Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2015}, volume = {9075}, booktitle = {Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2015}, doi = {10.1007/978-3-319-18008-3_10}, pages = {141 -- 156}, 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} } @inproceedings{CaoGleixnerMiltenberger, 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}, series = {EnInnov 2016: 14. Symposium Energieinnovation 2016}, booktitle = {EnInnov 2016: 14. Symposium Energieinnovation 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} } @misc{CheungGleixnerSteffy, 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}, 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} } @misc{GamrathGleixnerKochetal., 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}, 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} } @article{GleixnerBertholdMuelleretal., author = {Gleixner, Ambros and Berthold, Timo and M{\"u}ller, Benjamin and Weltge, Stefan}, title = {Three Enhancements for Optimization-Based Bound Tightening}, series = {Journal of Global Optimization}, volume = {67}, journal = {Journal of Global Optimization}, number = {4}, doi = {10.1007/s10898-016-0450-4}, pages = {731 -- 757}, 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} } @article{VigerskeGleixner, author = {Vigerske, Stefan and Gleixner, Ambros}, title = {SCIP: Global Optimization of Mixed-Integer Nonlinear Programs in a Branch-and-Cut Framework}, series = {Optimization Methods \& Software}, volume = {33}, journal = {Optimization Methods \& Software}, number = {3}, doi = {10.1080/10556788.2017.1335312}, pages = {563 -- 593}, abstract = {This paper describes the extensions that were added to the constraint integer programming framework SCIP in order to enable it to solve convex and nonconvex mixed-integer nonlinear programs (MINLPs) to global optimality. SCIP implements a spatial branch-and-bound algorithm based on a linear outer-approximation, which is computed by convex over- and underestimation of nonconvex functions. An expression graph representation of nonlinear constraints allows for bound tightening, structure analysis, and reformulation. Primal heuristics are employed throughout the solving process to find feasible solutions early. We provide insights into the performance impact of individual MINLP solver components via a detailed computational study over a large and heterogeneous test set.}, language = {en} } @article{BertholdGleixnerHeinzetal.2012, author = {Berthold, Timo and Gleixner, Ambros and Heinz, Stefan and Vigerske, Stefan}, title = {Analyzing the computational impact of MIQCP solver components}, series = {Numerical Algebra, Control and Optimization}, volume = {2}, journal = {Numerical Algebra, Control and Optimization}, number = {4}, doi = {10.3934/naco.2012.2.739}, pages = {739 -- 748}, year = {2012}, abstract = {We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on a linear relaxation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances.}, language = {en} } @inproceedings{GleixnerWeltge2013, author = {Gleixner, Ambros and Weltge, Stefan}, title = {Learning and Propagating Lagrangian Variable Bounds for Mixed-Integer Nonlinear Programming}, series = {Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 10th International Conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18-22, 2013}, volume = {7874}, booktitle = {Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 10th International Conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18-22, 2013}, doi = {10.1007/978-3-642-38171-3_26}, pages = {355 -- 361}, year = {2013}, abstract = {Optimization-based bound tightening (OBBT) is a domain reduction technique commonly used in nonconvex mixed-integer nonlinear programming that solves a sequence of auxiliary linear programs. Each variable is minimized and maximized to obtain the tightest bounds valid for a global linear relaxation. This paper shows how the dual solutions of the auxiliary linear programs can be used to learn what we call Lagrangian variable bound constraints. These are linear inequalities that explain OBBT's domain reductions in terms of the bounds on other variables and the objective value of the incumbent solution. Within a spatial branch-and-bound algorithm, they can be learnt a priori (during OBBT at the root node) and propagated within the search tree at very low computational cost. Experiments with an implementation inside the MINLP solver SCIP show that this reduces the number of branch-and-bound nodes and speeds up solution times.}, language = {en} } @inproceedings{BertholdGleixner2013, author = {Berthold, Timo and Gleixner, Ambros}, title = {Undercover Branching}, series = {Experimental Algorithms, 12th International Symposium, SEA 2013, Rome, Italy, June 5-7, 2013, Proceedings}, volume = {7933}, booktitle = {Experimental Algorithms, 12th International Symposium, SEA 2013, Rome, Italy, June 5-7, 2013, Proceedings}, editor = {Bonifaci, Vincenzo and Demetrescu, Camil and Marchetti-Spaccamela, Alberto}, doi = {10.1007/978-3-642-38527-8_20}, pages = {212 -- 223}, year = {2013}, abstract = {In this paper, we present a new branching strategy for nonconvex MINLP that aims at driving the created subproblems towards linearity. It exploits the structure of a minimum cover of an MINLP, a smallest set of variables that, when fixed, render the remaining system linear: whenever possible, branching candidates in the cover are preferred. Unlike most branching strategies for MINLP, Undercover branching is not an extension of an existing MIP branching rule. It explicitly regards the nonlinearity of the problem while branching on integer variables with a fractional relaxation solution. Undercover branching can be naturally combined with any variable-based branching rule. We present computational results on a test set of general MINLPs from MINLPLib, using the new strategy in combination with reliability branching and pseudocost branching. The computational cost of Undercover branching itself proves negligible. While it turns out that it can influence the variable selection only on a smaller set of instances, for those that are affected, significant improvements in performance are achieved.}, language = {en} } @inproceedings{BertholdGleixnerHeinzetal.2012, author = {Berthold, Timo and Gleixner, Ambros and Heinz, Stefan and Koch, Thorsten and Shinano, Yuji}, title = {SCIP Optimization Suite を利用した 混合整数(線形/非線形) 計画問題の解法}, series = {Proceedings of the 24th RAMP symposium. The Operations Society of Japan, RAMP: Research Association of Mathematical Programming}, booktitle = {Proceedings of the 24th RAMP symposium. The Operations Society of Japan, RAMP: Research Association of Mathematical Programming}, pages = {165 -- 192}, year = {2012}, abstract = {この論文ではソフトウェア・パッケージSCIP Optimization Suite を紹介し,その3つの構成要素:モデリン グ言語Zimpl, 線形計画(LP: linear programming) ソルバSoPlex, そして,制約整数計画(CIP: constraint integer programming) に対するソフトウェア・フレームワークSCIP, について述べる.本論文では,この3つの 構成要素を利用して,どのようにして挑戦的な混合整数線形計画問題(MIP: mixed integer linear optimization problems) や混合整数非線形計画問題(MINLP: mixed integer nonlinear optimization problems) をモデル化 し解くのかを説明する.SCIP は,現在,最も高速なMIP,MINLP ソルバの1つである.いくつかの例により, Zimpl, SCIP, SoPlex の利用方法を示すとともに,利用可能なインタフェースの概要を示す.最後に,将来の開 発計画の概要について述べる.}, language = {ja} } @inproceedings{BleyGleixnerKochetal.2012, author = {Bley, Andreas and Gleixner, Ambros and Koch, Thorsten and Vigerske, Stefan}, title = {Comparing MIQCP Solvers to a Specialised Algorithm for Mine Production Scheduling}, series = {Modeling, Simulation and Optimization of Complex Processes. Proceedings of the Fourth International Conference on High Performance Scientific Computing, March 2-6, 2009, Hanoi, Vietnam}, booktitle = {Modeling, Simulation and Optimization of Complex Processes. Proceedings of the Fourth International Conference on High Performance Scientific Computing, March 2-6, 2009, Hanoi, Vietnam}, doi = {10.1007/978-3-642-25707-0_3}, pages = {25 -- 39}, year = {2012}, abstract = {In this paper we investigate the performance of several out-of-the box solvers for mixed-integer quadratically constrained programmes (MIQCPs) on an open pit mine production scheduling problem with mixing constraints. We compare the solvers BARON, Couenne, SBB, and SCIP to a problem-specific algorithm on two different MIQCP formulations. The computational results presented show that general-purpose solvers with no particular knowledge of problem structure are able to nearly match the performance of a hand-crafted algorithm.}, language = {en} } @inproceedings{GleixnerSteffyWolter2012, author = {Gleixner, Ambros and Steffy, Daniel and Wolter, Kati}, title = {Improving the Accuracy of Linear Programming Solvers with Iterative Refinement}, series = {ISSAC '12. Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation}, booktitle = {ISSAC '12. Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation}, doi = {10.1145/2442829.2442858}, pages = {187 -- 194}, year = {2012}, 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}, series = {Proceedings of the European Workshop on Mixed Integer Nonlinear Programming, April 12-16, 2010, Marseilles, France}, 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} } @article{GleixnerHeldHuangetal.2012, author = {Gleixner, Ambros and Held, Harald and Huang, Wei and Vigerske, Stefan}, title = {Towards globally optimal operation of water supply networks}, series = {Numerical Algebra, Control and Optimization}, 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} } @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}, series = {Mathematical Programming Computation}, volume = {3}, journal = {Mathematical Programming Computation}, number = {2}, doi = {10.1007/s12532-011-0025-9}, pages = {103 -- 163}, year = {2011}, language = {en} } @misc{BertholdGleixnerHeinzetal., author = {Berthold, Timo and Gleixner, Ambros and Heinz, Stefan and Koch, Thorsten and Shinano, Yuji}, title = {SCIP Optimization Suite を利用した 混合整数(線形/非線形) 計画問題の解法}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-15598}, abstract = {この論文ではソフトウェア・パッケージSCIP Optimization Suite を紹介し,その3つの構成要素:モデリン グ言語Zimpl, 線形計画(LP: linear programming) ソルバSoPlex, そして,制約整数計画(CIP: constraint integer programming) に対するソフトウェア・フレームワークSCIP, について述べる.本論文では,この3つの 構成要素を利用して,どのようにして挑戦的な混合整数線形計画問題(MIP: mixed integer linear optimization problems) や混合整数非線形計画問題(MINLP: mixed integer nonlinear optimization problems) をモデル化 し解くのかを説明する.SCIP は,現在,最も高速なMIP,MINLP ソルバの1つである.いくつかの例により, Zimpl, SCIP, SoPlex の利用方法を示すとともに,利用可能なインタフェースの概要を示す.最後に,将来の開 発計画の概要について述べる.}, language = {ja} } @misc{GleixnerHeldHuangetal., author = {Gleixner, Ambros and Held, Harald and Huang, Wei and Vigerske, Stefan}, title = {Towards globally optimal operation of water supply networks}, issn = {1438-0064}, doi = {10.3934/naco.2012.2.695}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-15603}, 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} } @misc{BertholdGamrathGleixneretal., author = {Berthold, Timo and Gamrath, Gerald and Gleixner, Ambros and Heinz, Stefan and Koch, Thorsten and Shinano, Yuji}, title = {Solving mixed integer linear and nonlinear problems using the SCIP Optimization Suite}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-15654}, abstract = {This paper introduces the SCIP Optimization Suite and discusses the capabilities of its three components: the modeling language Zimpl, the linear programming solver SoPlex, and the constraint integer programming framework SCIP. We explain how these can be used in concert to model and solve challenging mixed integer linear and nonlinear optimization problems. SCIP is currently one of the fastest non-commercial MIP and MINLP solvers. We demonstrate the usage of Zimpl, SCIP, and SoPlex by selected examples, we give an overview of available interfaces, and outline plans for future development.}, language = {en} } @misc{VigerskeGleixner, author = {Vigerske, Stefan and Gleixner, Ambros}, title = {SCIP: Global Optimization of Mixed-Integer Nonlinear Programs in a Branch-and-Cut Framework}, issn = {1438-0064}, doi = {10.1080/10556788.2017.1335312}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-59377}, abstract = {This paper describes the extensions that were added to the constraint integer programming framework SCIP in order to enable it to solve convex and nonconvex mixed-integer nonlinear programs (MINLPs) to global optimality. SCIP implements a spatial branch-and-bound algorithm based on a linear outer-approximation, which is computed by convex over- and underestimation of nonconvex functions. An expression graph representation of nonlinear constraints allows for bound tightening, structure analysis, and reformulation. Primal heuristics are employed throughout the solving process to find feasible solutions early. We provide insights into the performance impact of individual MINLP solver components via a detailed computational study over a large and heterogeneous test set.}, language = {en} } @inproceedings{D'AndreagiovanniGleixner, author = {D'Andreagiovanni, Fabio and Gleixner, Ambros}, title = {Towards an accurate solution of wireless network design problems}, series = {Cerulli R., Fujishige S., Mahjoub A. (eds) Combinatorial Optimization. ISCO 2016}, booktitle = {Cerulli R., Fujishige S., Mahjoub A. (eds) Combinatorial Optimization. ISCO 2016}, doi = {10.1007/978-3-319-45587-7_12}, pages = {135 -- 147}, 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} } @phdthesis{Gleixner, author = {Gleixner, Ambros}, title = {Exact and Fast Algorithms for Mixed-Integer Nonlinear Programming}, publisher = {Logos Verlag Berlin}, isbn = {978-3-8325-4190-3}, pages = {341}, abstract = {Mixed-integer nonlinear programming (MINLP) comprises the broad class of finite-dimensional mathematical optimization problems from mixed-integer linear programming and global optimization. The combination of the two disciplines allows us to construct more accurate models of real-world systems, while at the same time it increases the algorithmic challenges that come with solving them. This thesis presents new methods that improve the numerical reliability and the computational performance of global MINLP solvers. Since state-of-the-art algorithms for nonconvex MINLP fundamentally rely on solving linear programming (LP) relaxations, we address numerical accuracy directly for LP by means of LP iterative refinement: a new algorithm to solve linear programs to arbitrarily high levels of precision. The thesis is supplemented by an exact extension of the LP solver SoPlex, which proves on average 1.85 to 3 times faster than current state-of-the-art software for solving general linear programs exactly over the rational numbers. These methods can be generalized to quadratic programming. We study their application to numerically difficult multiscale LP models for metabolic networks in systems biology. To improve the computational performance of LP-based MINLP solvers, we show how the expensive, but effective, bound-tightening technique called optimization-based bound tightening can be approximated more efficiently via feasibility-based bound tightening. The resulting implementation increases the number of instances that can be solved and reduces the average running time of the MINLP solver SCIP by 17-19\% on hard mixed-integer nonlinear programs. Last, we present branching rules that exploit the presence of nonlinear integer variables, i.e., variables both contained in nonlinear terms and required to be integral. The new branching rules prefer integer variables when performing spatial branching, and favor variables in nonlinear terms when resolving integer infeasibility. They reduce the average running time of SCIP by 17\% on affected instances. Most importantly, all of the new methods enable us to solve problems which could not be solved before, either due to their numerical complexity or because of limited computing resources.}, language = {en} } @article{GleixnerSteffyWolter, author = {Gleixner, Ambros and Steffy, Daniel and Wolter, Kati}, title = {Iterative Refinement for Linear Programming}, series = {INFORMS Journal on Computing}, volume = {28}, journal = {INFORMS Journal on Computing}, number = {3}, doi = {10.1287/ijoc.2016.0692}, pages = {449 -- 464}, abstract = {We describe an iterative refinement procedure for computing extended precision or exact solutions to linear programming problems (LPs). Arbitrarily precise solutions can be computed by solving a sequence of closely related LPs with limited precision arithmetic. The LPs solved share the same constraint matrix as the original problem instance and are transformed only by modification of the objective function, right-hand side, and variable bounds. Exact computation is used to compute and store the exact representation of the transformed problems, while numeric computation is used for solving LPs. At all steps of the algorithm the LP bases encountered in the transformed problems correspond directly to LP bases in the original problem description. We show that this algorithm is effective in practice for computing extended precision solutions and that it leads to a direct improvement of the best known methods for solving LPs exactly over the rational numbers. Our implementation is publically available as an extension of the academic LP solver SoPlex.}, language = {en} } @misc{GamrathMelchioriBertholdetal., 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}, 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{GleixnerSteffyWolter, author = {Gleixner, Ambros and Steffy, Daniel and Wolter, Kati}, title = {Iterative Refinement for Linear Programming}, issn = {1438-0064}, doi = {10.1287/ijoc.2016.0692}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-55118}, abstract = {We describe an iterative refinement procedure for computing extended precision or exact solutions to linear programming problems (LPs). Arbitrarily precise solutions can be computed by solving a sequence of closely related LPs with limited precision arithmetic. The LPs solved share the same constraint matrix as the original problem instance and are transformed only by modification of the objective function, right-hand side, and variable bounds. Exact computation is used to compute and store the exact representation of the transformed problems, while numeric computation is used for solving LPs. At all steps of the algorithm the LP bases encountered in the transformed problems correspond directly to LP bases in the original problem description. We show that this algorithm is effective in practice for computing extended precision solutions and that it leads to a direct improvement of the best known methods for solving LPs exactly over the rational numbers. Our implementation is publically available as an extension of the academic LP solver SoPlex.}, language = {en} } @misc{GeorgesGleixnerGojicetal., 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}, 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} } @misc{RehfeldtHobbieSchoenheitetal., author = {Rehfeldt, Daniel and Hobbie, Hannes and Sch{\"o}nheit, David and Gleixner, Ambros and Koch, Thorsten and M{\"o}st, Dominik}, title = {A massively parallel interior-point solver for linear energy system models with block structure}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74321}, abstract = {Linear energy system models are often a crucial component of system design and operations, as well as energy policy consulting. Such models can lead to large-scale linear programs, which can be intractable even for state-of-the-art commercial solvers|already the available memory on a desktop machine might not be sufficient. Against this backdrop, this article introduces an interior-point solver that exploits common structures of linear energy system models to efficiently run in parallel on distributed memory systems. The solver is designed for linear programs with doubly bordered block-diagonal constraint matrix and makes use of a Schur complement based decomposition. Special effort has been put into handling large numbers of linking constraints and variables as commonly observed in energy system models. In order to handle this strong linkage, a distributed preconditioning of the Schur complement is used. In addition, the solver features a number of more generic techniques such as parallel matrix scaling and structure-preserving presolving. The implementation is based on the existing parallel interior-point solver PIPS-IPM. We evaluate the computational performance on energy system models with up to 700 million non-zero entries in the constraint matrix, and with more than 200 million columns and 250 million rows. This article mainly concentrates on the energy system model ELMOD, which is a linear optimization model representing the European electricity markets by the use of a nodal pricing market clearing. It has been widely applied in the literature on energy system analyses during the recent years. However, it will be demonstrated that the new solver is also applicable to other energy system models.}, language = {en} } @inproceedings{GleixnerKempkeKochetal., author = {Gleixner, Ambros and Kempke, Nils-Christian and Koch, Thorsten and Rehfeldt, Daniel and Uslu, Svenja}, title = {First Experiments with Structure-Aware Presolving for a Parallel Interior-Point Method}, series = {Operations Research Proceedings 2019}, booktitle = {Operations Research Proceedings 2019}, edition = {1}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-030-48439-2_13}, pages = {105 -- 111}, abstract = {In linear optimization, matrix structure can often be exploited algorithmically. However, beneficial presolving reductions sometimes destroy the special structure of a given problem. In this article, we discuss structure-aware implementations of presolving as part of a parallel interior-point method to solve linear programs with block-diagonal structure, including both linking variables and linking constraints. While presolving reductions are often mathematically simple, their implementation in a high-performance computing environment is a complex endeavor. We report results on impact, performance, and scalability of the resulting presolving routines on real-world energy system models with up to 700 million nonzero entries in the constraint matrix.}, language = {en} } @misc{GleixnerKempkeKochetal., author = {Gleixner, Ambros and Kempke, Nils-Christian and Koch, Thorsten and Rehfeldt, Daniel and Uslu, Svenja}, title = {First Experiments with Structure-Aware Presolving for a Parallel Interior-Point Method}, issn = {1438-0064}, doi = {10.1007/978-3-030-48439-2_13}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-74084}, abstract = {In linear optimization, matrix structure can often be exploited algorithmically. However, beneficial presolving reductions sometimes destroy the special structure of a given problem. In this article, we discuss structure-aware implementations of presolving as part of a parallel interior-point method to solve linear programs with block-diagonal structure, including both linking variables and linking constraints. While presolving reductions are often mathematically simple, their implementation in a high-performance computing environment is a complex endeavor. We report results on impact, performance, and scalability of the resulting presolving routines on real-world energy system models with up to 700 million nonzero entries in the constraint matrix.}, language = {en} } @article{BreuerBussieckFiandetal., author = {Breuer, Thomas and Bussieck, Michael and Fiand, Frederik and Cao, Karl-Ki{\^e}n and Gils, Hans Christian and Wetzel, Manuel and Gleixner, Ambros and Koch, Thorsten and Rehfeldt, Daniel and Khabi, Dmitry}, title = {BEAM-ME: Ein interdisziplin{\"a}rer Beitrag zur Erreichung der Klimaziele}, series = {OR-News : das Magazin der GOR}, journal = {OR-News : das Magazin der GOR}, number = {66}, pages = {6 -- 8}, language = {de} } @article{SerranoSchwarzGleixner, author = {Serrano, Felipe and Schwarz, Robert and Gleixner, Ambros}, title = {On the relation between the extended supporting hyperplane algorithm and Kelley's cutting plane algorithm}, series = {Journal of Global Optimization}, volume = {78}, journal = {Journal of Global Optimization}, doi = {10.1007/s10898-020-00906-y}, pages = {161 -- 179}, abstract = {Recently, Kronqvist et al. (J Global Optim 64(2):249-272, 2016) rediscovered the supporting hyperplane algorithm of Veinott (Oper Res 15(1):147-152, 1967) and demonstrated its computational benefits for solving convex mixed integer nonlinear programs. In this paper we derive the algorithm from a geometric point of view. This enables us to show that the supporting hyperplane algorithm is equivalent to Kelley's cutting plane algorithm (J Soc Ind Appl Math 8(4):703-712, 1960) applied to a particular reformulation of the problem. As a result, we extend the applicability of the supporting hyperplane algorithm to convex problems represented by a class of general, not necessarily convex nor differentiable, functions.}, language = {en} } @article{GleixnerHendelGamrathetal., 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}, series = {Mathematical Programming Computation}, volume = {13}, journal = {Mathematical Programming Computation}, number = {3}, doi = {10.1007/s12532-020-00194-3}, pages = {443 -- 490}, 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} } @article{GamrathGleixnerKochetal., 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}, series = {Journal of Computational Mathematics}, volume = {37}, journal = {Journal of Computational Mathematics}, doi = {10.4208/jcm.1905-m2019-0055}, pages = {866 -- 888}, abstract = {The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of robust and future-proof decision support systems. The complexity of industrial-scale supply chain optimization, however, often poses limits to the application of general mixed-integer programming solvers. In this paper we describe algorithmic innovations that help to ensure that MIP solver performance matches the complexity of the large supply chain problems and tight time limits encountered in practice. Our computational evaluation is based on a diverse set, modeling real-world scenarios supplied by our industry partner SAP.}, language = {en} } @misc{GleixnerSteffy, 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}, 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} } @article{GleixnerSteffy, author = {Gleixner, Ambros and Steffy, Daniel}, title = {Linear Programming using Limited-Precision Oracles}, series = {Mathematical Programming}, volume = {183}, journal = {Mathematical Programming}, number = {1-2}, doi = {10.1007/s10107-019-01444-6}, pages = {525 -- 554}, 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} } @inproceedings{DevriendtGleixnerNordstroem, 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}, series = {Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2020}, volume = {12296}, booktitle = {Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2020}, publisher = {Springer}, pages = {xxiv -- xxvi}, 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{MuellerMuñozGasseetal., 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}, series = {Integer Programming and Combinatorial Optimization: 21th International Conference, IPCO 2020}, booktitle = {Integer Programming and Combinatorial Optimization: 21th International Conference, IPCO 2020}, doi = {10.1007/978-3-030-45771-6_25}, pages = {322 -- 337}, 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} } @misc{SerranoSchwarzGleixner, author = {Serrano, Felipe and Schwarz, Robert and Gleixner, Ambros}, title = {On the Relation between the Extended Supporting Hyperplane Algorithm and Kelley's Cutting Plane Algorithm}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-73253}, abstract = {Recently, Kronqvist et al. (2016) rediscovered the supporting hyperplane algorithm of Veinott (1967) and demonstrated its computational benefits for solving convex mixed-integer nonlinear programs. In this paper we derive the algorithm from a geometric point of view. This enables us to show that the supporting hyperplane algorithm is equivalent to Kelley's cutting plane algorithm applied to a particular reformulation of the problem. As a result, we extend the applicability of the supporting hyperplane algorithm to convex problems represented by general, not necessarily convex, differentiable functions that satisfy a mild condition.}, language = {en} } @inproceedings{GleixnerSteffy, author = {Gleixner, Ambros and Steffy, Daniel}, title = {Linear Programming using Limited-Precision Oracles}, series = {A. Lodi, V. Nagarajan (eds), Integer Programming and Combinatorial Optimization: 20th International Conference, IPCO 2019}, 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}, 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} } @article{MuellerSerranoGleixner, author = {M{\"u}ller, Benjamin and Serrano, Felipe and Gleixner, Ambros}, title = {Using two-dimensional Projections for Stronger Separation and Propagation of Bilinear Terms}, series = {SIAM Journal on Optimization}, volume = {30}, journal = {SIAM Journal on Optimization}, number = {2}, doi = {10.1137/19M1249825}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-72767}, pages = {1339 -- 1365}, abstract = {One of the most fundamental ingredients in mixed-integer nonlinear programming solvers is the well- known McCormick relaxation for a product of two variables x and y over a box-constrained domain. The starting point of this paper is the fact that the convex hull of the graph of xy can be much tighter when computed over a strict, non-rectangular subset of the box. In order to exploit this in practice, we propose to compute valid linear inequalities for the projection of the feasible region onto the x-y-space by solving a sequence of linear programs akin to optimization-based bound tightening. These valid inequalities allow us to employ results from the literature to strengthen the classical McCormick relaxation. As a consequence, we obtain a stronger convexification procedure that exploits problem structure and can benefit from supplementary information obtained during the branch-and bound algorithm such as an objective cutoff. We complement this by a new bound tightening procedure that efficiently computes the best possible bounds for x, y, and xy over the available projections. Our computational evaluation using the academic solver SCIP exhibit that the proposed methods are applicable to a large portion of the public test library MINLPLib and help to improve performance significantly.}, language = {en} }