TY - GEN A1 - Rehfeldt, Daniel A1 - Koch, Thorsten T1 - Generalized preprocessing techniques for Steiner tree and maximum-weight connected subgraph problems N2 - This article introduces new preprocessing techniques for the Steiner tree problem in graphs and one of its most popular relatives, the maximum-weight connected subgraph problem. Several of the techniques generalize previous results from the literature. The correctness of the new methods is shown, but also their NP-hardness is demonstrated. Despite this pessimistic worst-case complexity, several relaxations are discussed that are expected to allow for a strong practical efficiency of these techniques in strengthening both exact and heuristic solving approaches. T3 - ZIB-Report - 17-57 KW - Steiner tree KW - maximum-weight connected subgraph Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-65439 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Perregaard, Michael A1 - Mészáros, Csaba T1 - Four good reasons to use an Interior Point solver within a MIP solver N2 - "Interior point algorithms are a good choice for solving pure LPs or QPs, but when you solve MIPs, all you need is a dual simplex." This is the common conception which disregards that an interior point solution provides some unique structural insight into the problem at hand. In this paper, we will discuss some of the benefits that an interior point solver brings to the solution of difficult MIPs within FICO Xpress. This includes many different components of the MIP solver such as branching variable selection, primal heuristics, preprocessing, and of course the solution of the LP relaxation. T3 - ZIB-Report - 17-42 KW - mixed integer programming KW - interior point algorithm KW - Newton barrier method KW - analytic center Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64599 SN - 1438-0064 ER - TY - GEN A1 - Miltenberger, Matthias A1 - Ralphs, Ted A1 - Steffy, Daniel T1 - Exploring the Numerics of Branch-and-Cut for Mixed Integer Linear Optimization T2 - Operations Research Proceedings 2017 N2 - We investigate how the numerical properties of the LP relaxations evolve throughout the solution procedure in a solver employing the branch-and-cut algorithm. The long-term goal of this work is to determine whether the effect on the numerical conditioning of the LP relaxations resulting from the branching and cutting operations can be effectively predicted and whether such predictions can be used to make better algorithmic choices. In a first step towards this goal, we discuss here the numerical behavior of an existing solver in order to determine whether our intuitive understanding of this behavior is correct. T3 - ZIB-Report - 17-43 KW - Mixed Integer Programming KW - Linear Programming KW - Algorithm Analysis Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64645 SN - 1438-0064 ER - TY - GEN A1 - Schade, Stanley A1 - Schlechte, Thomas A1 - Witzig, Jakob T1 - Structure-based Decomposition for Pattern-Detection for Railway Timetables N2 - We consider the problem of pattern detection in large scale railway timetables. This problem arises in rolling stock optimization planning in order to identify invariant sections of the timetable for which a cyclic rotation plan is adequate. We propose a dual reduction technique which leads to an decomposition and enumeration method. Computational results for real world instances demonstrate that the method is able to produce optimal solutions as fast as standard MIP solvers. T3 - ZIB-Report - 17-40 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64525 SN - 1438-0064 ER - TY - CHAP A1 - Miltenberger, Matthias A1 - Ralphs, Ted A1 - Steffy, Daniel T1 - Exploring the Numerics of Branch-and-Cut for Mixed Integer Linear Optimization T2 - Operations Research Proceedings 2017 N2 - We investigate how the numerical properties of the LP relaxations evolve throughout the solution procedure in a solver employing the branch-and-cut algorithm. The long-term goal of this work is to determine whether the effect on the numerical conditioning of the LP relaxations resulting from the branching and cutting operations can be effectively predicted and whether such predictions can be used to make better algorithmic choices. In a first step towards this goal, we discuss here the numerical behavior of an existing solver in order to determine whether our intuitive understanding of this behavior is correct. Y1 - 2018 U6 - https://doi.org/10.1007/978-3-319-89920-6 SP - 151 EP - 157 PB - Springer International Publishing ER - TY - CHAP A1 - Yokoyama, Ryohei A1 - Shinano, Yuji A1 - Taniguchi, Syusuke A1 - Ohkura, Masashi A1 - Wakui, Tetsuya T1 - Generation of multiple best solutions in multiobjective optimal design of energy supply systems T2 - Proceedings of the 15th International Conference on Power Engineering. ICOPE 2015 N2 - Optimization approaches based on the mixed-integer linear programming (MILP) have been utilized to design energy supply systems. In this paper, an MILP method utilizing the hierarchical relationship between design and operation is extended to search not only the optimal solution but also suboptimal ones which follow the optimal one without any omissions, what are called K-best solutions, efficiently in a multiobjective optimal design problem. At the upper level, the values of design variables for the K-best solutions 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. Incumbents for the K-best solutions and an upper bound for all the values of the objective function for the K-best solutions are renewed if necessary between both the levels. This method is implemented into a commercial MILP solver. A practical case study on the multiobjective optimal design of a cogeneration system is conducted, and the validity and effectiveness of the method are clarified. Y1 - 2015 U6 - https://doi.org/10.1299/jsmeicope.2015.12._ICOPE-15-_56 ER - TY - JOUR A1 - Gleixner, Ambros A1 - Steffy, Daniel A1 - Wolter, Kati T1 - Iterative Refinement for Linear Programming JF - INFORMS Journal on Computing N2 - We describe an iterative refinement procedure for computing extended precision or exact solutions to linear programming problems (LPs). Arbitrarily precise solutions can be computed by solving a sequence of closely related LPs with limited precision arithmetic. The LPs solved share the same constraint matrix as the original problem instance and are transformed only by modification of the objective function, right-hand side, and variable bounds. Exact computation is used to compute and store the exact representation of the transformed problems, while numeric computation is used for solving LPs. At all steps of the algorithm the LP bases encountered in the transformed problems correspond directly to LP bases in the original problem description. We show that this algorithm is effective in practice for computing extended precision solutions and that it leads to a direct improvement of the best known methods for solving LPs exactly over the rational numbers. Our implementation is publically available as an extension of the academic LP solver SoPlex. Y1 - 2016 U6 - https://doi.org/10.1287/ijoc.2016.0692 VL - 28 IS - 3 SP - 449 EP - 464 ER - TY - CHAP A1 - Hendel, Gregor T1 - Exploiting Solving Phases for Mixed-Integer Programs T2 - Operations Research Proceedings 2015 N2 - 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. Y1 - 2016 U6 - https://doi.org/10.1007/978-3-319-42902-1_1 SP - 3 EP - 9 ER - TY - CHAP A1 - Shinano, Yuji A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Koch, Thorsten A1 - Winkler, Michael T1 - Solving Open MIP Instances with ParaSCIP on Supercomputers using up to 80,000 Cores T2 - Proc. of 30th IEEE International Parallel & Distributed Processing Symposium N2 - 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. Y1 - 2016 U6 - https://doi.org/10.1109/IPDPS.2016.56 ER - TY - GEN A1 - Witzig, Jakob T1 - Conflict Driven Diving for Mixed Integer Programming N2 - The analysis of infeasibility plays an important role in solving satisfiability problems (SAT) and mixed integer programs (MIPs). In mixed integer programming, this procedure is called conflict analysis. So far, modern MIP solvers use conflict analysis only for propagation and improving the dual bound, i.e., fathoming nodes that cannot contain feasible solutions. In this short paper, we present a new approach which uses conflict information to improve the primal bound during a MIP solve. To derive new improving primal solutions we use a conflict driven diving heuristic called conflict diving that uses the information obtained by conflict analysis. Conflict diving pursues a twofold strategy. By using conflict information the new diving approach is guided into parts of the search space that are usually not explored by other diving heuristics. At the same time, conflict diving has a fail-fast-strategy to reduce the time spent if it cannot find a new primal solution. As a byproduct, additional valid conflict constraints can be derived, from which a MIP solver can gain benefit to improve the dual bound as well. To show the added-value of conflict diving within a MIP solver, conflict diving has been implemented within the non-commercial MIP solver SCIP. Experiments are carried out on general MIP instances from standard public test sets, like MIPLIB2010 or Cor@l. T3 - ZIB-Report - 17-69 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-66116 SN - 1438-0064 ER - TY - GEN A1 - Achterberg, Tobias A1 - Bixby, Robert E. A1 - Gu, Zonghao A1 - Rothberg, Edward A1 - Weninger, Dieter T1 - Presolve Reductions in Mixed Integer Programming N2 - Mixed integer programming has become a very powerful tool for modeling and solving real-world planning and scheduling problems, with the breadth of applications appearing to be almost unlimited. A critical component in the solution of these mixed-integer programs is a set of routines commonly referred to as presolve. Presolve can be viewed as a collection of preprocessing techniques that reduce the size of and, more importantly, improve the ``strength'' of the given model formulation, that is, the degree to which the constraints of the formulation accurately describe the underlying polyhedron of integer-feasible solutions. As our computational results will show, presolve is a key factor in the speed with which we can solve mixed-integer programs, and is often the difference between a model being intractable and solvable, in some cases easily solvable. In this paper we describe the presolve functionality in the Gurobi commercial mixed-integer programming code. This includes an overview, or taxonomy of the different methods that are employed, as well as more-detailed descriptions of several of the techniques, with some of them appearing, to our knowledge, for the first time in the literature. T3 - ZIB-Report - 16-44 KW - integer programming KW - presolving KW - Gurobi Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60370 SN - 1438-0064 ER - TY - GEN A1 - Rehfeldt, Daniel A1 - Koch, Thorsten A1 - Maher, Stephen J. T1 - Reduction Techniques for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem N2 - The concept of reduction has frequently distinguished itself as a pivotal ingredient of exact solving approaches for the Steiner tree problem in graphs. In this paper we broaden the focus and consider reduction techniques for three Steiner problem variants that have been extensively discussed in the literature and entail various practical applications: The prize-collecting Steiner tree problem, the rooted prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem. By introducing and subsequently deploying numerous new reduction methods, we are able to drastically decrease the size of a large number of benchmark instances, already solving more than 90 percent of them to optimality. Furthermore, we demonstrate the impact of these techniques on exact solving, using the example of the state-of-the-art Steiner problem solver SCIP-Jack. T3 - ZIB-Report - 16-47 KW - Steiner tree problems KW - reduction techniques KW - prize-collecting Steiner tree problem KW - maximum-weight connected subgraph problem Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60420 SN - 1438-0064 ER -