@misc{BertholdHeinzLuebbeckeetal., author = {Berthold, Timo and Heinz, Stefan and L{\"u}bbecke, Marco and M{\"o}hring, Rolf and Schulz, Jens}, title = {A Constraint Integer Programming Approach for Resource-Constrained Project Scheduling}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11180}, number = {10-03}, abstract = {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.}, language = {en} } @misc{BertholdHeinzVigerske, author = {Berthold, Timo and Heinz, Stefan and Vigerske, Stefan}, title = {Extending a CIP framework to solve MIQCPs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11371}, number = {09-23}, abstract = {This paper discusses how to build a solver for mixed integer quadratically constrained programs (MIQCPs) by extending a framework for constraint integer programming (CIP). The advantage of this approach is that we can utilize the full power of advanced MIP and CP technologies. In particular, this addresses the linear relaxation and the discrete components of the problem. For relaxation, we use an outer approximation generated by linearization of convex constraints and linear underestimation of nonconvex constraints. Further, we give an overview of the reformulation, separation, and propagation techniques that are used to handle the quadratic constraints efficiently. We implemented these methods in the branch-cut-and-price framework SCIP. Computational experiments indicates the potential of the approach.}, language = {en} } @misc{BertholdHeinzPfetsch, author = {Berthold, Timo and Heinz, Stefan and Pfetsch, Marc}, title = {Nonlinear pseudo-Boolean optimization: relaxation or propagation?}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11232}, number = {09-11}, abstract = {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.}, language = {en} } @misc{HeinzStephanSchlechte, author = {Heinz, Stefan and Stephan, R{\"u}diger and Schlechte, Thomas}, title = {Solving Steel Mill Slab Problems with Branch and Price}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11260}, number = {09-14}, abstract = {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.}, language = {en} } @misc{AchterbergBertholdHeinzetal., author = {Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten and Wolter, Kati}, title = {Constraint Integer Programming: Techniques and Applications}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10950}, number = {08-43}, abstract = {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.}, language = {en} } @misc{HeinzSachenbacher, author = {Heinz, Stefan and Sachenbacher, Martin}, title = {Using Model Counting to Find Optimal Distinguishing Tests}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10832}, number = {08-32}, abstract = {Testing is the process of stimulating a system with inputs in order to reveal hidden parts of the system state. In the case of non-deterministic systems, the difficulty arises that an input pattern can generate several possible outcomes. Some of these outcomes allow to distinguish between different hypotheses about the system state, while others do~not. In this paper, we present a novel approach to find, for non-deterministic systems modeled as constraints over variables, tests that allow to distinguish among the hypotheses as good as possible. The idea is to assess the quality of a test by determining the ratio of distinguishing (good) and not distinguishing (bad) outcomes. This measure refines previous notions proposed in the literature on model-based testing and can be computed using model counting techniques. We propose and analyze a greedy-type algorithm to solve this test optimization problem, using existing model counters as a building block. We give preliminary experimental results of our method, and discuss possible improvements.}, language = {en} } @misc{AchterbergHeinzKoch, author = {Achterberg, Tobias and Heinz, Stefan and Koch, Thorsten}, title = {Counting solutions of integer programs using unrestricted subtree detection}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10632}, number = {08-09}, abstract = {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.}, language = {en} } @misc{BertholdHeinzPfetsch, author = {Berthold, Timo and Heinz, Stefan and Pfetsch, Marc}, title = {Solving Pseudo-Boolean Problems with SCIP}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10671}, number = {08-12}, abstract = {Pseudo-Boolean problems generalize SAT problems by allowing linear constraints and a linear objective function. Different solvers, mainly having their roots in the SAT domain, have been proposed and compared,for instance, in Pseudo-Boolean evaluations. One can also formulate Pseudo-Boolean models as integer programming models. That is,Pseudo-Boolean problems lie on the border between the SAT domain and the integer programming field. In this paper, we approach Pseudo-Boolean problems from the integer programming side. We introduce the framework SCIP that implements constraint integer programming techniques. It integrates methods from constraint programming, integer programming, and SAT-solving: the solution of linear programming relaxations, propagation of linear as well as nonlinear constraints, and conflict analysis. We argue that this approach is suitable for Pseudo-Boolean instances containing general linear constraints, while it is less efficient for pure SAT problems. We present extensive computational experiments on the test set used for the Pseudo-Boolean evaluation 2007. We show that our approach is very efficient for optimization instances and competitive for feasibility problems. For the nonlinear parts, we also investigate the influence of linear programming relaxations and propagation methods on the performance. It turns out that both techniques are helpful for obtaining an efficient solution method.}, language = {en} } @misc{HarksHeinzPfetsch, author = {Harks, Tobias and Heinz, Stefan and Pfetsch, Marc}, title = {Competitive Online Multicommodity Routing}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9212}, number = {06-27}, abstract = {We study online multicommodity minimum cost routing problems in networks, where commodities have to be routed sequentially. Arcs are equipped with load dependent price functions defining the routing weights. We discuss an online algorithm that routes each commodity by minimizing a convex cost function that depends on the demands that are previously routed. We present a competitive analysis of this algorithm showing that for affine linear price functions this algorithm is \$4K/2+K\$-competitive, where \$K\$ is the number of commodities. For the parallel arc case this algorithm is optimal. Without restrictions on the price functions and network, no algorithm is competitive. Finally, we investigate a variant in which the demands have to be routed unsplittably.}, language = {en} } @misc{HarksHeinzPfetsch, author = {Harks, Tobias and Heinz, Stefan and Pfetsch, Marc}, title = {Competitive Online Multicommodity Routing}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9599}, number = {07-16}, abstract = {In this paper we study online multicommodity routing problems in networks, in which commodities have to be routed sequentially. The flow of each commodity can be split on several paths. Arcs are equipped with load dependent price functions defining routing costs, which have to be minimized. We discuss a greedy online algorithm that routes each commodity by minimizing a convex cost function that only depends on the demands previously routed. We present a competitive analysis of this algorithm showing that for affine linear price functions this algorithm is 4K2 (1+K)2 -competitive, where K is the number of commodities. For the single-source single-destination case, this algorithm is optimal. Without restrictions on the price functions and network, no algorithm is competitive. Finally, we investigate a variant in which the demands have to be routed unsplittably.}, language = {en} } @misc{HeinzKrumkeMegowetal., author = {Heinz, Stefan and Krumke, Sven and Megow, Nicole and Rambau, J{\"o}rg and Tuchscherer, Andreas and Vredeveld, Tjark}, title = {The Online Target Date Assignment Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8945}, number = {05-61}, abstract = {Many online problems encountered in real-life involve a two-stage decision process: upon arrival of a new request, an irrevocable first-stage decision (the assignment of a specific resource to the request) must be made immediately, while in a second stage process, certain ``subinstances'' (that is, the instances of all requests assigned to a particular resource) can be solved to optimality (offline) later. We introduce the novel concept of an \emph{Online Target Date Assignment Problem} (\textsc{OnlineTDAP}) as a general framework for online problems with this nature. Requests for the \textsc{OnlineTDAP} become known at certain dates. An online algorithm has to assign a target date to each request, specifying on which date the request should be processed (e.\,g., an appointment with a customer for a washing machine repair). The cost at a target date is given by the \emph{downstream cost}, the optimal cost of processing all requests at that date w.\,r.\,t.\ some fixed downstream offline optimization problem (e.\,g., the cost of an optimal dispatch for service technicians). We provide general competitive algorithms for the \textsc{OnlineTDAP} independently of the particular downstream problem, when the overall objective is to minimize either the sum or the maximum of all downstream costs. As the first basic examples, we analyze the competitive ratios of our algorithms for the par ticular academic downstream problems of bin-packing, nonpreemptive scheduling on identical parallel machines, and routing a traveling salesman.}, language = {en} } @misc{Heinz, type = {Master Thesis}, author = {Heinz, Stefan}, title = {Policies for Online Target Date Assignment Problems: Competitive Analysis versus Expected Performance}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9933}, school = {Zuse Institute Berlin (ZIB)}, language = {en} } @misc{HarksHeinzPfetschetal., author = {Harks, Tobias and Heinz, Stefan and Pfetsch, Marc and Vredeveld, Tjark}, title = {Online Multicommodity Routing with Time Windows}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9654}, number = {07-22}, abstract = {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.}, language = {en} } @misc{KochAchterbergAndersenetal.2010, author = {Koch, Thorsten and Achterberg, Tobias and Andersen, Erling and Bastert, Oliver and Berthold, Timo and Bixby, Robert E. and Danna, Emilie and Gamrath, Gerald and Gleixner, Ambros and Heinz, Stefan and Lodi, Andrea and Mittelmann, Hans and Ralphs, Ted and Salvagnin, Domenico and Steffy, Daniel and Wolter, Kati}, title = {MIPLIB 2010}, doi = {10.1007/s12532-011-0025-9}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12953}, number = {10-31}, year = {2010}, abstract = {This paper reports on the fifth version of the Mixed Integer Programming Library. The MIPLIB 2010 is the first MIPLIB release that has been assembled by a large group from academia and from industry, all of whom work in integer programming. There was mutual consent that the concept of the library had to be expanded in order to fulfill the needs of the community. The new version comprises 361 instances sorted into several groups. This includes the main benchmark test set of 87 instances, which are all solvable by today's codes, and also the challenge test set with 164 instances, many of which are currently unsolved. For the first time, we include scripts to run automated tests in a predefined way. Further, there is a solution checker to test the accuracy of provided solutions using exact arithmetic.}, language = {en} } @misc{BertholdHeinzPfetschetal., author = {Berthold, Timo and Heinz, Stefan and Pfetsch, Marc and Vigerske, Stefan}, title = {Large Neighborhood Search beyond MIP}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12989}, number = {11-21}, abstract = {Large neighborhood search (LNS) heuristics are an important component of modern branch-and-cut algorithms for solving mixed-integer linear programs (MIPs). Most of these LNS heuristics use the LP relaxation as the basis for their search, which is a reasonable choice in case of MIPs. However, for more general problem classes, the LP relaxation alone may not contain enough information about the original problem to find feasible solutions with these heuristics, e.g., if the problem is nonlinear or not all constraints are present in the current relaxation. In this paper, we discuss a generic way to extend LNS heuristics that have been developed for MIP to constraint integer programming (CIP), which is a generalization of MIP in the direction of constraint programming (CP). We present computational results of LNS heuristics for three problem classes: mixed-integer quadratically constrained programs, nonlinear pseudo-Boolean optimization instances, and resource-constrained project scheduling problems. Therefore, we have implemented extended versions of the following LNS heuristics in the constraint integer programming framework SCIP: Local Branching, RINS, RENS, Crossover, and DINS. Our results indicate that a generic generalization of LNS heuristics to CIP considerably improves the success rate of these heuristics.}, language = {en} } @misc{ShinanoAchterbergBertholdetal., author = {Shinano, Yuji and Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten}, title = {ParaSCIP - a parallel extension of SCIP}, doi = {10.1007/978-3-642-24025-6_12}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11921}, number = {10-27}, abstract = {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.}, language = {en} } @misc{BertholdHeinzSchulz, author = {Berthold, Timo and Heinz, Stefan and Schulz, Jens}, title = {An approximative Criterion for the Potential of Energetic Reasoning}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12655}, number = {11-12}, abstract = {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.}, language = {en} } @misc{HeinzSchulz, author = {Heinz, Stefan and Schulz, Jens}, title = {Explanations for the Cumulative Constraint: an Experimental Study}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12668}, number = {11-13}, abstract = {In cumulative scheduling, conflict analysis seems to be one of the key ingredients to solve such problems efficiently. Thereby, the computational complexity of explanation algorithms plays an important role. Even more when we are faced with a backtracking system where explanations need to be constructed on the fly. In this paper we present extensive computational results to analyze the impact of explanation algorithms for the cumulative constraint in a backward checking system. The considered explanation algorithms differ in their quality and computational complexity. We present results for the domain propagation algorithms time-tabling, edge-finding, and energetic reasoning.}, language = {en} } @misc{HeinzBeck, author = {Heinz, Stefan and Beck, J. Christopher}, title = {Solving Resource Allocation/Scheduling Problems with Constraint Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12691}, number = {11-14}, abstract = {Constraint Integer Programming (CIP) is a generalization of mixed-integer programming (MIP) in the direction of constraint programming (CP) allowing the inference techniques that have traditionally been the core of \P to be integrated with the problem solving techniques that form the core of complete MIP solvers. In this paper, we investigate the application of CIP to scheduling problems that require resource and start-time assignments to satisfy resource capacities. The best current approach to such problems is logic-based Benders decomposition, a manual decomposition method. We present a CIP model and demonstrate that it achieves performance competitive to the decomposition while out-performing the standard MIP and CP formulations.}, language = {en} } @misc{HeinzBeck, author = {Heinz, Stefan and Beck, J. Christopher}, title = {Reconsidering Mixed Integer Programming and MIP-based Hybrids for Scheduling}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14660}, number = {12-05}, abstract = {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.}, language = {en} }