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 - THES A1 - Heinz, Stefan T1 - Policies for Online Target Date Assignment Problems: Competitive Analysis versus Expected Performance Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9933 ER - TY - CHAP 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 T2 - Proc. of 30th IEEE International Parallel & Distributed Processing Symposium 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. Y1 - 2016 U6 - https://doi.org/10.1109/IPDPS.2016.56 ER - TY - GEN A1 - Harks, Tobias A1 - Heinz, Stefan A1 - Pfetsch, Marc A1 - Vredeveld, Tjark T1 - Online Multicommodity Routing with Time Windows N2 - We consider a multicommodity routing problem, where demands are released \emph{online} and have to be routed in a network during specified time windows. The objective is to minimize a time and load dependent convex cost function of the aggregate arc flow. First, we study the fractional routing variant. We present two online algorithms, called Seq and Seq$^2$. Our first main result states that, for cost functions defined by polynomial price functions with nonnegative coefficients and maximum degree~$d$, the competitive ratio of Seq and Seq$^2$ is at most $(d+1)^{d+1}$, which is tight. We also present lower bounds of $(0.265\,(d+1))^{d+1}$ for any online algorithm. In the case of a network with two nodes and parallel arcs, we prove a lower bound of $(2-\frac{1}{2} \sqrt{3})$ on the competitive ratio for Seq and Seq$^2$, even for affine linear price functions. Furthermore, we study resource augmentation, where the online algorithm has to route less demand than the offline adversary. Second, we consider unsplittable routings. For this setting, we present two online algorithms, called U-Seq and U-Seq$^2$. We prove that for polynomial price functions with nonnegative coefficients and maximum degree~$d$, the competitive ratio of U-Seq and U-Seq$^2$ is bounded by $O{1.77^d\,d^{d+1}}$. We present lower bounds of $(0.5307\,(d+1))^{d+1}$ for any online algorithm and $(d+1)^{d+1}$ for our algorithms. Third, we consider a special case of our framework: online load balancing in the $\ell_p$-norm. For the fractional and unsplittable variant of this problem, we show that our online algorithms are $p$ and $O{p}$ competitive, respectively. Such results where previously known only for scheduling jobs on restricted (un)related parallel machines. T3 - ZIB-Report - 07-22 KW - Online Optimization KW - Routing KW - Telecommunications Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9654 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 - Heinz, Stefan A1 - Schulz, Jens T1 - An approximative Criterion for the Potential of Energetic Reasoning N2 - Energetic reasoning is one of the most powerful propagation algorithms in cumulative scheduling. In practice, however, it is not commonly used because it has a high running time and its success highly depends on the tightness of the variable bounds. In order to speed up energetic reasoning, we provide an easy-to-check necessary condition for energetic reasoning to detect infeasibilities. We present an implementation of energetic reasoning that employs this condition and that can be parametrically adjusted to handle the trade-off between solving time and propagation overhead. Computational results on instances from the PSPLIB are provided. These results show that using this condition decreases the running time by more than a half, although more search nodes need to be explored. T3 - ZIB-Report - 11-12 KW - conflict analysis KW - constraint integer programming KW - cumulative constraint KW - resource-constrained project scheduling KW - energetic reasoning Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-12655 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 - 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 - GEN A1 - Heinz, Stefan A1 - Schulz, Jens A1 - Beck, J. Christopher T1 - Using dual presolving reductions to reformulate cumulative constraints N2 - Dual presolving reductions are a class of reformulation techniques that remove feasible or even optimal solutions while guaranteeing that at least one optimal solution remains, as long as the original problem was feasible. Presolving and dual reductions are important components of state-of-the-art mixed-integer linear programming solvers. In this paper, we introduce them both as unified, practical concepts in constraint programming solvers. Building on the existing idea of variable locks, we formally define and justify the use of dual information for cumulative constraints during a presolving phase of a solver. In particular, variable locks are used to decompose cumulative constraints, detect irrelevant variables, and infer variable assignments and domain reductions. Since the computational complexity of propagation algorithms typically depends on the number of variables and/or domain size, such dual reductions are a source of potential computational speed-up. Through experimental evidence on resource constrained project scheduling problems, we demonstrate that the conditions for dual reductions are present in well-known benchmark instances and that a substantial proportion of them can be solved to optimality in presolving -- without search. While we consider this result very promising, we do not observe significant change in overall run-time from the use of our novel dual reductions. T3 - ZIB-Report - 12-37 KW - dual reductions KW - cumulative constraints KW - presolving KW - variable locks Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-16321 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 - Berthold, Timo A1 - Heinz, Stefan A1 - Lübbecke, Marco A1 - Möhring, Rolf A1 - Schulz, Jens T1 - A Constraint Integer Programming Approach for Resource-Constrained Project Scheduling N2 - We propose a hybrid approach for solving the resource-constrained project scheduling problem which is an extremely hard to solve combinatorial optimization problem of practical relevance. Jobs have to be scheduled on (renewable) resources subject to precedence constraints such that the resource capacities are never exceeded and the latest completion time of all jobs is minimized. The problem has challenged researchers from different communities, such as integer programming (IP), constraint programming (CP), and satisfiability testing (SAT). Still, there are instances with 60 jobs which have not been solved for many years. The currently best known approach, lazyFD, is a hybrid between CP and SAT techniques. In this paper we propose an even stronger hybridization by integrating all the three areas, IP, CP, and SAT, into a single branch-and-bound scheme. We show that lower bounds from the linear relaxation of the IP formulation and conflict analysis are key ingredients for pruning the search tree. First computational experiments show very promising results. For five instances of the well-known PSPLIB we report an improvement of lower bounds. Our implementation is generic, thus it can be potentially applied to similar problems as well. T3 - ZIB-Report - 10-03 KW - constraint integer programming KW - cumulative constraint KW - scheduling KW - conflict analysis KW - resource-constrained project Scheduling Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11180 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Pfetsch, Marc T1 - Nonlinear pseudo-Boolean optimization: relaxation or propagation? N2 - Pseudo-Boolean problems lie on the border between satisfiability problems, constraint programming, and integer programming. In particular, nonlinear constraints in pseudo-Boolean optimization can be handled by methods arising in these different fields: One can either linearize them and work on a linear programming relaxation or one can treat them directly by propagation. In this paper, we investigate the individual strengths of these approaches and compare their computational performance. Furthermore, we integrate these techniques into a branch-and-cut-and-propagate framework, resulting in an efficient nonlinear pseudo-Boolean solver. T3 - ZIB-Report - 09-11 KW - Pseudo-Boolean KW - constraint integer programming KW - linear relaxation KW - separation algorithm KW - domain propagation Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11232 SN - 1438-0064 ER - TY - GEN A1 - Heinz, Stefan A1 - Stephan, Rüdiger A1 - Schlechte, Thomas T1 - Solving Steel Mill Slab Problems with Branch and Price N2 - The steel mill slab design problem from the CSPLib is a binpacking problem that is motivated by an application of the steel industry and that has been widely studied in the constraint programming community. Recently, several people proposed new models and methods to solve this problem. A steel mill slab library was created which contains 380 instances. A closely related binpacking problem called multiple knapsack problem with color constraints, originated from the same industrial problem, were discussed in the integer programming community. In particular, a simple integer programming for this problem has been given by Forrest et al. [3]. The aim of this paper is to bring these different studies together. Moreover, we adopt the model of [3] for the steel mill slab problem. Using a state of the art integer program solver, this model is capable to solve all instances of the steel mill slab library, mostly in less than one second, to optimality. We improved, thereby, the solution value of 76 instances. T3 - ZIB-Report - 09-14 KW - steel mill slab problem KW - branch-and-price KW - integer programming Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11260 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 - CHAP A1 - Witzig, Jakob A1 - Berthold, Timo A1 - Heinz, Stefan T1 - Experiments with Conflict Analysis in Mixed Integer Programming T2 - Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2017 N2 - The analysis of infeasible subproblems plays an import role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. There are two fundamentally different concepts to generate valid global constraints from infeasible subproblems. The first is to analyze the sequence of implications obtained by domain propagation that led to infeasibility. The result of the analysis is one or more sets of contradicting variable bounds from which so-called conflict constraints can be generated. This concept has its origin in solving satisfiability problems and is similarly used in constraint programming. The second concept is to analyze infeasible linear programming (LP) relaxations. The dual LP solution provides a set of multipliers that can be used to generate a single new globally valid linear constraint. The main contribution of this short paper is an empirical evaluation of two ways to combine both approaches. Experiments are carried out on general MIP instances from standard public test sets such as Miplib2010; the presented algorithms have been implemented within the non-commercial MIP solver SCIP. Moreover, we present a pool-based approach to manage conflicts which addresses the way a MIP solver traverses the search tree better than aging strategies known from SAT solving. Y1 - 2017 U6 - https://doi.org/10.1007/978-3-319-59776-8_17 VL - 10335 SP - 211 EP - 222 PB - Springer ER - TY - CHAP A1 - Shinano, Yuji A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Koch, Thorsten A1 - Winkler, Michael ED - IEEE, T1 - Solving Hard MIPLIP2003 Problems with ParaSCIP on Supercomputers: An Update T2 - IPDPSW'14 Proceedings of the 2014 IEEE, International Parallel & Distributed Processing Symposium Workshops Y1 - 2014 SN - 978-1-4799-4117-9 U6 - https://doi.org/10.1109/IPDPSW.2014.174 SP - 1552 EP - 1561 PB - IEEE Computer Society CY - Washington, DC, USA ER - TY - GEN A1 - Gamrath, Gerald A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Winkler, Michael T1 - Structure-based primal heuristics for mixed integer programming 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. T3 - ZIB-Report - 15-26 KW - mixed-integer programming, large neighborhood search, primal heuristics, domain propagation Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-55518 SN - 1438-0064 ER - TY - GEN A1 - Gamrath, Gerald A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Winkler, Michael T1 - Structure-driven fix-and-propagate heuristics for mixed integer programming N2 - Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They often provide good feasible solutions early in the solving process and help to solve instances to optimality faster. In this paper, we present a scheme for primal start heuristics that can be executed without previous knowledge of an LP solution or a previously found integer feasible solution. It uses global structures available within MIP solvers to iteratively fix integer variables and propagate these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. If sufficiently many variables can be fixed that way, the resulting problem is solved as an LP and the solution is rounded. If the rounded solution did not provide a feasible solution already, a sub-MIP is solved for the neighborhood defined by the variable fixings performed in the first phase. The global structures help to define a neighborhood that is with high probability significantly easier to process while (hopefully) still containing good feasible solutions. We present three primal heuristics that use this scheme based on different global structures. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about three out of five instances and therewith help to improve several performance measures for MIP solvers, including the primal integral and the average solving time. T3 - ZIB-Report - 17-56 KW - mixed-integer programming KW - primal heuristics KW - fix-and-propagate KW - large neighborhood search KW - domain propagation Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-65387 SN - 1438-0064 ER - TY - GEN A1 - Heinz, Stefan A1 - Beck, J. Christopher T1 - Reconsidering Mixed Integer Programming and MIP-based Hybrids for Scheduling N2 - Despite the success of constraint programming (CP) for scheduling, the much wider penetration of mixed integer programming (MIP) technology into business applications means that many practical scheduling problems are being addressed with MIP, at least as an initial approach. Furthermore, there has been impressive and well-documented improvements in the power of generic MIP solvers over the past decade. We empirically demonstrate that on an existing set of resource allocation and scheduling problems standard MIP and CP models are now competitive with the state-of-the-art manual decomposition approach. Motivated by this result, we formulate two tightly coupled hybrid models based on constraint integer programming (CIP) and demonstrate that these models, which embody advances in CP and MIP, are able to out-perform the CP, MIP, and decomposition models. We conclude that both MIP and CIP are technologies that should be considered along with CP for solving scheduling problems. T3 - ZIB-Report - 12-05 KW - constraint integer programming KW - constraint programming KW - cumulative constraint KW - mixed integer programming KW - optional activities Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14660 SN - 1438-0064 ER -