TY - GEN A1 - Berthold, Timo A1 - Gamrath, Gerald A1 - Salvagnin, Domenico T1 - Exploiting Dual Degeneracy in Branching N2 - Branch-and-bound methods for mixed-integer programming (MIP) are traditionally based on solving a linear programming (LP) relaxation and branching on a variable which takes a fractional value in the (single) computed relaxation optimum. In this paper, we study branching strategies for mixed-integer programs that exploit the knowledge of multiple alternative optimal solutions (a cloud ) of the current LP relaxation. These strategies naturally extend common methods like most infeasible branching, strong branching, pseudocost branching, and their hybrids, but we also propose a novel branching rule called cloud diameter branching. We show that dual degeneracy, a requirement for alternative LP optima, is present for many instances from common MIP test sets. Computational experiments show significant improvements in the quality of branching decisions as well as reduced branching effort when using our modifications of existing branching rules. We discuss different ways to generate a cloud of solutions and present extensive computational results showing that through a careful implementation, cloud modifications can speed up full strong branching by more than 10 % on standard test sets. Additionally, by exploiting degeneracy, we are also able to improve the state-of-the-art hybrid branching rule and reduce the solving time on affected instances by almost 20 % on average. T3 - ZIB-Report - 19-17 KW - mixed integer programming KW - branching rule KW - search strategy KW - dual degeneracy Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-73028 SN - 1438-0064 ER - TY - CHAP A1 - Berthold, Timo A1 - Grimm, Boris A1 - Reuther, Markus A1 - Schade, Stanley A1 - Schlechte, Thomas T1 - Strategic Planning of Rolling Stock Rotations for Public Tenders T2 - Proceedings of the 8th International Conference on Railway Operations Modelling and Analysis - RailNorrköping 2019 N2 - Since railway companies have to apply for long-term public contracts to operate railway lines in public tenders, the question how they can estimate the operating cost for long-term periods adequately arises naturally. We consider a rolling stock rotation problem for a time period of ten years, which is based on a real world instance provided by an industry partner. We use a two stage approach for the cost estimation of the required rolling stock. In the first stage, we determine a weekly rotation plan. In the second stage, we roll out this weekly rotation plan for a longer time period and incorporate scheduled maintenance treatments. We present a heuristic approach and a mixed integer programming model to implement the process of the second stage. Finally, we discuss computational results for a real world tendering scenario. Y1 - 2019 UR - http://www.ep.liu.se/ecp/article.asp?issue=069&article=009&volume= SN - 978-91-7929-992-7 SN - 1650-3686 VL - Linköping Electronic Conference Proceedings IS - 069 SP - 148 EP - 159 PB - Linköping University Electronic Press, Linköpings universitet ER - TY - JOUR A1 - Gamrath, Gerald A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Winkler, Michael T1 - Structure-driven fix-and-propagate heuristics for mixed integer programming JF - Mathematical Programming Computation N2 - Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They often provide good feasible solutions early and help to reduce the time needed to prove optimality. In this paper, we present a scheme for start heuristics that can be executed without previous knowledge of an LP solution or a previously found integer feasible solution. It uses global structures available within MIP solvers to iteratively fix integer variables and propagate these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. If sufficiently many variables can be fixed that way, the resulting problem is solved first as an LP, and then as an auxiliary MIP if the rounded LP solution does not provide a feasible solution already. We present three primal heuristics that use this scheme based on different global structures. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about 60 % of the instances and by this, help to improve several performance measures for MIP solvers, including the primal integral and the average solving time. Y1 - 2019 U6 - https://doi.org/10.1007/s12532-019-00159-1 VL - 11 IS - 4 SP - 675 EP - 702 PB - Springer CY - Berlin Heidelberg ER - TY - GEN A1 - Witzig, Jakob A1 - Berthold, Timo T1 - Conflict-Free Learning for Mixed Integer Programming N2 - Conflict learning plays an important role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. A major step for MIP conflict learning is to aggregate the LP relaxation of an infeasible subproblem to a single globally valid constraint, the dual proof, that proves infeasibility within the local bounds. Among others, one way of learning is to add these constraints to the problem formulation for the remainder of the search. We suggest to not restrict this procedure to infeasible subproblems, but to also use global proof constraints from subproblems that are not (yet) infeasible, but can be expected to be pruned soon. As a special case, we also consider learning from integer feasible LP solutions. First experiments of this conflict-free learning strategy show promising results on the MIPLIB2017 benchmark set. T3 - ZIB-Report - 19-59 KW - mixed integer programming KW - conflict analysis KW - dual proof analysis KW - no-good learning KW - solution learning Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-75338 SN - 1438-0064 ER - TY - GEN A1 - Witzig, Jakob A1 - Berthold, Timo A1 - Heinz, Stefan T1 - Computational Aspects of Infeasibility Analysis in Mixed Integer Programming N2 - The analysis of infeasible subproblems plays an important role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. There are two fundamentally different concepts to generate valid global constraints from infeasible subproblems. The first is to analyze the sequence of implications, obtained by domain propagation, that led to infeasibility. The result of this analysis is one or more sets of contradicting variable bounds from which so-called conflict constraints can be generated. This concept is called conflict graph analysis and has its origin in solving satisfiability problems and is similarly used in constraint programming. The second concept is to analyze infeasible linear programming (LP) relaxations. Every ray of the dual LP provides a set of multipliers that can be used to generate a single new globally valid linear constraint. This method is called dual proof analysis. The main contribution of this paper is twofold. Firstly, we present three enhancements of dual proof analysis: presolving via variable cancellation, strengthening by applying mixed integer rounding functions, and a filtering mechanism. Further, we provide an intense computational study evaluating the impact of every presented component regarding dual proof analysis. Secondly, this paper presents the first integrated approach to use both conflict graph and dual proof analysis simultaneously within a single MIP solution process. All experiments are carried out on general MIP instances from the standard public test set MIPLIB 2017; the presented algorithms have been implemented within the non-commercial MIP solver SCIP and the commercial MIP solver FICO Xpress. T3 - ZIB-Report - 19-54 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-74962 SN - 1438-0064 ER - TY - CHAP A1 - Witzig, Jakob A1 - Berthold, Timo A1 - Heinz, Stefan T1 - A Status Report on Conflict Analysis in Mixed Integer Nonlinear Programming T2 - Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2019 N2 - Mixed integer nonlinear programs (MINLPs) are arguably among the hardest optimization problems, with a wide range of applications. MINLP solvers that are based on linear relaxations and spatial branching work similar as mixed integer programming (MIP) solvers in the sense that they are based on a branch-and-cut algorithm, enhanced by various heuristics, domain propagation, and presolving techniques. However, the analysis of infeasible subproblems, which is an important component of most major MIP solvers, has been hardly studied in the context of MINLPs. There are two main approaches for infeasibility analysis in MIP solvers: conflict graph analysis, which originates from artificial intelligence and constraint programming, and dual ray analysis. The main contribution of this short paper is twofold. Firstly, we present the first computational study regarding the impact of dual ray analysis on convex and nonconvex MINLPs. In that context, we introduce a modified generation of infeasibility proofs that incorporates linearization cuts that are only locally valid. Secondly, we describe an extension of conflict analysis that works directly with the nonlinear relaxation of convex MINLPs instead of considering a linear relaxation. This is work-in-progress, and this short paper is meant to present first theoretical considerations without a computational study for that part. Y1 - 2019 U6 - https://doi.org/10.1007/978-3-030-19212-9_6 VL - 11494 SP - 84 EP - 94 PB - Springer ER - TY - CHAP A1 - Berthold, Timo A1 - Stuckey, Peter A1 - Witzig, Jakob T1 - Local Rapid Learning for Integer Programs T2 - Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2019 N2 - Conflict learning algorithms are an important component of modern MIP and CP solvers. But strong conflict information is typically gained by depth-first search. While this is the natural mode for CP solving, it is not for MIP solving. Rapid Learning is a hybrid CP/MIP approach where CP search is applied at the root to learn information to support the remaining MIP solve. This has been demonstrated to be beneficial for binary programs. In this paper, we extend the idea of Rapid Learning to integer programs, where not all variables are restricted to the domain {0, 1}, and rather than just running a rapid CP search at the root, we will apply it repeatedly at local search nodes within the MIP search tree. To do so efficiently, we present six heuristic criteria to predict the chance for local Rapid Learning to be successful. Our computational experiments indicate that our extended Rapid Learning algorithm significantly speeds up MIP search and is particularly beneficial on highly dual degenerate problems. Y1 - 2019 U6 - https://doi.org/10.1007/978-3-030-19212-9_5 VL - 11494 SP - 67 EP - 83 PB - Springer ER -