@inproceedings{HeinzBeck2012, author = {Heinz, Stefan and Beck, J. Christopher}, title = {Reconsidering Mixed Integer Programming and MIP-based Hybrids for Scheduling}, volume = {7298}, booktitle = {Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2012)}, pages = {211 -- 227}, year = {2012}, language = {en} } @inproceedings{BertholdHeinzSchulz2011, author = {Berthold, Timo and Heinz, Stefan and Schulz, Jens}, title = {An approximative Criterion for the Potential of Energetic Reasoning}, volume = {6595}, booktitle = {Theory and Practice of Algorithms in (Computer) Systems}, pages = {229 -- 239}, year = {2011}, language = {en} } @article{HeinzSchlechteStephanetal.2012, author = {Heinz, Stefan and Schlechte, Thomas and Stephan, R{\"u}diger and Winkler, Michael}, title = {Solving steel mill slab design problems}, volume = {17}, journal = {Constraints}, number = {1}, doi = {10.1007/s10601-011-9113-8}, pages = {39 -- 50}, year = {2012}, abstract = {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.}, language = {en} } @misc{ShinanoAchterbergBertholdetal.2013, author = {Shinano, Yuji and Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten and Winkler, Michael}, title = {Solving hard MIPLIB2003 problems with ParaSCIP on Supercomputers: An update}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42888}, year = {2013}, abstract = {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.}, language = {en} } @inproceedings{HeinzKrumkeMegowetal.2006, 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}, volume = {3879}, booktitle = {Proc. 3rd Workshop on Approximation and Online Algorithms}, editor = {Erlebach, Thomas and Persiano, Giuseppe}, publisher = {Springer}, pages = {230 -- 243}, year = {2006}, language = {en} } @article{HeinzKaibelPeinhardtetal.2006, author = {Heinz, Stefan and Kaibel, Volker and Peinhardt, Matthias and Rambau, J{\"o}rg and Tuchscherer, Andreas}, title = {LP-Based Local Approximation for Markov Decision Problems}, number = {343}, publisher = {Matheon}, year = {2006}, language = {en} } @inproceedings{ShinanoAchterbergBertholdetal.2012, author = {Shinano, Yuji and Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten}, title = {ParaSCIP: a parallel extension of SCIP}, booktitle = {Competence in High Performance Computing 2010}, editor = {Bischof, Christian and Hegering, Heinz-Gerd and Nagel, Wolfgang and Wittum, Gabriel}, publisher = {Springer}, doi = {10.1007/978-3-642-24025-6_12}, pages = {135 -- 148}, year = {2012}, language = {en} } @misc{HeinzKuBeck2013, author = {Heinz, Stefan and Ku, Wen-Yang and Beck, J. Christopher}, title = {Recent improvements using constraint integer programming for resource allocation and scheduling}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17676}, year = {2013}, abstract = {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.}, language = {en} } @misc{HeinzBeck2011, 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}, year = {2011}, 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{HeinzSchulz2011, 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}, year = {2011}, 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} } @inproceedings{ShinanoBertholdHeinz2016, author = {Shinano, Yuji and Berthold, Timo and Heinz, Stefan}, title = {A First Implementation of ParaXpress: Combining Internal and External Parallelization to Solve MIPs on Supercomputers}, booktitle = {Mathematical Software - ICMS 2016, 5th International Conference Berlin, Germany, July 11-14, 2016 Proceedings}, doi = {10.1007/978-3-319-42432-3_38}, pages = {308 -- 316}, year = {2016}, language = {en} } @inproceedings{BertholdFarmerHeinzetal.2016, author = {Berthold, Timo and Farmer, James and Heinz, Stefan and Perregaard, Michael}, title = {Parallelization of the FICO Xpress-Optimizer}, booktitle = {Mathematical Software - ICMS 2016, 5th International Conference Berlin, Germany, July 11-14, 2016 Proceedings}, doi = {10.1007/978-3-319-42432-3_31}, pages = {251 -- 258}, year = {2016}, language = {en} } @article{ShinanoBertholdHeinz2018, author = {Shinano, Yuji and Berthold, Timo and Heinz, Stefan}, title = {ParaXpress: An Experimental Extension of the FICO Xpress-Optimizer to Solve Hard MIPs on Supercomputers}, volume = {33}, journal = {Optimization Methods \& Software}, number = {3}, doi = {10.1080/10556788.2018.1428602}, pages = {530 -- 539}, year = {2018}, abstract = {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.}, language = {en} } @misc{BertholdGleixnerHeinzetal.2012, author = {Berthold, Timo and Gleixner, Ambros and Heinz, Stefan and Koch, Thorsten and Shinano, Yuji}, title = {SCIP Optimization Suite を利用した 混合整数(線形/非線形) 計画問題の解法}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-15598}, year = {2012}, abstract = {この論文ではソフトウェア・パッケージ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 の利用方法を示すとともに,利用可能なインタフェースの概要を示す.最後に,将来の開 発計画の概要について述べる.}, language = {ja} } @misc{HeinzSachenbacher2008, 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}, year = {2008}, 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{BertholdHeinzPfetsch2008, 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}, year = {2008}, 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{AchterbergHeinzKoch2008, 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}, year = {2008}, 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{Heinz2005, 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)}, year = {2005}, language = {en} } @inproceedings{ShinanoAchterbergBertholdetal.2016, author = {Shinano, Yuji and Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten and Winkler, Michael}, title = {Solving Open MIP Instances with ParaSCIP on Supercomputers using up to 80,000 Cores}, booktitle = {Proc. of 30th IEEE International Parallel \& Distributed Processing Symposium}, doi = {10.1109/IPDPS.2016.56}, year = {2016}, abstract = {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.}, language = {en} } @misc{HarksHeinzPfetschetal.2007, 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}, year = {2007}, 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} }