TY - THES A1 - Berthold, Timo T1 - Primal Heuristics for Mixed Integer Programs Y1 - 2006 UR - http://opus.kobv.de/zib/volltexte/2007/1054/ ER - TY - JOUR A1 - Achterberg, Tobias A1 - Berthold, Timo T1 - Improving the Feasibility Pump JF - Discrete Optimization Y1 - 2007 VL - Special Issue 4 IS - 1 SP - 77 EP - 86 ER - TY - CHAP A1 - Achterberg, Tobias A1 - Heinz, Stefan A1 - Koch, Thorsten ED - Perron, Laurent ED - Trick, Michael T1 - Counting Solutions of Integer Programs Using Unrestricted Subtree Detection T2 - Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 5th International Conference, CPAIOR 2008 Y1 - 2008 UR - http://opus.kobv.de/zib/volltexte/2008/1092/ VL - 5015 SP - 278 EP - 282 PB - Springer ER - TY - JOUR A1 - Berthold, Timo T1 - Heuristiken im Branch-and-Cut-Framework SCIP JF - OR News Y1 - 2008 IS - 32 SP - 24 EP - 25 ER - TY - CHAP A1 - Berthold, Timo ED - Kalcsics, Jörg ED - Nickel, Stefan T1 - Heuristics of the Branch-Cut-and-Price-Framework SCIP T2 - Operations Research Proceedings 2007 Y1 - 2008 SP - 31 EP - 36 PB - Springer-Verlag ER - TY - CHAP A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Pfetsch, Marc ED - Kullmann, Oliver T1 - Nonlinear pseudo-Boolean optimization T2 - Theory and Applications of Satisfiability Testing – SAT 2009 Y1 - 2009 VL - 5584 SP - 441 EP - 446 PB - Springer ER - TY - CHAP A1 - Achterberg, Tobias A1 - Berthold, Timo ED - van Hoeve, Willem ED - Hooker, John T1 - Hybrid Branching T2 - Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 6th International Conference, CPAIOR 2009 Y1 - 2009 VL - 5547 SP - 309 EP - 311 PB - Springer ER - TY - CHAP A1 - Berthold, Timo A1 - Pfetsch, Marc ED - Fleischmann, Bernhard ED - Borgwardt, Karl ED - Klein, Robert ED - Tuma, Axel T1 - Detecting Orbitopal Symmetries T2 - Operations Research Proceedings 2008 Y1 - 2009 SP - 433 EP - 438 PB - Springer-Verlag 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 - CHAP A1 - Berthold, Timo A1 - Feydy, Thibaut A1 - Stuckey, Peter ED - Lodi, Andrea ED - Milano, Michela ED - Toth, Paolo T1 - Rapid Learning for Binary Programs T2 - Proc. of CPAIOR 2010 Y1 - 2010 VL - 6140 SP - 51 EP - 55 PB - Springer ER - TY - CHAP A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Lübbecke, Marco A1 - Möhring, Rolf A1 - Schulz, Jens ED - Lodi, Andrea ED - Milano, Michela ED - Toth, Paolo T1 - A Constraint Integer Programming Approach for Resource-Constrained Project Scheduling T2 - Proc. of CPAIOR 2010 Y1 - 2010 VL - 6140 SP - 313 EP - 317 PB - Springer ER - TY - THES A1 - Gamrath, Gerald T1 - Generic Branch-Cut-and-Price N2 - In this thesis, we present the theoretical background, implementational details and computational results concerning the generic branch-cut-and-price solver GCG. KW - mixed-integer programming KW - column generation KW - branch-and-price Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57543 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 - CHAP A1 - Fügenschuh, Armin A1 - Hiller, Benjamin A1 - Humpola, Jesco A1 - Koch, Thorsten A1 - Lehmann, Thomas A1 - Schwarz, Robert A1 - Schweiger, Jonas A1 - Szabo, Jacint T1 - Gas Network Topology Optimization for Upcoming Market Requirements T2 - International Conference on the European Energy Market (EEM) N2 - Gas distribution networks are complex structures that consist of passive pipes, and active, controllable elements such as valves and compressors. Controlling such network means to find a suitable setting for all active components such that a nominated amount of gas can be transmitted from entries to exits through the network, without violating physical or operational constraints. The control of a large-scale gas network is a challenging task from a practical point of view. In most companies the actual controlling process is supported by means of computer software that is able to simulate the flow of the gas. However, the active settings have to be set manually within such simulation software. The solution quality thus depends on the experience of a human planner. When the gas network is insufficient for the transport then topology extensions come into play. Here a set of new pipes or active elements is determined such that the extended network admits a feasible control again. The question again is how to select these extensions and where to place them such that the total extension costs are minimal. Industrial practice is again to use the same simulation software, determine extensions by experience, add them to the virtual network, and then try to find a feasible control of the active elements. The validity of this approach now depends even more on the human planner. Another weakness of this manual simulation-based approach is that it cannot establish infeasibility of a certain gas nomination, unless all settings of the active elements are tried. Moreover, it is impossible to find a cost-optimal network extension in this way. In order to overcome these shortcomings of the manual planning approach we present a new approach, rigorously based on mathematical optimization. Hereto we describe a model for finding feasible controls and then extend this model such that topology extensions can additionally and simultaneously be covered. Numerical results for real-world instances are presented and discussed. Y1 - 2011 U6 - https://doi.org/10.1109/EEM.2011.5953035 SP - 346 EP - 351 ER - TY - CHAP A1 - Heinz, Stefan A1 - Schulz, Jens T1 - Explanations for the Cumulative Constraint: An Experimental Study T2 - Experimental Algorithms Y1 - 2011 VL - 6630 SP - 400 EP - 409 ER - TY - CHAP A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Schulz, Jens T1 - An approximative Criterion for the Potential of Energetic Reasoning T2 - Theory and Practice of Algorithms in (Computer) Systems Y1 - 2011 VL - 6595 SP - 229 EP - 239 ER - TY - CHAP A1 - Hendel, Gregor A1 - Berthold, Timo A1 - Achterberg, Tobias T1 - Rounding and Propagation Heuristics for Mixed Integer Programming T2 - Operations Research Proceedings 2011 N2 - Primal heuristics are an important component of state-of-the-art codes for mixed integer programming. In this paper, we focus on primal heuristics that only employ computationally inexpensive procedures such as rounding and logical deductions (propagation). We give an overview of eight different approaches. To assess the impact of these primal heuristics on the ability to find feasible solutions, in particular early during search, we introduce a new performance measure, the primal integral. Computational experiments evaluate this and other measures on MIPLIB~2010 benchmark instances. Y1 - 2011 SP - 71 EP - 76 ER - TY - GEN A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Hendel, Gregor T1 - Rounding and Propagation Heuristics for Mixed Integer Programming N2 - Primal heuristics are an important component of state-of-the-art codes for mixed integer programming. In this paper, we focus on primal heuristics that only employ computationally inexpensive procedures such as rounding and logical deductions (propagation). We give an overview of eight different approaches. To assess the impact of these primal heuristics on the ability to find feasible solutions, in particular early during search, we introduce a new performance measure, the primal integral. Computational experiments evaluate this and other measures on MIPLIB~2010 benchmark instances. T3 - ZIB-Report - 11-29 KW - primal heuristic KW - mixed integer programming KW - domain propagation Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-13255 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 - 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 - 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 - 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 - Heinz, Stefan A1 - Beck, J. Christopher T1 - Reconsidering Mixed Integer Programming and MIP-based Hybrids for Scheduling T2 - Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2012) Y1 - 2012 VL - 7298 SP - 211 EP - 227 ER - TY - JOUR A1 - Heinz, Stefan A1 - Schlechte, Thomas A1 - Stephan, Rüdiger A1 - Winkler, Michael T1 - Solving steel mill slab design problems JF - Constraints N2 - The steel mill slab design problem from the CSPLIB is a combinatorial optimization problem motivated by an application of the steel industry. It has been widely studied in the constraint programming community. Several methods were proposed to solve this problem. A steel mill slab library was created which contains 380 instances. A closely related binpacking problem called the multiple knapsack problem with color constraints, originated from the same industrial problem, was discussed in the integer programming community. In particular, a simple integer program for this problem has been given by Forrest et al. (INFORMS J Comput 18:129–134, 2006). The aim of this paper is to bring these different studies together. Moreover, we adapt the model of Forrest et al. (INFORMS J Comput 18:129–134, 2006) for the steel mill slab design problem. Using this model and a state-of-the-art integer program solver all instances of the steel mill slab library can be solved efficiently to optimality. We improved, thereby, the solution values of 76 instances compared to previous results (Schaus et al., Constraints 16:125–147, 2010). Finally, we consider a recently introduced variant of the steel mill slab design problem, where within all solutions which minimize the leftover one is interested in a solution which requires a minimum number of slabs. For that variant we introduce two approaches and solve all instances of the steel mill slab library with this slightly changed objective function to optimality. Y1 - 2012 U6 - https://doi.org/10.1007/s10601-011-9113-8 VL - 17 IS - 1 SP - 39 EP - 50 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 - 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 - GEN A1 - Gamrath, Gerald A1 - Koch, Thorsten A1 - Martin, Alexander A1 - Miltenberger, Matthias A1 - Weninger, Dieter T1 - Progress in Presolving for Mixed Integer Programming N2 - Presolving attempts to eliminate redundant information from the problem formulation and simultaneously tries to strengthen the formulation. It can be very effective and is often essential for solving instances. Especially for mixed integer programming problems, fast and effective presolving algorithms are very important. In this paper, we report on three new presolving techniques. The first method searches for singleton continuous columns and tries to fix the corresponding variables. Then we present a presolving technique which exploits a partial order of the variables to induce fixings. Finally, we show an approach based on connected components in graphs. Our computational results confirm the profitable use of the algorithms in practice. T3 - ZIB-Report - 13-48 KW - mixed-integer programming KW - presolving KW - preprocessing Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42530 SN - 1438-0064 ER - TY - JOUR A1 - Gamrath, Gerald ED - Gomes, Carla ED - Sellmann, Meinolf T1 - Improving strong branching by propagation JF - Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems N2 - Strong branching is an important component of most variable selection rules in branch-and-bound based mixed-integer linear programming solvers. It predicts the dual bounds of potential child nodes by solving auxiliary LPs and thereby helps to keep the branch-and-bound tree small. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Computational experiments on standard MIP instances indicate that this is beneficial in three aspects: It helps to reduce the average number of LP iterations per strong branching call, the number of branch-and-bound nodes, and the overall solving time. Y1 - 2013 U6 - https://doi.org/10.1007/978-3-642-38171-3_25 VL - 7874 SP - 347 EP - 354 PB - Springer Berlin Heidelberg ER - TY - GEN A1 - Berthold, Timo A1 - Salvagnin, Domenico ED - Gomes, Carla ED - Sellmann, Meinolf T1 - Cloud branching T2 - Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems N2 - Branch-and-bound methods for mixed-integer programming (MIP) are traditionally based on solving a linear programming (LP) relaxation and branching on a variable which takes a fractional value in the (single) computed relaxation optimum. In this paper we study branching strategies for mixed-integer programs that exploit the knowledge of multiple alternative optimal solutions (a cloud) of the current LP relaxation. These strategies naturally extend state-of-the-art methods like strong branching, pseudocost branching, and their hybrids. We show that by exploiting dual degeneracy, and thus multiple alternative optimal solutions, it is possible to enhance traditional methods. We present preliminary computational results, applying the newly proposed strategy to full strong branching, which is known to be the MIP branching rule leading to the fewest number of search nodes. It turns out that cloud branching can reduce the mean running time by up to 30% on standard test sets. Y1 - 2013 U6 - https://doi.org/10.1007/978-3-642-38171-3_3 VL - 7874 SP - 28 EP - 43 PB - Springer ER - TY - GEN A1 - Shinano, Yuji A1 - Heinz, Stefan A1 - Vigerske, Stefan A1 - Winkler, Michael T1 - FiberSCIP - A shared memory parallelization of SCIP N2 - Recently, parallel computing environments have become significantly popular. In order to obtain the benefit of using parallel computing environments, we have to deploy our programs for these effectively. This paper focuses on a parallelization of SCIP (Solving Constraint Integer Programs), which is a MIP solver and constraint integer programming framework available in source code. There is a parallel extension of SCIP named ParaSCIP, which parallelizes SCIP on massively parallel distributed memory computing environments. This paper describes FiberSCIP, which is yet another parallel extension of SCIP to utilize multi-threaded parallel computation on shared memory computing environments, and has the following contributions: First, the basic concept of having two parallel extensions and the relationship between them and the parallelization framework provided by UG (Ubiquity Generator) is presented, including an implementation of deterministic parallelization. Second, the difficulties to achieve a good performance that utilizes all resources on an actual computing environment and the difficulties of performance evaluation of the parallel solvers are discussed. Third, a way to evaluate the performance of new algorithms and parameter settings of the parallel extensions is presented. Finally, current performance of FiberSCIP for solving mixed-integer linear programs (MIPs) and mixed-integer non-linear programs (MINLPs) in parallel is demonstrated. T3 - ZIB-Report - 13-55 KW - parallel KW - branch-and-bound KW - deterministic parallelism KW - constraint integer programming KW - mixed integer programming KW - mixed integer nonlinear programming KW - SCIP KW - MIP KW - MINLP Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42595 SN - 1438-0064 ER - TY - GEN A1 - Gamrath, Gerald T1 - Improving strong branching by domain propagation N2 - One of the essential components of a branch-and-bound based mixed-integer linear programming (MIP) solver is the branching rule. Strong branching is a method used by many state-of-the-art branching rules to select the variable to branch on. It precomputes the dual bounds of potential child nodes by solving auxiliary linear programs (LPs) and thereby helps to take good branching decisions that lead to a small search tree. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Domain propagation is a technique usually used at every node of the branch-and-bound tree to tighten the local domains of variables. Computational experiments on standard MIP instances indicate that our improved strong branching method significantly improves the quality of the predictions and causes almost no additional effort. For a full strong branching rule, we are able to obtain substantial reductions of the branch-and-bound tree size as well as the solving time. Moreover, also the state-of-the-art hybrid branching rule can be improved this way. This paper extends previous work by the author published in the proceedings of the CPAIOR 2013. T3 - ZIB-Report - 13-47 KW - mixed-integer programming KW - branch-and-bound KW - branching rule KW - variable selection KW - strong branching KW - domain propagation Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42546 SN - 1438-0064 ER - TY - GEN A1 - Ballerstein, Martin A1 - Michaels, Dennis A1 - Vigerske, Stefan T1 - Linear Underestimators for bivariate functions with a fixed convexity behavior N2 - This is a technical report for the SCIP constraint handler cons_bivariate. We describe a cut-generation algorithm for a class of bivariate twice continuously differentiable functions with fixed convexity behavior over a box. Computational results comparing our cut-generation algorithms with state-of-the-art global optimization software on a series of randomly generated test instances are reported and discussed. T3 - ZIB-Report - 13-02 KW - bivariate functions KW - convex envelope KW - global optimization KW - linear underestimator Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17641 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Hendel, Gregor T1 - Shift-And-Propagate N2 - For mixed integer programming, recent years have seen a growing interest in the design of general purpose primal heuristics for use inside complete solvers. Many of these heuristics rely on an optimal LP solution. Finding this may itself take a significant amount of time. The presented paper addresses this issue by the introduction of the Shift-And-Propagate heuristic. Shift-And-Propagate is a pre-root primal heuristic that does not require a previously found LP solution. It applies domain propagation techniques to quickly drive a variable assignment towards feasibility. Computational experiments indicate that this heuristic is a powerful supplement of existing rounding and propagation heuristics. T3 - ZIB-Report - 13-03 KW - primal heuristic KW - mixed integer programming KW - domain propagation KW - rounding Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17596 SN - 1438-0064 ER - TY - CHAP A1 - Matuschke, Jannik A1 - Bley, Andreas A1 - Müller, Benjamin ED - Bodlaender, Hans L. ED - Italiano, Giuseppe F. T1 - Approximation Algorithms for Facility Location with Capacitated and Length-Bounded Tree Connections N2 - We consider a generalization of the uncapacitated facility location problem that occurs in planning of optical access networks in telecommunications. Clients are connected to open facilities via depth-bounded trees. The total demand of clients served by a tree must not exceed a given tree capacity. We investigate a framework for combining facility location algorithms with a tree-based clustering approach and derive approximation algorithms for several variants of the problem, using techniques for approximating shallow-light Steiner trees via layer graphs, simultaneous approximation of shortest paths and minimum spanning trees, and greedy coverings. Y1 - 2013 U6 - https://doi.org/10.1007/978-3-642-40450-4_60 VL - Algorithms -- ESA 2013 SP - 707 EP - 718 PB - Springer ER - TY - JOUR A1 - Cook, William A1 - Koch, Thorsten A1 - Steffy, Daniel A1 - Wolter, Kati T1 - A hybrid branch-and-bound approach for exact rational mixed-integer programming JF - Mathematical Programming Computation N2 - We present an exact rational solver for mixed-integer linear programming that avoids the numerical inaccuracies inherent in the floating-point computations used by existing software. This allows the solver to be used for establishing theoretical results and in applications where correct solutions are critical due to legal and financial consequences. Our solver is a hybrid symbolic/numeric implementation of LP-based branch-and-bound, using numerically-safe methods for all binding computations in the search tree. Computing provably accurate solutions by dynamically choosing the fastest of several safe dual bounding methods depending on the structure of the instance, our exact solver is only moderately slower than an inexact floating-point branch-and-bound solver. The software is incorporated into the SCIP optimization framework, using the exact LP solver QSopt_ex and the GMP arithmetic library. Computational results are presented for a suite of test instances taken from the MIPLIB and Mittelmann libraries and for a new collection of numerically difficult instances. Y1 - 2013 U6 - https://doi.org/10.1007/s12532-013-0055-6 VL - 5 IS - 3 SP - 305 EP - 344 ER - TY - JOUR A1 - Shinano, Yuji A1 - Inui, Nobuo A1 - Fukagawa, Youzou A1 - Takakura, Noburu T1 - Optimizing Movement Sequences for Step-and-Scan Lithography Equipment JF - Journal of Advanced Mechanical Design, Systems, and Manufacturing N2 - The purpose of this work is to improve the throughput of step-and-scan lithography equipment to shorten the production time of a wafer. For this purpose, we propose a method for solving the MSOP (Movement Sequence Optimization Problem), which is the problem of computing the fastest schedule for visiting all shots on a wafer. It is well-known that the MSOP on step-and-repeat lithography equipment can be modeled as a traveling salesman problem. In contrast to step-and-repeat lithography equipment, a schedule for step-and-scan lithography equipment must also indicate the scanning direction of each shot, in addition to the sequence of the shots. For this reason, the traveling salesman problem formulation for step-and-repeat lithography equipment cannot be applied to solve the MSOP on step-and-scan lithography equipment directly. We overcame this difficulty by introducing auxiliary vertices to model the scanning directions in the traveling salesman problem formulation. By this method, we were able to compute exact optimal sequences considering the scanning directions of shots for several MSOP instances. Our numerical experiments demonstrated that our proposed method was capable of computing exact optimal solutions for real-world MSOP instances having up to 232 shots on a wafer. These optimal solutions gave a 0.25% to 4.66% improvement in productivity over solutions computed by previously known methods. Y1 - 2013 U6 - https://doi.org/10.1299/jamdsm.7.608 VL - 7 IS - 4 SP - 608 EP - 618 ER - TY - JOUR A1 - Gamrath, Gerald T1 - Improving strong branching by domain propagation JF - EURO Journal on Computational Optimization N2 - One of the essential components of a branch-and-bound based mixed-integer linear programming (MIP) solver is the branching rule. Strong branching is a method used by many state-of-the-art branching rules to select the variable to branch on. It precomputes the dual bounds of potential child nodes by solving auxiliary linear programs (LPs) and thereby helps to take good branching decisions that lead to a small search tree. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Domain propagation is a technique MIP solvers usually apply at every node of the branch-and-bound tree to tighten the local domains of variables. Computational experiments on standard MIP instances indicate that our improved strong branching method significantly improves the quality of the predictions and causes almost no additional effort. For a full strong branching rule, we are able to obtain substantial reductions of the branch-and-bound tree size as well as the solving time. Moreover, the state-of-the-art hybrid branching rule can be improved this way as well. This paper extends previous work by the author published in the proceedings of the CPAIOR 2013. Y1 - 2014 U6 - https://doi.org/10.1007/s13675-014-0021-8 VL - 2 IS - 3 SP - 99 EP - 122 PB - Springer CY - Berlin Heidelberg 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 - JOUR A1 - Berthold, Timo A1 - Hendel, Gregor T1 - Shift-and-Propagate JF - Journal of Heuristics N2 - In recent years, there has been a growing interest in the design of general purpose primal heuristics for use inside complete mixed integer programming solvers. Many of these heuristics rely on an optimal LP solution, which may take a significant amount of time to find. In this paper, we address this issue by introducing a pre-root primal heuristic that does not require a previously found LP solution. This heuristic, named Shift-and-Propagate , applies domain propagation techniques to quickly drive a variable assignment towards feasibility. Computational experiments indicate that this heuristic is a powerful supplement to existing rounding and propagation heuristics. Y1 - 2014 U6 - https://doi.org/10.1007/s10732-014-9271-0 VL - 21 IS - 1 SP - 73 EP - 106 ER - TY - GEN A1 - Gamrath, Gerald A1 - Koch, Thorsten A1 - Rehfeldt, Daniel A1 - Shinano, Yuji T1 - SCIP-Jack - A massively parallel STP solver N2 - In this article we describe the impact from embedding a 15 year old model for solving the Steiner tree problem in graphs in a state-of-the-art MIP-Framework, making the result run in a massively parallel environment and extending the model to solve as many variants as possible. We end up with a high-perfomance solver that is capable of solving previously unsolved instances and, in contrast to its predecessor, is freely available for academic research. T3 - ZIB-Report - 14-35 KW - Steiner Tree Problem KW - Mixed-Integer Programming KW - Branch-and-Cut KW - DIMACS Challenge Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-52293 SN - 1438-0064 ER - TY - GEN A1 - Arnold, Thomas A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Vigerske, Stefan A1 - Henrion, René A1 - Grötschel, Martin A1 - Koch, Thorsten A1 - Tischendorf, Caren A1 - Römisch, Werner ED - Deuflhard, Peter ED - Grötschel, Martin ED - Hömberg, Dietmar ED - Horst, Ulrich ED - Kramer, Jürg ED - Mehrmann, Volker ED - Polthier, Konrad ED - Schmidt, Frank ED - Schütte, Christof ED - Skutella, Martin ED - Sprekels, Jürgen T1 - A Jack of all Trades? Solving stochastic mixed-integer nonlinear constraint programs T2 - MATHEON - Mathematics for Key Technologies N2 - Natural gas is one of the most important energy sources in Germany and Europe. In recent years, political regulations have led to a strict separation of gas trading and gas transport, thereby assigning a central role in energy politics to the transportation and distribution of gas. These newly imposed political requirements influenced the technical processes of gas transport in such a way that the complex task of planning and operating gas networks has become even more intricate. Mathematically, the combination of discrete decisions on the configuration of a gas transport network, the nonlinear equations describing the physics of gas, and the uncertainty in demand and supply yield large-scale and highly complex stochastic mixed-integer nonlinear optimization problems. The Matheon project "Optimization of Gas Transport" takes the key role of making available the necessary core technology to solve the mathematical optimization problems which model the topology planning and the operation of gas networks. An important aspect of the academic impact is the free availability of our framework. As a result of several years of research and development, it is now possible to download a complete state-of-the-art framework for mixed-integer linear and nonlinear programming in source code at http://scip.zib.de Y1 - 2014 U6 - https://doi.org/10.4171/137 VL - 1 SP - 135 EP - 146 PB - European Mathematical Society ER - TY - GEN A1 - Yokoyama, Ryohei A1 - Shinano, Yuji A1 - Taniguchi, Syusuke A1 - Ohkura, Masashi A1 - Wakui, Tetsuya T1 - Optimization of energy supply systems by MILP branch and bound method in consideration of hierarchical relationship between design and operation N2 - To attain the highest performance of energy supply systems, it is necessary to rationally determine types, capacities, and numbers of equipment in consideration of their operational strategies corresponding to seasonal and hourly variations in energy demands. In the combinatorial optimization method based on the mixed-integer linear programming (MILP), integer variables are used to express the selection, numbers, and on/off status of operation of equipment, and the number of these variables increases with those of equipment and periods for variations in energy demands, and affects the computation efficiency significantly. In this paper, a MILP method utilizing the hierarchical relationship between design and operation variables is proposed to solve the optimal design problem of energy supply systems efficiently: At the upper level, the optimal values of design variables are searched by the branch and bound method; At the lower level, the values of operation variables are optimized independently at each period by the branch and bound method under the values of design variables given tentatively during the search at the upper level; Lower bounds for the optimal value of the objective function are evaluated, and are utilized for the bounding operations at both the levels. This method is implemented into open and commercial MILP solvers. Illustrative and practical case studies on the optimal design of cogeneration systems are conducted, and the validity and effectiveness of the proposed method are clarified. T3 - ZIB-Report - 14-09 KW - Energy supply systems KW - Optimal design KW - Optimal operation KW - Mixed-integer linear programming KW - Branch and bound method KW - Hierarchical approach Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-49413 SN - 1438-0064 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 - GEN A1 - Shinano, Yuji A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Koch, Thorsten A1 - Winkler, Michael T1 - Solving Open MIP Instances with ParaSCIP on Supercomputers using up to 80,000 Cores N2 - This paper describes how we solved 12 previously unsolved mixed-integer program- ming (MIP) instances from the MIPLIB benchmark sets. To achieve these results we used an enhanced version of ParaSCIP, setting a new record for the largest scale MIP computation: up to 80,000 cores in parallel on the Titan supercomputer. In this paper we describe the basic parallelization mechanism of ParaSCIP, improvements of the dynamic load balancing and novel techniques to exploit the power of parallelization for MIP solving. We give a detailed overview of computing times and statistics for solving open MIPLIB instances. T3 - ZIB-Report - 15-53 KW - Mixed Integer Programming KW - Parallel processing KW - Node merging KW - Racing ParaSCIP KW - Ubiquity Generator Framework KW - MIPLIB Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-56404 SN - 1438-0064 ER - TY - CHAP A1 - Gamrath, Gerald A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Winkler, Michael T1 - Structure-Based Primal Heuristics for Mixed Integer Programming T2 - Optimization in the Real World N2 - Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They help to reach optimality faster and provide good feasible solutions early in the solving process. In this paper, we present two new primal heuristics which take into account global structures available within MIP solvers to construct feasible solutions at the beginning of the solving process. These heuristics follow a large neighborhood search (LNS) approach and use global structures to define a neighborhood that is with high probability significantly easier to process while (hopefully) still containing good feasible solutions. The definition of the neighborhood is done by iteratively fixing variables and propagating these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. The neighborhood is solved as a sub-MIP and solutions are transferred back to the original problem. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about every third instance and therewith help to improve the average solving time. Y1 - 2015 SN - 978-4-431-55419-6 U6 - https://doi.org/10.1007/978-4-431-55420-2_3 VL - 13 SP - 37 EP - 53 PB - Springer Japan ER - TY - GEN A1 - Fujisawa, Katsuki A1 - Shinano, Yuji A1 - Waki, Hayato T1 - Optimization in the Real World T2 - Mathematics for Industry (MFI) Y1 - 2015 SN - 978-4-431-55419-6 U6 - https://doi.org/10.1007/978-4-431-55420-2 VL - 13 PB - Springer Tokyo Heidelberg New York Dordrecht London 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 - Witzig, Jakob A1 - Gamrath, Gerald A1 - Hiller, Benjamin T1 - Reoptimization Techniques in MIP Solvers N2 - Recently, there have been many successful applications of optimization algorithms that solve a sequence of quite similar mixed-integer programs (MIPs) as subproblems. Traditionally, each problem in the sequence is solved from scratch. In this paper we consider reoptimization techniques that try to benefit from information obtained by solving previous problems of the sequence. We focus on the case that subsequent MIPs differ only in the objective function or that the feasible region is reduced. We propose extensions of the very complex branch-and-bound algorithms employed by general MIP solvers based on the idea to ``warmstart'' using the final search frontier of the preceding solver run. We extend the academic MIP solver SCIP by these techniques to obtain a reoptimizing branch-and-bound solver and report computational results which show the effectiveness of the approach. T3 - ZIB-Report - 15-24 Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54375 SN - 1438-0064 ER - TY - JOUR A1 - Yokoyama, Ryohei A1 - Shinano, Yuji A1 - Taniguchi, Syusuke A1 - Ohkura, Masashi A1 - Wakui, Tetsuya T1 - Optimization of energy supply systems by MILP branch and bound method in consideration of hierarchical relationship between design and operation JF - Energy Conversion and Management N2 - To attain the highest performance of energy supply systems, it is necessary to rationally determine types, capacities, and numbers of equipment in consideration of their operational strategies corresponding to seasonal and hourly variations in energy demands. In the combinatorial optimization method based on the mixed-integer linear programming (MILP), integer variables are used to express the selection, numbers, and on/off status of operation of equipment, and the number of these variables increases with those of equipment and periods for variations in energy demands, and affects the computation efficiency significantly. In this paper, a MILP method utilizing the hierarchical relationship between design and operation variables is proposed to solve the optimal design problem of energy supply systems efficiently: At the upper level, the optimal values of design variables are searched by the branch and bound method; At the lower level, the values of operation variables are optimized independently at each period by the branch and bound method under the values of design variables given tentatively during the search at the upper level; Lower bounds for the optimal value of the objective function to be minimized are evaluated, and are utilized for the bounding operations at both the levels. This method is implemented into open and commercial MILP solvers. Illustrative and practical case studies on the optimal design of cogeneration systems are conducted, and the validity and effectiveness of the proposed method are clarified. Y1 - 2015 U6 - https://doi.org/10.1016/j.enconman.2014.12.020 VL - 92 SP - 92 EP - 104 ER - TY - CHAP A1 - Yokoyama, Ryohei A1 - Shinano, Yuji T1 - MILP Approaches to Optimal Design and Operation of Distributed Energy Systems T2 - Optimization in the Real World N2 - Energy field is one of the practical areas to which optimization can contribute significantly. In this chapter, the application of mixed-integer linear programming (MILP) approaches to optimal design and operation of distributed energy systems is described. First, the optimal design and operation problems are defined, and relevant previous work is reviewed. Then, an MILP method utilizing the hierarchical relationship between design and operation variables is presented. In the optimal design problem, integer variables are used to express the types, capacities, numbers, operation modes, and on/off states of operation of equipment, and the number of these variables increases with those of equipment and periods for variations in energy demands, and affects the computation efficiency significantly. The presented method can change the enumeration tree for the branching and bounding procedures, and can search the optimal solution very efficiently. Finally, future work in relation to this method is described. Y1 - 2015 SN - 978-4-431-55419-6 U6 - https://doi.org/10.1007/978-4-431-55420-2_9 VL - Volume 13 SP - 157 EP - 176 PB - Springer ER -