TY - GEN A1 - Achterberg, Tobias A1 - Koch, Thorsten A1 - Martin, Alexander T1 - Branching on History Information N2 - Mixed integer programs ($MIPs$) are commonly solved with branch and bound algorithms based on linear programming. The success and the speed of the algorithm strongly depends on the strategy used to select the branching variables. Today's state-of-the-art strategy is called \emph{pseudocost branching} and uses information of previous branchings to determine the current branching. We propose a modification of \emph{pseudocost branching} which we call \emph{history branching}. This strategy has been implemented in $SIP$, a state-of-the-art $MIP$ solver. We give computational results that show the superiority of the new strategy. T3 - ZIB-Report - 02-32 KW - Mixed Integer Programming KW - Branch-and-Bound KW - Branching Rules KW - Pseudocost Branching Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6990 ER - TY - GEN A1 - Achterberg, Tobias A1 - Berthold, Timo T1 - Improving the Feasibility Pump N2 - The Feasibility Pump of Fischetti, Glover, Lodi, and Bertacco has proved to be a very successful heuristic for finding feasible solutions of mixed integer programs. The quality of the solutions in terms of the objective value, however, tends to be poor. This paper proposes a slight modification of the algorithm in order to find better solutions. Extensive computational results show the success of this variant: in 89 out of 121 MIP instances the modified version produces improved solutions in comparison to the original Feasibility Pump. T3 - ZIB-Report - 05-42 KW - mixed integer programming KW - primal heuristics KW - feasibility pump Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8754 ER - TY - GEN A1 - Achterberg, Tobias T1 - SCIP - a framework to integrate Constraint and Mixed Integer Programming N2 - Constraint Programs and Mixed Integer Programs are closely related optimization problems originating from different scientific areas. Today's state-of-the-art algorithms of both fields have several strategies in common, in particular the branch-and-bound process to recursively divide the problem into smaller sub problems. On the other hand, the main techniques to process each sub problem are different, and it was observed that they have complementary strenghts. We propose a programming framework {\sffamily SCIP} that integrates techniques from both fields in order to exploit the strenghts of both, Constraint Programming and Mixed Integer Programming. In contrast to other proposals of recent years to combine both fields, {\sffamily SCIP} does not focus on easy implementation and rapid prototyping, but is tailored towards expert users in need of full, in-depth control and high performance. T3 - ZIB-Report - 04-19 KW - Mixed Integer Programming KW - MIP KW - Constraint Programming KW - CP KW - branch-and-bound Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7947 ER - TY - GEN A1 - Achterberg, Tobias A1 - Koch, Thorsten A1 - Martin, Alexander T1 - Branching rules revisited N2 - Mixed integer programs are commonly solved with linear programming based branch-and-bound algorithms. The success of the algorithm strongly depends on the strategy used to select the variable to branch on. We present a new generalization called {\sl reliability branching} of today's state-of-the-art {\sl strong branching} and {\sl pseudocost branching} strategies for linear programming based branch-and-bound algorithms. After reviewing commonly used branching strategies and performing extensive computational studies we compare different parameter settings and show the superiority of our proposed newstrategy. T3 - ZIB-Report - 04-13 KW - Mixed-integer-programming KW - Branch-and-Bound KW - Variable selection KW - Pseudocost-Branching KW - Strong-Branching KW - Reliability-Branching Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7886 ER - TY - THES A1 - Achterberg, Tobias T1 - Constraint Integer Programming N2 - This thesis introduces the novel paradigm of "constraint integer programming" (CIP), which integrates constraint programming (CP) and mixed integer programming (MIP) modeling and solving techniques. It is supplemented by the software SCIP, which is a solver and framework for constraint integer programming that also features SAT solving techniques. SCIP is freely available in source code for academic and non-commercial purposes. Our constraint integer programming approach is a generalization of MIP that allows for the inclusion of arbitrary constraints, as long as they turn into linear constraints on the continuous variables after all integer variables have been fixed. The constraints, may they be linear or more complex, are treated by any combination of CP and MIP techniques: the propagation of the domains by constraint specific algorithms, the generation of a linear relaxation and its solving by LP methods, and the strengthening of the LP by cutting plane separation. The current version of SCIP comes with all of the necessary components to solve mixed integer programs. In the thesis, we cover most of these ingredients and present extensive computational results to compare different variants for the individual building blocks of a MIP solver. We focus on the algorithms and their impact on the overall performance of the solver. In addition to mixed integer programming, the thesis deals with chip design verification, which is an important topic of electronic design automation. Chip manufacturers have to make sure that the logic design of a circuit conforms to the specification of the chip. Otherwise, the chip would show an erroneous behavior that may cause failures in the device where it is employed. An important subproblem of chip design verification is the property checking problem, which is to verify whether a circuit satisfies a specified property. We show how this problem can be modeled as constraint integer program and provide a number of problem-specific algorithms that exploit the structure of the individual constraints and the circuit as a whole. Another set of extensive computational benchmarks compares our CIP approach to the current state-of-the-art SAT methodology and documents the success of our method. N2 - Diese Arbeit stellt einen integrierten Ansatz aus "Constraint Programming" (CP) und Gemischt-Ganzzahliger Programmierung ("Mixed Integer Programming", MIP) vor, den wir "Constraint Integer Programming" (CIP) nennen. Sowohl Modellierungs- als auch Lösungstechniken beider Felder fließen in den neuen integrierten Ansatz ein, um die unterschiedlichen Stärken der beiden Gebiete zu kombinieren. Als weiteren Beitrag stellen wir der wissenschaftlichen Gemeinschaft die Software SCIP zur Verfügung, die ein Framework für Constraint Integer Programming darstellt und zusätzlich Techniken des SAT-Lösens beinhaltet. SCIP ist im Source Code für akademische und nicht-kommerzielle Zwecke frei erhältlich. Unser Ansatz des Constraint Integer Programming ist eine Verallgemeinerung von MIP, die zusätzlich die Verwendung beliebiger Constraints erlaubt, solange sich diese durch lineare Bedingungen ausdrücken lassen falls alle ganzzahligen Variablen auf feste Werte eingestellt sind. Die Constraints werden von einer beliebigen Kombination aus CP- und MIP-Techniken behandelt. Dies beinhaltet insbesondere die "Domain Propagation", die Relaxierung der Constraints durch lineare Ungleichungen, sowie die Verstärkung der Relaxierung durch dynamisch generierte Schnittebenen. Die derzeitige Version von SCIP enthält alle Komponenten, die für das effiziente Lösen von Gemischt-Ganzzahligen Programmen benötigt werden. Die vorliegende Arbeit liefert eine ausführliche Beschreibung dieser Komponenten und bewertet verschiedene Varianten in Hinblick auf ihren Einfluß auf das Gesamt-Lösungsverhalten anhand von aufwendigen praktischen Experimenten. Dabei wird besonders auf die algorithmischen Aspekte eingegangen. Ein weiterer Hauptteil der Arbeit befasst sich mit der Chip-Design-Verifikation, die ein wichtiges Thema innerhalb des Fachgebiets der "Electronic Design Automation" darstellt. Chip-Hersteller müssen sicherstellen, dass der logische Entwurf einer Schaltung der gegebenen Spezifikation entspricht. Andernfalls würde der Chip fehlerhaftes Verhalten aufweisen, dass zu Fehlfunktionen innerhalb des Gerätes führen kann, in dem der Chip verwendet wird. Ein wichtiges Teilproblem in diesem Feld ist das Eigenschafts-Verifikations-Problem, bei dem geprüft wird, ob der gegebene Schaltkreisentwurf eine gewünschte Eigenschaft aufweist. Wir zeigen, wie dieses Problem als Constraint Integer Program modelliert werden kann und geben eine Reihe von problemspezifischen Algorithmen an, die die Struktur der einzelnen Constraints und der Gesamtschaltung ausnutzen. Testrechnungen auf Industrie-Beispielen vergleichen unseren Ansatz mit den bisher verwendeten SAT-Techniken und belegen den Erfolg unserer Methode. KW - Ganzzahlige Programmierung KW - Constraint Programmierung KW - SAT KW - Chip-Verifikation KW - Mathematische Programmierung KW - Integer Programming KW - Constraint Programming KW - SAT KW - Chip Verification KW - Mathematical Programming Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11129 ER - TY - GEN A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Koch, Thorsten A1 - Wolter, Kati T1 - Constraint Integer Programming: a New Approach to Integrate CP and MIP N2 - This article introduces constraint integer programming (CIP), which is a novel way to combine constraint programming (CP) and mixed integer programming (MIP) methodologies. CIP is a generalization of MIP that supports the notion of general constraints as in CP. This approach is supported by the CIP framework SCIP, which also integrates techniques from SAT solving. SCIP is available in source code and free for non-commercial use. We demonstrate the usefulness of CIP on two tasks. First, we apply the constraint integer programming approach to pure mixed integer programs. Computational experiments show that SCIP is almost competitive to current state-of-the-art commercial MIP solvers. Second, we employ the CIP framework to solve chip design verification problems, which involve some highly non-linear constraint types that are very hard to handle by pure MIP solvers. The CIP approach is very effective here: it can apply the full sophisticated MIP machinery to the linear part of the problem, while dealing with the non-linear constraints by employing constraint programming techniques. T3 - ZIB-Report - 08-01 KW - Constraint Programming KW - Ganzzahlige Programmierung KW - Branch-And-Cut KW - Optimierungssoftware KW - Chipverifikation KW - constraint programming KW - mixed integer programming KW - branch-and-cut KW - optimization software KW - chip verification Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10520 SN - 1438-0064 ER - TY - GEN A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Koch, Thorsten A1 - Wolter, Kati T1 - Constraint Integer Programming: Techniques and Applications N2 - This article introduces constraint integer programming (CIP), which is a novel way to combine constraint programming (CP) and mixed integer programming (MIP) methodologies. CIP is a generalization of MIP that supports the notion of general constraints as in CP. This approach is supported by the CIP framework SCIP, which also integrates techniques for solving satisfiability problems. SCIP is available in source code and free for noncommercial use. We demonstrate the usefulness of CIP on three tasks. First, we apply the constraint integer programming approach to pure mixed integer programs. Computational experiments show that SCIP is almost competitive to current state-of-the-art commercial MIP solvers. Second, we demonstrate how to use CIP techniques to compute the number of optimal solutions of integer programs. Third, we employ the CIP framework to solve chip design verification problems, which involve some highly nonlinear constraint types that are very hard to handle by pure MIP solvers. The CIP approach is very effective here: it can apply the full sophisticated MIP machinery to the linear part of the problem, while dealing with the nonlinear constraints by employing constraint programming techniques. T3 - ZIB-Report - 08-43 KW - constraint programming KW - mixed integer programming KW - branch-and-cut KW - optimization software KW - chip verification Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10950 SN - 1438-0064 ER - TY - GEN A1 - Achterberg, Tobias A1 - Koch, Thorsten A1 - Tuchscherer, Andreas T1 - On the Effects of Minor Changes in Model Formulations N2 - Starting with the description of the Traveling Salesmen Problem formulation as given by van Vyve and Wolsey in the article Approximate extended formulations'', we investigate the effects of small variations onto the performance of contemporary mixed integer programming solvers. We will show that even minor changes in the formulation of the model can result in performance difference of more than a factor of 1000. As the results show it is not obvious which changes will result in performance improvements and which not. T3 - ZIB-Report - 08-29 Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10808 SN - 1438-0064 ER - TY - GEN A1 - Achterberg, Tobias A1 - Heinz, Stefan A1 - Koch, Thorsten T1 - Counting solutions of integer programs using unrestricted subtree detection N2 - In the recent years there has been tremendous progress in the development of algorithms to find optimal solutions for integer programs. In many applications it is, however, desirable (or even necessary) to generate all feasible solutions. Examples arise in the areas of hardware and software verification and discrete geometry. In this paper, we investigate how to extend branch-and-cut integer programming frameworks to support the generation of all solutions. We propose a method to detect so-called unrestricted subtrees, which allows us to prune the integer program search tree and to collect several solutions simultaneously. We present computational results of this branch-and-count paradigm which show the potential of the unrestricted subtree detection. T3 - ZIB-Report - 08-09 KW - Zählen KW - ganzzahlige Programme KW - IP KW - counting KW - integer programming KW - IP Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10632 SN - 1438-0064 ER - TY - GEN A1 - Achterberg, Tobias A1 - Grötschel, Martin A1 - Koch, Thorsten T1 - Software for Teaching Modeling of Integer Programming Problems N2 - Modern applications of mathematical programming must take into account a multitude of technical details, business demands, and legal requirements. Teaching the mathematical modeling of such issues and their interrelations requires real-world examples that are well beyond the toy sizes that can be tackled with the student editions of most commercial software packages. We present a new tool, which is freely available for academic use including complete source code. It consists of an algebraic modeling language and a linear mixed integer programming solver. The performance and features of the tool are in the range of current state-of-the-art commercial tools, though not in all aspects as good as the best ones. Our tool does allow the execution and analysis of large real-world instances in the classroom and can therefore enhance the teaching of problem solving issues. Teaching experience has been gathered and practical usability was tested in classes at several universities and a two week intensive block course at TU Berlin. The feedback from students and teachers has been very positive. T3 - ZIB-Report - 06-23 KW - Integer Programming KW - Modelling KW - MIP-Solver KW - Algebraic Modelling Languages KW - Teaching Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9176 ER - TY - GEN A1 - Achterberg, Tobias A1 - Koch, Thorsten A1 - Martin, Alexander T1 - MIPLIB 2003 N2 - This paper reports on the fourth version of the Mixed Integer Programming Library. Since ({\sc miplib}) is to provide a concise set of challenging problems, it became necessary to purge instances that became too easy. We present an overview of the 27 new problems and statistical data for all 60 instances. T3 - ZIB-Report - 05-28 KW - Mathematical Programming KW - Mixed Integer Programming KW - IP KW - MIP KW - Optimization KW - Instances Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8625 ER - TY - GEN A1 - Achterberg, Tobias A1 - Brinkmann, Raik A1 - Wedler, Markus T1 - Property Checking with Constraint Integer Programming N2 - We address the property checking problem for SoC design verification at the register transfer level (RTL) by integrating techniques from integer programming, constraint programming, and SAT solving. Specialized domain propagation and preprocessing algorithms for individual RTL operations extend a general constraint integer programming framework. Conflict clauses are learned by analyzing infeasible LPs and deductions, and by employing reverse propagation. Experimental results show that our approach outperforms SAT techniques for proving the validity of properties on circuits containing arithmetics. T3 - ZIB-Report - 07-37 KW - formale Chip Verifikation KW - constraint integer programming KW - scip KW - Eigenschaftsprüfer KW - formal chip verification KW - constraint integer programming KW - scip KW - property checking KW - micro chip Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10376 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 - Shinano, Yuji A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Koch, Thorsten T1 - ParaSCIP - a parallel extension of SCIP N2 - Mixed integer programming (MIP) has become one of the most important techniques in Operations Research and Discrete Optimization. SCIP (Solving Constraint Integer Programs) is currently one of the fastest non-commercial MIP solvers. It is based on the branch-and-bound procedure in which the problem is recursively split into smaller subproblems, thereby creating a so-called branching tree. We present ParaSCIP, an extension of SCIP, which realizes a parallelization on a distributed memory computing environment. ParaSCIP uses SCIP solvers as independently running processes to solve subproblems (nodes of the branching tree) locally. This makes the parallelization development independent of the SCIP development. Thus, ParaSCIP directly profits from any algorithmic progress in future versions of SCIP. Using a first implementation of ParaSCIP, we were able to solve two previously unsolved instances from MIPLIB2003, a standard test set library for MIP solvers. For these computations, we used up to 2048 cores of the HLRN~II supercomputer. T3 - ZIB-Report - 10-27 KW - massive parallization KW - mixed integer programming KW - ParaSCIP KW - branch-and-cut KW - branch-and-bound Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11921 UR - http://www.springerlink.com/content/t2160206253v7661/ ER - TY - GEN A1 - Achterberg, Tobias A1 - Raack, Christian T1 - The MCF-Separator -- Detecting and Exploiting Multi-Commodity Flow Structures in MIPs N2 - Given a general mixed integer program (MIP), we automatically detect block structures in the constraint matrix together with the coupling by capacity constraints arising from multi-commodity-flow formulations. We identify the underlying graph and generate cutting planes based on cuts in the detected network. Our implementation adds a separator to the branch-and-cut libraries of SCIP and CPLEX. We make use of the complemented mixed integer rounding framework (cMIR) but provide a special purpose aggregation heuristic that exploits the network structure. Our separation scheme speeds-up the computation for a large set of MIPs coming from network design problems by a factor of two on average. T3 - ZIB-Report - 09-38 KW - mixed integer programming KW - network detection KW - cut-based inequalities KW - cplex KW - scip Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11592 SN - 1438-0064 ER - TY - JOUR A1 - Achterberg, Tobias A1 - Grötschel, Martin A1 - Koch, Thorsten T1 - Teaching MIP Modeling and Solving JF - OR/MS Today Y1 - 2006 UR - http://www.lionhrtpub.com/orms/orms-12-06/freducation.html VL - 33 IS - 6 SP - 14 EP - 15 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 - JOUR A1 - Achterberg, Tobias A1 - Raack, Christian T1 - The MCF-Separator – Detecting and Exploiting Multi-Commodity Flows in MIPs JF - Mathematical Programming C Y1 - 2010 UR - http://www.springerlink.com/content/383250gmx3184126/ IS - 2 SP - 125 EP - 165 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 - 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 -