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 - 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 - Berthold, Timo A1 - Heinz, Stefan A1 - Pfetsch, Marc T1 - Solving Pseudo-Boolean Problems with SCIP N2 - 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. T3 - ZIB-Report - 08-12 KW - Pseudo-Boolean KW - Constraint Programming KW - Ganzzahlige Programmierung KW - Branch-And-Cut KW - Optimierungssoftware KW - Pseudo-Boolean KW - constraint integer programming KW - integer programming KW - branch-and-cut KW - optimization software Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10671 SN - 1438-0064 ER - TY - GEN A1 - Heinz, Stefan A1 - Schlechte, Thomas A1 - Stephan, Rüdiger A1 - Winkler, Michael T1 - Solving steel mill slab design problems 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. The aim of this paper is to bring these different studies together. Moreover, we adapt the model of Forrest et al. 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. 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. T3 - ZIB-Report - 11-38 KW - steel mill slab design problem KW - multiple knapsack problem with color constraints KW - integer programming KW - set partitioning KW - binpacking with side constraints Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14089 SN - 1438-0064 ER -