TY - THES A1 - Gleixner, Ambros T1 - Solving Large-scale Open Pit Mining Production Scheduling Problems by Integer Programming N2 - 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ö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. Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11389 ER - TY - GEN A1 - Bley, Andreas A1 - Gleixner, Ambros A1 - Koch, Thorsten A1 - Vigerske, Stefan T1 - Comparing MIQCP solvers to a specialised algorithm for mine production scheduling N2 - 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. T3 - ZIB-Report - 09-32 Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11507 SN - 1438-0064 ER - TY - GEN A1 - Koch, Thorsten A1 - Achterberg, Tobias A1 - Andersen, Erling A1 - Bastert, Oliver A1 - Berthold, Timo A1 - Bixby, Robert E. A1 - Danna, Emilie A1 - Gamrath, Gerald A1 - Gleixner, Ambros A1 - Heinz, Stefan A1 - Lodi, Andrea A1 - Mittelmann, Hans A1 - Ralphs, Ted A1 - Salvagnin, Domenico A1 - Steffy, Daniel A1 - Wolter, Kati T1 - MIPLIB 2010 N2 - 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. T3 - ZIB-Report - 10-31 KW - Mixed Integer Programming KW - Problem Instances KW - IP KW - MIP KW - MIPLIB Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-12953 ER - TY - GEN A1 - Berthold, Timo A1 - Gleixner, Ambros T1 - Undercover Branching N2 - 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. T3 - ZIB-Report - 13-14 Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-18030 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Gleixner, Ambros T1 - Undercover: a primal MINLP heuristic exploring a largest sub-MIP N2 - We present Undercover, a primal heuristic for nonconvex mixed-integer nonlinear programming (MINLP) that explores a mixed-integer linear subproblem (sub-MIP) of a given MINLP. We solve a vertex covering problem to identify a minimal set of variables that need to be fixed in order to linearize each constraint, a so-called cover. Subsequently, these variables are fixed to values obtained from a reference point, e.g., an optimal solution of a linear relaxation. We apply domain propagation and conflict analysis to try to avoid infeasibilities and learn from them, respectively. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem. We present computational results on a test set of mixed-integer quadratically constrained programs (MIQCPs) and general MINLPs from MINLPLib. It turns out that the majority of these instances allow for small covers. Although general in nature, the heuristic appears most promising for MIQCPs, and complements nicely with existing root node heuristics in different state-of-the-art solvers. T3 - ZIB-Report - 12-07 KW - Primal Heuristic KW - Mixed-Integer Nonlinear Programming KW - Large Neighborhood Search KW - Mixed-Integer Quadratically Constrained Programming KW - Nonconvex Optimization Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14631 SN - 1438-0064 ER - TY - GEN A1 - Gleixner, Ambros T1 - Factorization and update of a reduced basis matrix for the revised simplex method N2 - 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. T3 - ZIB-Report - 12-36 Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-16349 SN - 1438-0064 ER - TY - GEN A1 - Gleixner, Ambros A1 - Weltge, Stefan T1 - Learning and Propagating Lagrangian Variable Bounds for Mixed-Integer Nonlinear Programming N2 - 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. T3 - ZIB-Report - 13-04 KW - MINLP KW - optimization-based bound tightening KW - optimality-based bound tightening KW - OBBT KW - propagation Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17631 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Gleixner, Ambros A1 - Heinz, Stefan A1 - Vigerske, Stefan T1 - Analyzing the computational impact of MIQCP solver components N2 - We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on a linear relaxation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances. T3 - ZIB-Report - 13-08 KW - mixed-integer quadratically constrained programming KW - mixed-integer programming KW - branch-and-cut KW - nonconvex KW - global optimization Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17754 SN - 1438-0064 ER - TY - JOUR A1 - Boland, Natashia A1 - Dumitrescu, Irina A1 - Froyland, Gary A1 - Gleixner, Ambros T1 - LP-based disaggregation approaches to solving the open pit mining production scheduling problem with block processing selectivity JF - Computers & Operations Research Y1 - 2009 VL - 36 SP - 1064 EP - 1089 ER - TY - THES A1 - Gleixner, Ambros T1 - Solving Large-scale Open Pit Mining Production Scheduling Problems by Integer Programming Y1 - 2008 UR - http://opus.kobv.de/zib/volltexte/2009/1187/ ER - TY - JOUR A1 - Berthold, Timo A1 - Gleixner, Ambros T1 - Undercover: a primal MINLP heuristic exploring a largest sub-MIP JF - Mathematical Programming N2 - We present Undercover, a primal heuristic for nonconvex mixed-integer nonlinear programming (MINLP) that explores a mixed-integer linear subproblem (sub-MIP) of a given MINLP. We solve a vertex covering problem to identify a minimal set of variables that need to be fixed in order to linearize each constraint, a so-called cover. Subsequently, these variables are fixed to values obtained from a reference point, e.g., an optimal solution of a linear relaxation. We apply domain propagation and conflict analysis to try to avoid infeasibilities and learn from them, respectively. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem. We present computational results on a test set of mixed-integer quadratically constrained programs (MIQCPs) and general MINLPs from MINLPLib. It turns out that the majority of these instances allow for small covers. Although general in nature, the heuristic appears most promising for MIQCPs, and complements nicely with existing root node heuristics in different state-of-the-art solvers. Y1 - 2014 U6 - https://doi.org/10.1007/s10107-013-0635-2 VL - 144 IS - 1-2 SP - 315 EP - 346 ER - TY - CHAP A1 - Gamrath, Gerald A1 - Melchiori, Anna A1 - Berthold, Timo A1 - Gleixner, Ambros A1 - Salvagnin, Domenico T1 - Branching on Multi-aggregated Variables T2 - Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2015 N2 - In mixed-integer programming, the branching rule is a key component to a fast convergence of the branch-and-bound algorithm. The most common strategy is to branch on simple disjunctions that split the domain of a single integer variable into two disjoint intervals. Multi-aggregation is a presolving step that replaces variables by an affine linear sum of other variables, thereby reducing the problem size. While this simplification typically improves the performance of MIP solvers, it also restricts the degree of freedom in variable-based branching rules. We present a novel branching scheme that tries to overcome the above drawback by considering general disjunctions defined by multi-aggregated variables in addition to the standard disjunctions based on single variables. This natural idea results in a hybrid between variable- and constraint-based branching rules. Our implementation within the constraint integer programming framework SCIP incorporates this into a full strong branching rule and reduces the number of branch-and-bound nodes on a general test set of publicly available benchmark instances. For a specific class of problems, we show that the solving time decreases significantly. Y1 - 2015 U6 - https://doi.org/10.1007/978-3-319-18008-3_10 VL - 9075 SP - 141 EP - 156 ER - TY - CHAP A1 - Cao, Karl-Kiên A1 - Gleixner, Ambros A1 - Miltenberger, Matthias T1 - Methoden zur Reduktion der Rechenzeit linearer Optimierungsmodelle in der Energiewirtschaft - Eine Performance-Analyse T2 - EnInnov 2016: 14. Symposium Energieinnovation 2016 N2 - Dieser Beitrag stellt mögliche Ansätze zur Reduktion der Rechenzeit von linearen Optimierungsproblemen mit energiewirtschaftlichem Anwendungshintergrund vor. Diese Ansätze bilden im Allgemeinen die Grundlage für konzeptionelle Strategien zur Beschleunigung von Energiesystemmodellen. Zu den einfachsten Beschleunigungsstrategien zählt die Verkleinerung der Modelldimensionen, was beispielsweise durch Ändern der zeitlichen, räumlichen oder technologischen Auflösung eines Energiesystemmodells erreicht werden kann. Diese Strategien sind zwar häufig ein Teil der Methodik in der Energiesystemanalyse, systematische Benchmarks zur Bewertung ihrer Effektivität werden jedoch meist nicht durchgeführt. Die vorliegende Arbeit adressiert genau diesen Sachverhalt. Hierzu werden Modellinstanzen des Modells REMix in verschiedenen Größenordnungen mittels einer Performance-Benchmark-Analyse untersucht. Die Ergebnisse legen zum einen den Schluss nahe, dass verkürzte Betrachtungszeiträume das größte Potential unter den hier analysierten Strategien zur Reduktion von Rechenzeit bieten. Zum anderen empfiehlt sich die Verwendung des Barrier-Lösungsverfahrens mit multiplen Threads unter Vernachlässigung des Cross-Over. Y1 - 2016 ER - TY - GEN A1 - Cheung, Kevin K. H. A1 - Gleixner, Ambros A1 - Steffy, Daniel T1 - Verifying Integer Programming Results N2 - 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. T3 - ZIB-Report - 16-58 KW - correctness, verification, proof, certificate, optimality, infeasibility, mixed-integer linear programming Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61044 SN - 1438-0064 ER - TY - GEN A1 - Gamrath, Gerald A1 - Gleixner, Ambros A1 - Koch, Thorsten A1 - Miltenberger, Matthias A1 - Kniasew, Dimitri A1 - Schlögel, Dominik A1 - Martin, Alexander A1 - Weninger, Dieter T1 - Tackling Industrial-Scale Supply Chain Problems by Mixed-Integer Programming N2 - SAP's decision support systems for optimized supply network planning rely on mixed-integer programming as the core engine to compute optimal or near-optimal solutions. The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of a robust and future-proof decision support system for a large and diverse customer base. In this paper we describe our coordinated efforts to ensure that the performance of the underlying solution algorithms matches the complexity of the large supply chain problems and tight time limits encountered in practice. T3 - ZIB-Report - 16-45 KW - supply chain management, supply network optimization, mixed-integer linear programming, primal heuristics, numerical stability, large-scale optimization Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61107 SN - 1438-0064 ER - TY - JOUR A1 - Gleixner, Ambros A1 - Berthold, Timo A1 - Müller, Benjamin A1 - Weltge, Stefan T1 - Three Enhancements for Optimization-Based Bound Tightening JF - Journal of Global Optimization N2 - Optimization-based bound tightening (OBBT) is one of the most effective procedures to reduce variable domains of nonconvex mixed-integer nonlinear programs (MINLPs). At the same time it is one of the most expensive bound tightening procedures, since it solves auxiliary linear programs (LPs)—up to twice the number of variables many. The main goal of this paper is to discuss algorithmic techniques for an efficient implementation of OBBT. Most state-of-the-art MINLP solvers apply some restricted version of OBBT and it seems to be common belief that OBBT is beneficial if only one is able to keep its computational cost under control. To this end, we introduce three techniques to increase the efficiency of OBBT: filtering strategies to reduce the number of solved LPs, ordering heuristics to exploit simplex warm starts, and the generation of Lagrangian variable bounds (LVBs). The propagation of LVBs during tree search is a fast approximation to OBBT without the need to solve auxiliary LPs. We conduct extensive computational experiments on MINLPLib2. Our results indicate that OBBT is most beneficial on hard instances, for which we observe a speedup of 17% to 19% on average. Most importantly, more instances can be solved when using OBBT. Y1 - 2017 U6 - https://doi.org/10.1007/s10898-016-0450-4 VL - 67 IS - 4 SP - 731 EP - 757 ER - TY - JOUR A1 - Vigerske, Stefan A1 - Gleixner, Ambros T1 - SCIP: Global Optimization of Mixed-Integer Nonlinear Programs in a Branch-and-Cut Framework JF - Optimization Methods & Software N2 - This paper describes the extensions that were added to the constraint integer programming framework SCIP in order to enable it to solve convex and nonconvex mixed-integer nonlinear programs (MINLPs) to global optimality. SCIP implements a spatial branch-and-bound algorithm based on a linear outer-approximation, which is computed by convex over- and underestimation of nonconvex functions. An expression graph representation of nonlinear constraints allows for bound tightening, structure analysis, and reformulation. Primal heuristics are employed throughout the solving process to find feasible solutions early. We provide insights into the performance impact of individual MINLP solver components via a detailed computational study over a large and heterogeneous test set. Y1 - 2018 U6 - https://doi.org/10.1080/10556788.2017.1335312 VL - 33 IS - 3 SP - 563 EP - 593 ER - TY - JOUR A1 - Berthold, Timo A1 - Gleixner, Ambros A1 - Heinz, Stefan A1 - Vigerske, Stefan T1 - Analyzing the computational impact of MIQCP solver components JF - Numerical Algebra, Control and Optimization N2 - We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on a linear relaxation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances. Y1 - 2012 U6 - https://doi.org/10.3934/naco.2012.2.739 VL - 2 IS - 4 SP - 739 EP - 748 ER - TY - CHAP A1 - Gleixner, Ambros A1 - Weltge, Stefan T1 - Learning and Propagating Lagrangian Variable Bounds for Mixed-Integer Nonlinear Programming T2 - 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 N2 - 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. Y1 - 2013 U6 - https://doi.org/10.1007/978-3-642-38171-3_26 VL - 7874 SP - 355 EP - 361 ER - TY - CHAP A1 - Berthold, Timo A1 - Gleixner, Ambros ED - Bonifaci, Vincenzo ED - Demetrescu, Camil ED - Marchetti-Spaccamela, Alberto T1 - Undercover Branching T2 - Experimental Algorithms, 12th International Symposium, SEA 2013, Rome, Italy, June 5-7, 2013, Proceedings N2 - 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. Y1 - 2013 U6 - https://doi.org/10.1007/978-3-642-38527-8_20 VL - 7933 SP - 212 EP - 223 ER - TY - CHAP A1 - Berthold, Timo A1 - Gleixner, Ambros A1 - Heinz, Stefan A1 - Koch, Thorsten A1 - Shinano, Yuji T1 - SCIP Optimization Suite を利用した 混合整数(線形/非線形) 計画問題の解法 T2 - Proceedings of the 24th RAMP symposium. The Operations Society of Japan, RAMP: Research Association of Mathematical Programming N2 - この論文ではソフトウェア・パッケージ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 の利用方法を示すとともに,利用可能なインタフェースの概要を示す.最後に,将来の開 発計画の概要について述べる. N2 - 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 in concert these can be used 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 over available interfaces, and outline plans for future development. Y1 - 2012 SP - 165 EP - 192 ER - TY - CHAP A1 - Bley, Andreas A1 - Gleixner, Ambros A1 - Koch, Thorsten A1 - Vigerske, Stefan T1 - Comparing MIQCP Solvers to a Specialised Algorithm for Mine Production Scheduling T2 - Modeling, Simulation and Optimization of Complex Processes. Proceedings of the Fourth International Conference on High Performance Scientific Computing, March 2-6, 2009, Hanoi, Vietnam N2 - 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. Y1 - 2012 U6 - https://doi.org/10.1007/978-3-642-25707-0_3 SP - 25 EP - 39 ER - TY - CHAP A1 - Gleixner, Ambros A1 - Steffy, Daniel A1 - Wolter, Kati T1 - Improving the Accuracy of Linear Programming Solvers with Iterative Refinement T2 - ISSAC '12. Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation Y1 - 2012 U6 - https://doi.org/10.1145/2442829.2442858 SP - 187 EP - 194 ER - TY - CHAP A1 - Berthold, Timo A1 - Gleixner, Ambros ED - Bonami, Pierre ED - Liberti, Leo ED - Miller, Andrew J. ED - Sartenaer, Annick T1 - Undercover – a primal heuristic for MINLP based on sub-MIPs generated by set covering T2 - Proceedings of the European Workshop on Mixed Integer Nonlinear Programming, April 12-16, 2010, Marseilles, France N2 - 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. Y1 - 2010 SP - 103 EP - 112 ER - TY - JOUR A1 - Gleixner, Ambros A1 - Held, Harald A1 - Huang, Wei A1 - Vigerske, Stefan T1 - Towards globally optimal operation of water supply networks JF - Numerical Algebra, Control and Optimization N2 - 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. Y1 - 2012 U6 - https://doi.org/10.3934/naco.2012.2.695 VL - 2 IS - 4 SP - 695 EP - 711 ER - TY - JOUR A1 - Koch, Thorsten A1 - Achterberg, Tobias A1 - Andersen, Erling A1 - Bastert, Oliver A1 - Berthold, Timo A1 - Bixby, Robert E. A1 - Danna, Emilie A1 - Gamrath, Gerald A1 - Gleixner, Ambros A1 - Heinz, Stefan A1 - Lodi, Andrea A1 - Mittelmann, Hans A1 - Ralphs, Ted A1 - Salvagnin, Domenico A1 - Steffy, Daniel A1 - Wolter, Kati T1 - MIPLIB 2010 JF - Mathematical Programming Computation Y1 - 2011 UR - http://mpc.zib.de/index.php/MPC/article/view/56 U6 - https://doi.org/10.1007/s12532-011-0025-9 VL - 3 IS - 2 SP - 103 EP - 163 ER - TY - GEN A1 - Berthold, Timo A1 - Gleixner, Ambros A1 - Heinz, Stefan A1 - Koch, Thorsten A1 - Shinano, Yuji T1 - SCIP Optimization Suite を利用した 混合整数(線形/非線形) 計画問題の解法 T1 - Solving mixed integer linear and nonlinear problems using the SCIP Optimization Suite N2 - この論文ではソフトウェア・パッケージ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 の利用方法を示すとともに,利用可能なインタフェースの概要を示す.最後に,将来の開 発計画の概要について述べる. N2 - 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 in concert these can be used 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 over available interfaces, and outline plans for future development. T3 - ZIB-Report - 12-24 KW - SCIP, MIP, MINLP, CIP, LP, modeling, optimization Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15598 SN - 1438-0064 ER - TY - GEN A1 - Gleixner, Ambros A1 - Held, Harald A1 - Huang, Wei A1 - Vigerske, Stefan T1 - Towards globally optimal operation of water supply networks N2 - 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. T3 - ZIB-Report - 12-25 KW - MINLP, global optimization, operative planning, water supply networks Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15603 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Gamrath, Gerald A1 - Gleixner, Ambros A1 - Heinz, Stefan A1 - Koch, Thorsten A1 - Shinano, Yuji T1 - Solving mixed integer linear and nonlinear problems using the SCIP Optimization Suite N2 - 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. T3 - ZIB-Report - 12-27 KW - LP, MIP, CIP, MINLP, modeling, optimization, SCIP, SoPlex, Zimpl Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15654 SN - 1438-0064 ER - TY - GEN A1 - Vigerske, Stefan A1 - Gleixner, Ambros T1 - SCIP: Global Optimization of Mixed-Integer Nonlinear Programs in a Branch-and-Cut Framework N2 - This paper describes the extensions that were added to the constraint integer programming framework SCIP in order to enable it to solve convex and nonconvex mixed-integer nonlinear programs (MINLPs) to global optimality. SCIP implements a spatial branch-and-bound algorithm based on a linear outer-approximation, which is computed by convex over- and underestimation of nonconvex functions. An expression graph representation of nonlinear constraints allows for bound tightening, structure analysis, and reformulation. Primal heuristics are employed throughout the solving process to find feasible solutions early. We provide insights into the performance impact of individual MINLP solver components via a detailed computational study over a large and heterogeneous test set. T3 - ZIB-Report - 16-24 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59377 SN - 1438-0064 ER - TY - CHAP A1 - D'Andreagiovanni, Fabio A1 - Gleixner, Ambros T1 - Towards an accurate solution of wireless network design problems T2 - Cerulli R., Fujishige S., Mahjoub A. (eds) Combinatorial Optimization. ISCO 2016 N2 - 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. Y1 - 2016 U6 - https://doi.org/10.1007/978-3-319-45587-7_12 SP - 135 EP - 147 ER - TY - THES A1 - Gleixner, Ambros T1 - Exact and Fast Algorithms for Mixed-Integer Nonlinear Programming N2 - 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. Y1 - 2015 UR - http://dx.doi.org/10.14279/depositonce-4938 SN - 978-3-8325-4190-3 PB - Logos Verlag Berlin ER - TY - JOUR A1 - Gleixner, Ambros A1 - Steffy, Daniel A1 - Wolter, Kati T1 - Iterative Refinement for Linear Programming JF - INFORMS Journal on Computing N2 - We describe an iterative refinement procedure for computing extended precision or exact solutions to linear programming problems (LPs). Arbitrarily precise solutions can be computed by solving a sequence of closely related LPs with limited precision arithmetic. The LPs solved share the same constraint matrix as the original problem instance and are transformed only by modification of the objective function, right-hand side, and variable bounds. Exact computation is used to compute and store the exact representation of the transformed problems, while numeric computation is used for solving LPs. At all steps of the algorithm the LP bases encountered in the transformed problems correspond directly to LP bases in the original problem description. We show that this algorithm is effective in practice for computing extended precision solutions and that it leads to a direct improvement of the best known methods for solving LPs exactly over the rational numbers. Our implementation is publically available as an extension of the academic LP solver SoPlex. Y1 - 2016 U6 - https://doi.org/10.1287/ijoc.2016.0692 VL - 28 IS - 3 SP - 449 EP - 464 ER - TY - GEN A1 - Gamrath, Gerald A1 - Melchiori, Anna A1 - Berthold, Timo A1 - Gleixner, Ambros A1 - Salvagnin, Domenico T1 - Branching on multi-aggregated variables N2 - In mixed-integer programming, the branching rule is a key component to a fast convergence of the branch-and-bound algorithm. The most common strategy is to branch on simple disjunctions that split the domain of a single integer variable into two disjoint intervals. Multi-aggregation is a presolving step that replaces variables by an affine linear sum of other variables, thereby reducing the problem size. While this simplification typically improves the performance of MIP solvers, it also restricts the degree of freedom in variable-based branching rules. We present a novel branching scheme that tries to overcome the above drawback by considering general disjunctions defined by multi-aggregated variables in addition to the standard disjunctions based on single variables. This natural idea results in a hybrid between variable- and constraint-based branching rules. Our implementation within the constraint integer programming framework SCIP incorporates this into a full strong branching rule and reduces the number of branch-and-bound nodes on a general test set of publicly available benchmark instances. For a specific class of problems, we show that the solving time decreases significantly. T3 - ZIB-Report - 15-10 KW - mixed-integer programming, branch-and-bound, branching rule, strong branching Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-53829 SN - 1438-0064 ER - TY - GEN A1 - Gleixner, Ambros A1 - Steffy, Daniel A1 - Wolter, Kati T1 - Iterative Refinement for Linear Programming N2 - We describe an iterative refinement procedure for computing extended precision or exact solutions to linear programming problems (LPs). Arbitrarily precise solutions can be computed by solving a sequence of closely related LPs with limited precision arithmetic. The LPs solved share the same constraint matrix as the original problem instance and are transformed only by modification of the objective function, right-hand side, and variable bounds. Exact computation is used to compute and store the exact representation of the transformed problems, while numeric computation is used for solving LPs. At all steps of the algorithm the LP bases encountered in the transformed problems correspond directly to LP bases in the original problem description. We show that this algorithm is effective in practice for computing extended precision solutions and that it leads to a direct improvement of the best known methods for solving LPs exactly over the rational numbers. Our implementation is publically available as an extension of the academic LP solver SoPlex. T3 - ZIB-Report - 15-15 Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-55118 SN - 1438-0064 ER - TY - GEN A1 - Georges, Alexander A1 - Gleixner, Ambros A1 - Gojic, Gorana A1 - Gottwald, Robert Lion A1 - Haley, David A1 - Hendel, Gregor A1 - Matejczyk, Bartlomiej T1 - Feature-Based Algorithm Selection for Mixed Integer Programming N2 - 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. T3 - ZIB-Report - 18-17 KW - algorithm selection KW - mixed integer programming Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-68362 SN - 1438-0064 ER - TY - GEN A1 - Rehfeldt, Daniel A1 - Hobbie, Hannes A1 - Schönheit, David A1 - Gleixner, Ambros A1 - Koch, Thorsten A1 - Möst, Dominik T1 - A massively parallel interior-point solver for linear energy system models with block structure N2 - 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. T3 - ZIB-Report - 19-41 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-74321 SN - 1438-0064 N1 - In the meantime, this report got published as a journal article: https://opus4.kobv.de/opus4-zib/frontdoor/index/index/searchtype/authorsearch/author/Hannes+Hobbie/docId/8191/start/1/rows/10 Please use this journal reference when citing this work. ER - TY - CHAP A1 - Gleixner, Ambros A1 - Kempke, Nils-Christian A1 - Koch, Thorsten A1 - Rehfeldt, Daniel A1 - Uslu, Svenja T1 - First Experiments with Structure-Aware Presolving for a Parallel Interior-Point Method T2 - Operations Research Proceedings 2019 N2 - 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. KW - block structure KW - energy system models KW - interior-point method KW - high performance computing KW - linear programming KW - parallelization KW - presolving KW - preprocessing Y1 - 2020 U6 - https://doi.org/10.1007/978-3-030-48439-2_13 SP - 105 EP - 111 PB - Springer International Publishing ET - 1 ER - TY - GEN A1 - Gleixner, Ambros A1 - Kempke, Nils-Christian A1 - Koch, Thorsten A1 - Rehfeldt, Daniel A1 - Uslu, Svenja T1 - First Experiments with Structure-Aware Presolving for a Parallel Interior-Point Method N2 - 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. T3 - ZIB-Report - 19-39 KW - block structure KW - energy system models KW - interior-point method KW - high performance computing KW - linear programming KW - parallelization KW - presolving KW - preprocessing Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-74084 SN - 1438-0064 ER - TY - JOUR A1 - Breuer, Thomas A1 - Bussieck, Michael A1 - Fiand, Frederik A1 - Cao, Karl-Kiên A1 - Gils, Hans Christian A1 - Wetzel, Manuel A1 - Gleixner, Ambros A1 - Koch, Thorsten A1 - Rehfeldt, Daniel A1 - Khabi, Dmitry T1 - BEAM-ME: Ein interdisziplinärer Beitrag zur Erreichung der Klimaziele JF - OR-News : das Magazin der GOR Y1 - 2019 IS - 66 SP - 6 EP - 8 ER - TY - JOUR A1 - Serrano, Felipe A1 - Schwarz, Robert A1 - Gleixner, Ambros T1 - On the relation between the extended supporting hyperplane algorithm and Kelley’s cutting plane algorithm JF - Journal of Global Optimization N2 - 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. Y1 - 2020 U6 - https://doi.org/10.1007/s10898-020-00906-y VL - 78 SP - 161 EP - 179 ER - TY - JOUR A1 - Gleixner, Ambros A1 - Hendel, Gregor A1 - Gamrath, Gerald A1 - Achterberg, Tobias A1 - Bastubbe, Michael A1 - Berthold, Timo A1 - Christophel, Philipp M. A1 - Jarck, Kati A1 - Koch, Thorsten A1 - Linderoth, Jeff A1 - Lübbecke, Marco A1 - Mittelmann, Hans A1 - Ozyurt, Derya A1 - Ralphs, Ted A1 - Salvagnin, Domenico A1 - Shinano, Yuji T1 - MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library JF - Mathematical Programming Computation N2 - 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. Y1 - 2021 U6 - https://doi.org/10.1007/s12532-020-00194-3 VL - 13 IS - 3 SP - 443 EP - 490 ER - TY - JOUR A1 - Gamrath, Gerald A1 - Gleixner, Ambros A1 - Koch, Thorsten A1 - Miltenberger, Matthias A1 - Kniasew, Dimitri A1 - Schlögel, Dominik A1 - Martin, Alexander A1 - Weninger, Dieter T1 - Tackling Industrial-Scale Supply Chain Problems by Mixed-Integer Programming JF - Journal of Computational Mathematics N2 - 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. Y1 - 2019 U6 - https://doi.org/10.4208/jcm.1905-m2019-0055 VL - 37 SP - 866 EP - 888 ER - TY - GEN A1 - Gleixner, Ambros A1 - Steffy, Daniel T1 - Linear Programming using Limited-Precision Oracles N2 - 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. T3 - ZIB-Report - 19-57 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-75316 SN - 1438-0064 ER - TY - JOUR A1 - Gleixner, Ambros A1 - Steffy, Daniel T1 - Linear Programming using Limited-Precision Oracles JF - Mathematical Programming N2 - 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. Y1 - 2020 U6 - https://doi.org/10.1007/s10107-019-01444-6 VL - 183 IS - 1-2 SP - 525 EP - 554 ER - TY - CHAP A1 - Devriendt, Jo A1 - Gleixner, Ambros A1 - Nordström, Jakob T1 - Learn to Relax: Integrating 0-1 Integer Linear Programming with Pseudo-Boolean Conflict-Driven Search T2 - Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2020 N2 - 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. Y1 - 2020 VL - 12296 SP - xxiv EP - xxvi PB - Springer ER - TY - CHAP A1 - Müller, Benjamin A1 - Muñoz, Gonzalo A1 - Gasse, Maxime A1 - Gleixner, Ambros A1 - Lodi, Andrea A1 - Serrano, Felipe T1 - On Generalized Surrogate Duality in Mixed-Integer Nonlinear Programming T2 - Integer Programming and Combinatorial Optimization: 21th International Conference, IPCO 2020 N2 - 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. Y1 - 2020 U6 - https://doi.org/10.1007/978-3-030-45771-6_25 SP - 322 EP - 337 ER - TY - GEN A1 - Serrano, Felipe A1 - Schwarz, Robert A1 - Gleixner, Ambros T1 - On the Relation between the Extended Supporting Hyperplane Algorithm and Kelley’s Cutting Plane Algorithm N2 - 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. T3 - ZIB-Report - 19-18 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-73253 SN - 1438-0064 ER - TY - CHAP A1 - Gleixner, Ambros A1 - Steffy, Daniel T1 - Linear Programming using Limited-Precision Oracles T2 - A. Lodi, V. Nagarajan (eds), Integer Programming and Combinatorial Optimization: 20th International Conference, IPCO 2019 N2 - 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. Y1 - 2019 U6 - https://doi.org/10.1007/978-3-030-17953-3_30 SP - 399 EP - 412 ER - TY - JOUR A1 - Müller, Benjamin A1 - Serrano, Felipe A1 - Gleixner, Ambros T1 - Using two-dimensional Projections for Stronger Separation and Propagation of Bilinear Terms JF - SIAM Journal on Optimization N2 - 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. Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-72767 VL - 30 IS - 2 SP - 1339 EP - 1365 ER -