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 - 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 - GEN A1 - Shinano, Yuji A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Koch, Thorsten A1 - Winkler, Michael T1 - Solving hard MIPLIB2003 problems with ParaSCIP on Supercomputers: An update N2 - Contemporary supercomputers can easily provide years of CPU time per wall-clock hour. One challenge of today's software development is how to harness this wast computing power in order to solve really hard mixed integer programming instances. In 2010, two out of six open MIPLIB2003 instances could be solved by ParaSCIP in more than ten consecutive runs, restarting from checkpointing files. The contribution of this paper is threefold: For the first time, we present computational results of single runs for those two instances. Secondly, we provide new improved upper and lower bounds for all of the remaining four open MIPLIB2003 instances. Finally, we explain which new developments led to these results and discuss the current progress of ParaSCIP. Experiments were conducted on HLRNII, on HLRN III, and on the Titan supercomputer, using up to 35,200 cores. T3 - ZIB-Report - 13-66 KW - Mixed Integer Programming KW - MIPLIB2003 KW - ParaSCIP KW - Ubiquity Generator Framework KW - Supercomputer Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42888 SN - 1438-0064 ER - TY - CHAP A1 - Heinz, Stefan A1 - Krumke, Sven A1 - Megow, Nicole A1 - Rambau, Jörg A1 - Tuchscherer, Andreas A1 - Vredeveld, Tjark ED - Erlebach, Thomas ED - Persiano, Giuseppe T1 - The Online Target Date Assignment Problem T2 - Proc. 3rd Workshop on Approximation and Online Algorithms Y1 - 2006 UR - http://opus.kobv.de/zib/volltexte/2005/894/ VL - 3879 SP - 230 EP - 243 PB - Springer ER - TY - JOUR A1 - Heinz, Stefan A1 - Kaibel, Volker A1 - Peinhardt, Matthias A1 - Rambau, Jörg A1 - Tuchscherer, Andreas T1 - LP-Based Local Approximation for Markov Decision Problems Y1 - 2006 IS - 343 PB - Matheon ER - TY - CHAP A1 - Shinano, Yuji A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Koch, Thorsten ED - Bischof, Christian ED - Hegering, Heinz-Gerd ED - Nagel, Wolfgang ED - Wittum, Gabriel T1 - ParaSCIP: a parallel extension of SCIP T2 - Competence in High Performance Computing 2010 Y1 - 2012 U6 - https://doi.org/10.1007/978-3-642-24025-6_12 SP - 135 EP - 148 PB - Springer ER - TY - GEN A1 - Heinz, Stefan A1 - Ku, Wen-Yang A1 - Beck, J. Christopher T1 - Recent improvements using constraint integer programming for resource allocation and scheduling N2 - Recently, we compared the performance of mixed-integer programming (MIP), constraint programming (CP), and constraint integer programming (CIP) to a state-of-the-art logic-based Benders manual decomposition (LBBD) for a resource allocation/scheduling problem. For a simple linear relaxation, the LBBD and CIP models deliver comparable performance with MIP also performing well. Here we show that algorithmic developments in CIP plus the use of an existing tighter relaxation substantially improve one of the CIP approaches. Furthermore, the use of the same relaxation in LBBD and MIP models significantly improves their performance. While such a result is known for LBBD, to the best of our knowledge, the other results are novel. Our experiments show that both CIP and MIP approaches are competitive with LBBD in terms of the number of problems solved to proven optimality, though MIP is about three times slower on average. Further, unlike the LBBD and CIP approaches, the MIP model is able to obtain provably high-quality solutions for all problem instances. T3 - ZIB-Report - 13-05 KW - constraint integer programming KW - constraint programming KW - cumulative constraint KW - mixed integer programming KW - optional activities Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17676 SN - 1438-0064 ER - TY - GEN A1 - Heinz, Stefan A1 - Beck, J. Christopher T1 - Solving Resource Allocation/Scheduling Problems with Constraint Integer Programming N2 - 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. T3 - ZIB-Report - 11-14 KW - constraint integer programming KW - cumulative constraint KW - optional resources KW - mixed integer programming KW - constraint programming Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-12691 ER - TY - GEN A1 - Heinz, Stefan A1 - Schulz, Jens T1 - Explanations for the Cumulative Constraint: an Experimental Study N2 - 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. T3 - ZIB-Report - 11-13 KW - conflict analysis KW - constraint integer programming KW - cumulative constraint KW - resource-constrained project scheduling KW - propagation algorithms Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-12668 ER - TY - CHAP A1 - Shinano, Yuji A1 - Berthold, Timo A1 - Heinz, Stefan T1 - A First Implementation of ParaXpress: Combining Internal and External Parallelization to Solve MIPs on Supercomputers T2 - Mathematical Software - ICMS 2016, 5th International Conference Berlin, Germany, July 11-14, 2016 Proceedings Y1 - 2016 U6 - https://doi.org/10.1007/978-3-319-42432-3_38 SP - 308 EP - 316 ER - TY - CHAP A1 - Berthold, Timo A1 - Farmer, James A1 - Heinz, Stefan A1 - Perregaard, Michael T1 - Parallelization of the FICO Xpress-Optimizer T2 - Mathematical Software - ICMS 2016, 5th International Conference Berlin, Germany, July 11-14, 2016 Proceedings Y1 - 2016 U6 - https://doi.org/10.1007/978-3-319-42432-3_31 SP - 251 EP - 258 ER - TY - JOUR A1 - Shinano, Yuji A1 - Berthold, Timo A1 - Heinz, Stefan T1 - ParaXpress: An Experimental Extension of the FICO Xpress-Optimizer to Solve Hard MIPs on Supercomputers JF - Optimization Methods & Software N2 - The Ubiquity Generator (UG) is a general framework for the external parallelization of mixed integer programming (MIP) solvers. In this paper, we present ParaXpress, a distributed memory parallelization of the powerful commercial MIP solver FICO Xpress. Besides sheer performance, an important feature of Xpress is that it provides an internal parallelization for shared memory systems. When aiming for a best possible performance of ParaXpress on a supercomputer, the question arises how to balance the internal Xpress parallelization and the external parallelization by UG against each other. We provide computational experiments to address this question and we show computational results for running ParaXpress on a Top500 supercomputer, using up to 43,344 cores in parallel. Y1 - 2018 U6 - https://doi.org/10.1080/10556788.2018.1428602 VL - 33 IS - 3 SP - 530 EP - 539 ER - TY - GEN A1 - Berthold, Timo A1 - Gleixner, Ambros A1 - Heinz, Stefan A1 - Koch, Thorsten A1 - Shinano, Yuji T1 - SCIP Optimization Suite を利用した 混合整数(線形/非線形) 計画問題の解法 T1 - Solving mixed integer linear and nonlinear problems using the SCIP Optimization Suite 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. T3 - ZIB-Report - 12-24 KW - SCIP, MIP, MINLP, CIP, LP, modeling, optimization Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15598 SN - 1438-0064 ER -