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 - TY - GEN A1 - Pulaj, Jonad T1 - Cutting Planes for Families Implying Frankl's Conjecture N2 - We find previously unknown families which imply Frankl’s conjecture using an algorithmic framework. The conjecture states that for any non-empty union-closed (or Frankl) family there exists an element in at least half of the sets. Poonen’s Theorem characterizes the existence of weights which determine whether a given Frankl family implies the conjecture for all Frankl families which contain it. A Frankl family is Non–Frankl-Complete (Non–FC), if it does not imply the conjecture in its elements for some Frankl family that contains it. We design a cutting-plane method that computes the explicit weights which imply the existence conditions of Poonen’s Theorem. This method allows us to find a counterexample to a ten-year-old conjecture by R. Morris about the structure of generators for Non–FC-families. T3 - ZIB-Report - 16-51 KW - extremal combinatorics, extremal set theory, cutting plane, exact integer programming Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60626 SN - 1438-0064 ER - TY - GEN A1 - Witzig, Jakob A1 - Beckenbach, Isabel A1 - Eifler, Leon A1 - Fackeldey, Konstantin A1 - Gleixner, Ambros A1 - Grever, Andreas A1 - Weber, Marcus T1 - Mixed-Integer Programming for Cycle Detection in Non-reversible Markov Processes N2 - In this paper, we present a new, optimization-based method to exhibit cyclic behavior in non-reversible stochastic processes. While our method is general, it is strongly motivated by discrete simulations of ordinary differential equations representing non-reversible biological processes, in particular molecular simulations. Here, the discrete time steps of the simulation are often very small compared to the time scale of interest, i.e., of the whole process. In this setting, the detection of a global cyclic behavior of the process becomes difficult because transitions between individual states may appear almost reversible on the small time scale of the simulation. We address this difficulty using a mixed-integer programming model that allows us to compute a cycle of clusters with maximum net flow, i.e., large forward and small backward probability. For a synthetic genetic regulatory network consisting of a ring-oscillator with three genes, we show that this approach can detect the most productive overall cycle, outperforming classical spectral analysis methods. Our method applies to general non-equilibrium steady state systems such as catalytic reactions, for which the objective value computes the effectiveness of the catalyst. T3 - ZIB-Report - 16-39 KW - Non-reversible Markov Processes KW - NESS KW - Mixed-Integer Programming KW - Markov State Models Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60353 SN - 1438-0064 ER - TY - JOUR A1 - Witzig, Jakob A1 - Beckenbach, Isabel A1 - Eifler, Leon A1 - Fackeldey, Konstantin A1 - Gleixner, Ambros A1 - Grever, Andreas A1 - Weber, Marcus T1 - Mixed-Integer Programming for Cycle Detection in Non-reversible Markov Processes JF - Multiscale Modeling and Simulation N2 - In this paper, we present a new, optimization-based method to exhibit cyclic behavior in non-reversible stochastic processes. While our method is general, it is strongly motivated by discrete simulations of ordinary differential equations representing non-reversible biological processes, in particular molecular simulations. Here, the discrete time steps of the simulation are often very small compared to the time scale of interest, i.e., of the whole process. In this setting, the detection of a global cyclic behavior of the process becomes difficult because transitions between individual states may appear almost reversible on the small time scale of the simulation. We address this difficulty using a mixed-integer programming model that allows us to compute a cycle of clusters with maximum net flow, i.e., large forward and small backward probability. For a synthetic genetic regulatory network consisting of a ring-oscillator with three genes, we show that this approach can detect the most productive overall cycle, outperforming classical spectral analysis methods. Our method applies to general non-equilibrium steady state systems such as catalytic reactions, for which the objective value computes the effectiveness of the catalyst. KW - Markov State Models KW - NESS KW - Non-reversible Markov Processes KW - Mixed-Integer Programming Y1 - 2018 U6 - https://doi.org/10.1137/16M1091162 SN - 1438-0064 VL - 16 IS - 1 SP - 248 EP - 265 ER - TY - JOUR A1 - Maher, Stephen J. T1 - A novel passenger recovery approach for the integrated airline recovery problem JF - Computers & Operations Research N2 - Schedule disruptions require airlines to intervene through the process of recovery; this involves modifications to the planned schedule, aircraft routings, crew pairings and passenger itineraries. Passenger recovery is generally considered as the final stage in this process, and hence passengers experience unnecessarily large impacts resulting from flight delays and cancellations. Most recovery approaches considering passengers involve a separately defined module within the problem formulation. However, this approach may be overly complex for recovery in many aviation and general transportation applications. This paper presents a unique description of the cancellation variables that models passenger recovery by prescribing the alternative travel arrangements for passengers in the event of flight cancellations. The results will demonstrate that this simple, but effective, passenger recovery approach significantly reduces the operational costs of the airline and increases passenger flow through the network. The integrated airline recovery problem with passenger reallocation is solved using column-and-row generation to achieve high quality solutions in short runtimes. An analysis of the column-and-row generation solution approach is performed, identifying a number of enhancement techniques to further improve the solution runtimes. Y1 - 2015 U6 - https://doi.org/10.1016/j.cor.2014.11.005 VL - 57 SP - 123 EP - 137 ER - TY - GEN A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Hendel, Gregor T1 - Rounding and Propagation Heuristics for Mixed Integer Programming N2 - 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. T3 - ZIB-Report - 11-29 KW - primal heuristic KW - mixed integer programming KW - domain propagation Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-13255 ER - TY - CHAP A1 - Berthold, Timo A1 - Feydy, Thibaut A1 - Stuckey, Peter ED - Lodi, Andrea ED - Milano, Michela ED - Toth, Paolo T1 - Rapid Learning for Binary Programs T2 - Proc. of CPAIOR 2010 Y1 - 2010 VL - 6140 SP - 51 EP - 55 PB - Springer ER - TY - CHAP A1 - Berthold, Timo ED - Kalcsics, Jörg ED - Nickel, Stefan T1 - Heuristics of the Branch-Cut-and-Price-Framework SCIP T2 - Operations Research Proceedings 2007 Y1 - 2008 SP - 31 EP - 36 PB - Springer-Verlag ER - TY - THES A1 - Berthold, Timo T1 - Primal Heuristics for Mixed Integer Programs Y1 - 2006 UR - http://opus.kobv.de/zib/volltexte/2007/1054/ ER - TY - CHAP A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Lübbecke, Marco A1 - Möhring, Rolf A1 - Schulz, Jens ED - Lodi, Andrea ED - Milano, Michela ED - Toth, Paolo T1 - A Constraint Integer Programming Approach for Resource-Constrained Project Scheduling T2 - Proc. of CPAIOR 2010 Y1 - 2010 VL - 6140 SP - 313 EP - 317 PB - Springer ER - TY - CHAP A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Pfetsch, Marc ED - Kullmann, Oliver T1 - Nonlinear pseudo-Boolean optimization T2 - Theory and Applications of Satisfiability Testing – SAT 2009 Y1 - 2009 VL - 5584 SP - 441 EP - 446 PB - Springer ER - TY - CHAP A1 - Achterberg, Tobias A1 - Berthold, Timo ED - van Hoeve, Willem ED - Hooker, John T1 - Hybrid Branching T2 - Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 6th International Conference, CPAIOR 2009 Y1 - 2009 VL - 5547 SP - 309 EP - 311 PB - Springer ER - TY - CHAP A1 - Berthold, Timo A1 - Pfetsch, Marc ED - Fleischmann, Bernhard ED - Borgwardt, Karl ED - Klein, Robert ED - Tuma, Axel T1 - Detecting Orbitopal Symmetries T2 - Operations Research Proceedings 2008 Y1 - 2009 SP - 433 EP - 438 PB - Springer-Verlag ER - TY - THES A1 - Gamrath, Gerald T1 - Generic Branch-Cut-and-Price N2 - In this thesis, we present the theoretical background, implementational details and computational results concerning the generic branch-cut-and-price solver GCG. KW - mixed-integer programming KW - column generation KW - branch-and-price Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57543 ER -