@misc{AchterbergBertholdHendel, author = {Achterberg, Tobias and Berthold, Timo and Hendel, Gregor}, title = {Rounding and Propagation Heuristics for Mixed Integer Programming}, doi = {10.1007/978-3-642-29210-1_12}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-13255}, number = {11-29}, abstract = {Primal heuristics are an important component of state-of-the-art codes for mixed integer programming. In this paper, we focus on primal heuristics that only employ computationally inexpensive procedures such as rounding and logical deductions (propagation). We give an overview of eight different approaches. To assess the impact of these primal heuristics on the ability to find feasible solutions, in particular early during search, we introduce a new performance measure, the primal integral. Computational experiments evaluate this and other measures on MIPLIB~2010 benchmark instances.}, language = {en} } @misc{BertholdHendel, author = {Berthold, Timo and Hendel, Gregor}, title = {Shift-And-Propagate}, issn = {1438-0064}, doi = {10.1007/s10732-014-9271-0}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17596}, abstract = {For mixed integer programming, recent years have seen a growing interest in the design of general purpose primal heuristics for use inside complete solvers. Many of these heuristics rely on an optimal LP solution. Finding this may itself take a significant amount of time. The presented paper addresses this issue by the introduction of the Shift-And-Propagate heuristic. Shift-And-Propagate is a pre-root primal heuristic that does not require a previously found LP solution. It applies domain propagation techniques to quickly drive a variable assignment towards feasibility. Computational experiments indicate that this heuristic is a powerful supplement of existing rounding and propagation heuristics.}, language = {en} } @misc{ShinanoHeinzVigerskeetal., author = {Shinano, Yuji and Heinz, Stefan and Vigerske, Stefan and Winkler, Michael}, title = {FiberSCIP - A shared memory parallelization of SCIP}, issn = {1438-0064}, doi = {10.1287/ijoc.2017.0762}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42595}, abstract = {Recently, parallel computing environments have become significantly popular. In order to obtain the benefit of using parallel computing environments, we have to deploy our programs for these effectively. This paper focuses on a parallelization of SCIP (Solving Constraint Integer Programs), which is a MIP solver and constraint integer programming framework available in source code. There is a parallel extension of SCIP named ParaSCIP, which parallelizes SCIP on massively parallel distributed memory computing environments. This paper describes FiberSCIP, which is yet another parallel extension of SCIP to utilize multi-threaded parallel computation on shared memory computing environments, and has the following contributions: First, the basic concept of having two parallel extensions and the relationship between them and the parallelization framework provided by UG (Ubiquity Generator) is presented, including an implementation of deterministic parallelization. Second, the difficulties to achieve a good performance that utilizes all resources on an actual computing environment and the difficulties of performance evaluation of the parallel solvers are discussed. Third, a way to evaluate the performance of new algorithms and parameter settings of the parallel extensions is presented. Finally, current performance of FiberSCIP for solving mixed-integer linear programs (MIPs) and mixed-integer non-linear programs (MINLPs) in parallel is demonstrated.}, language = {en} } @misc{GamrathKochMartinetal., author = {Gamrath, Gerald and Koch, Thorsten and Martin, Alexander and Miltenberger, Matthias and Weninger, Dieter}, title = {Progress in Presolving for Mixed Integer Programming}, issn = {1438-0064}, doi = {10.1007/s12532-015-0083-5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42530}, abstract = {Presolving attempts to eliminate redundant information from the problem formulation and simultaneously tries to strengthen the formulation. It can be very effective and is often essential for solving instances. Especially for mixed integer programming problems, fast and effective presolving algorithms are very important. In this paper, we report on three new presolving techniques. The first method searches for singleton continuous columns and tries to fix the corresponding variables. Then we present a presolving technique which exploits a partial order of the variables to induce fixings. Finally, we show an approach based on connected components in graphs. Our computational results confirm the profitable use of the algorithms in practice.}, language = {en} } @misc{Gamrath, author = {Gamrath, Gerald}, title = {Improving strong branching by domain propagation}, issn = {1438-0064}, doi = {10.1007/s13675-014-0021-8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42546}, abstract = {One of the essential components of a branch-and-bound based mixed-integer linear programming (MIP) solver is the branching rule. Strong branching is a method used by many state-of-the-art branching rules to select the variable to branch on. It precomputes the dual bounds of potential child nodes by solving auxiliary linear programs (LPs) and thereby helps to take good branching decisions that lead to a small search tree. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Domain propagation is a technique usually used at every node of the branch-and-bound tree to tighten the local domains of variables. Computational experiments on standard MIP instances indicate that our improved strong branching method significantly improves the quality of the predictions and causes almost no additional effort. For a full strong branching rule, we are able to obtain substantial reductions of the branch-and-bound tree size as well as the solving time. Moreover, also the state-of-the-art hybrid branching rule can be improved this way. This paper extends previous work by the author published in the proceedings of the CPAIOR 2013.}, language = {en} } @misc{BallersteinMichaelsVigerske, author = {Ballerstein, Martin and Michaels, Dennis and Vigerske, Stefan}, title = {Linear Underestimators for bivariate functions with a fixed convexity behavior}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17641}, abstract = {This is a technical report for the SCIP constraint handler cons_bivariate. We describe a cut-generation algorithm for a class of bivariate twice continuously differentiable functions with fixed convexity behavior over a box. Computational results comparing our cut-generation algorithms with state-of-the-art global optimization software on a series of randomly generated test instances are reported and discussed.}, language = {en} } @misc{YokoyamaShinanoTaniguchietal.2014, author = {Yokoyama, Ryohei and Shinano, Yuji and Taniguchi, Syusuke and Ohkura, Masashi and Wakui, Tetsuya}, title = {Optimization of energy supply systems by MILP branch and bound method in consideration of hierarchical relationship between design and operation}, issn = {1438-0064}, doi = {10.1016/j.enconman.2014.12.020}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-49413}, year = {2014}, abstract = {To attain the highest performance of energy supply systems, it is necessary to rationally determine types, capacities, and numbers of equipment in consideration of their operational strategies corresponding to seasonal and hourly variations in energy demands. In the combinatorial optimization method based on the mixed-integer linear programming (MILP), integer variables are used to express the selection, numbers, and on/off status of operation of equipment, and the number of these variables increases with those of equipment and periods for variations in energy demands, and affects the computation efficiency significantly. In this paper, a MILP method utilizing the hierarchical relationship between design and operation variables is proposed to solve the optimal design problem of energy supply systems efficiently: At the upper level, the optimal values of design variables are searched by the branch and bound method; At the lower level, the values of operation variables are optimized independently at each period by the branch and bound method under the values of design variables given tentatively during the search at the upper level; Lower bounds for the optimal value of the objective function are evaluated, and are utilized for the bounding operations at both the levels. This method is implemented into open and commercial MILP solvers. Illustrative and practical case studies on the optimal design of cogeneration systems are conducted, and the validity and effectiveness of the proposed method are clarified.}, language = {en} } @misc{GamrathKochRehfeldtetal., author = {Gamrath, Gerald and Koch, Thorsten and Rehfeldt, Daniel and Shinano, Yuji}, title = {SCIP-Jack - A massively parallel STP solver}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-52293}, abstract = {In this article we describe the impact from embedding a 15 year old model for solving the Steiner tree problem in graphs in a state-of-the-art MIP-Framework, making the result run in a massively parallel environment and extending the model to solve as many variants as possible. We end up with a high-perfomance solver that is capable of solving previously unsolved instances and, in contrast to its predecessor, is freely available for academic research.}, language = {en} } @misc{GamrathMelchioriBertholdetal., author = {Gamrath, Gerald and Melchiori, Anna and Berthold, Timo and Gleixner, Ambros and Salvagnin, Domenico}, title = {Branching on multi-aggregated variables}, issn = {1438-0064}, doi = {10.1007/978-3-319-18008-3_10}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-53829}, abstract = {In mixed-integer programming, the branching rule is a key component to a fast convergence of the branch-and-bound algorithm. The most common strategy is to branch on simple disjunctions that split the domain of a single integer variable into two disjoint intervals. Multi-aggregation is a presolving step that replaces variables by an affine linear sum of other variables, thereby reducing the problem size. While this simplification typically improves the performance of MIP solvers, it also restricts the degree of freedom in variable-based branching rules. We present a novel branching scheme that tries to overcome the above drawback by considering general disjunctions defined by multi-aggregated variables in addition to the standard disjunctions based on single variables. This natural idea results in a hybrid between variable- and constraint-based branching rules. Our implementation within the constraint integer programming framework SCIP incorporates this into a full strong branching rule and reduces the number of branch-and-bound nodes on a general test set of publicly available benchmark instances. For a specific class of problems, we show that the solving time decreases significantly.}, language = {en} } @misc{Hendel, author = {Hendel, Gregor}, title = {Exploiting Solving Phases for Mixed-Integer Programs}, issn = {1438-0064}, doi = {10.1007/978-3-319-42902-1_1}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-57098}, abstract = {Modern MIP solving software incorporates dozens of auxiliary algorithmic components for supporting the branch-and-bound search in finding and improving solutions and in strengthening the relaxation. Intuitively, a dynamic solving strategy with an appropriate emphasis on different solving components and strategies is desirable during the search process. We propose an adaptive solver behavior that dynamically reacts on transitions between the three typical phases of a MIP solving process: The first phase objective is to find a feasible solution. During the second phase, a sequence of incumbent solutions gets constructed until the incumbent is eventually optimal. Proving optimality is the central objective of the remaining third phase. Based on the MIP-solver SCIP, we demonstrate the usefulness of the phase concept both with an exact recognition of the optimality of a solution, and provide heuristic alternatives to make use of the concept in practice.}, language = {en} }