TY - CHAP A1 - Ghannam, Mohammed A1 - Gleixner, Ambros T1 - Hybrid genetic search for dynamic vehicle routing with time windows T2 - Proceedings of Conference of the Society for Operations Research in Germany Y1 - 2023 ER - TY - JOUR A1 - Eifler, Leon A1 - Gleixner, Ambros T1 - Safe and verified Gomory mixed integer cuts in a rational MIP framework JF - SIAM Journal on Optimization N2 - This paper is concerned with the exact solution of mixed-integer programs (MIPs) over the rational numbers, i.e., without any roundoff errors and error tolerances. Here, one computational bottleneck that should be avoided whenever possible is to employ large-scale symbolic computations. Instead it is often possible to use safe directed rounding methods, e.g., to generate provably correct dual bounds. In this work, we continue to leverage this paradigm and extend an exact branch-and-bound framework by separation routines for safe cutting planes, based on the approach first introduced by Cook, Dash, Fukasawa, and Goycoolea in 2009 [INFORMS J. Comput., 21 (2009), pp. 641–649]. Constraints are aggregated safely using approximate dual multipliers from an LP solve, followed by mixed-integer rounding to generate provably valid, although slightly weaker inequalities. We generalize this approach to problem data that is not representable in floating-point arithmetic, add routines for controlling the encoding length of the resulting cutting planes, and show how these cutting planes can be verified according to the VIPR certificate standard. Furthermore, we analyze the performance impact of these cutting planes in the context of an exact MIP framework, showing that we can solve 21.5% more instances to exact optimality and reduce solving times by 26.8% on the MIPLIB 2017 benchmark test set. Y1 - 2024 U6 - https://doi.org/10.1137/23M156046X VL - 34 IS - 1 ER - TY - CHAP A1 - Hoen, Alexander A1 - Oertel, Andy A1 - Gleixner, Ambros A1 - Nordström, Jakob T1 - Certifying MIP-based presolve reductions for 0-1 integer linear programs T2 - Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2024 N2 - It is well known that reformulating the original problem can be crucial for the performance of mixed-integer programming (MIP) solvers. To ensure correctness, all transformations must preserve the feasibility status and optimal value of the problem, but there is currently no established methodology to express and verify the equivalence of two mixed-integer programs. In this work, we take a first step in this direction by showing how the correctness of MIP presolve reductions on – integer linear programs can be certified by using (and suitably extending) the VeriPB tool for pseudo-Boolean proof logging. Our experimental evaluation on both decision and optimization instances demonstrates the computational viability of the approach and leads to suggestions for future revisions of the proof format that will help to reduce the verbosity of the certificates and to accelerate the certification and verification process further. Y1 - 2024 U6 - https://doi.org/10.1007/978-3-031-60597-0_20 VL - 14742 ER - TY - JOUR A1 - Bolusani, Suresh A1 - Besançon, Mathieu A1 - Gleixner, Ambros A1 - Berthold, Timo A1 - D'Ambrosio, Claudia A1 - Muñoz, Gonzalo A1 - Paat, Joseph A1 - Thomopulos, Dimitri T1 - The MIP workshop 2023 computational competition on reoptimization JF - Mathematical Programming Computation N2 - This paper describes the computational challenge developed for a computational competition held in 2023 for the 20th anniversary of the Mixed Integer Programming Workshop. The topic of this competition was reoptimization, also known as warm starting, of mixed integer linear optimization problems after slight changes to the input data for a common formulation. The challenge was to accelerate the proof of optimality of the modified instances by leveraging the information from the solving processes of previously solved instances, all while creating high-quality primal solutions. Specifically, we discuss the competition’s format, the creation of public and hidden datasets, and the evaluation criteria. Our goal is to establish a methodology for the generation of benchmark instances and an evaluation framework, along with benchmark datasets, to foster future research on reoptimization of mixed integer linear optimization problems. Y1 - 2024 U6 - https://doi.org/10.1007/s12532-024-00256-w VL - 16 SP - 255 EP - 266 ER - TY - CHAP A1 - Eifler, Leon A1 - Witzig, Jakob A1 - Gleixner, Ambros T1 - Branch and cut for partitioning a graph into a cycle of clusters T2 - Combinatorial Optimization. ISCO 2024 N2 - In this paper we study formulations and algorithms for the cycle clustering problem, a partitioning problem over the vertex set of a directed graph with nonnegative arc weights that is used to identify cyclic behavior in simulation data generated from nonreversible Markov state models. Here, in addition to partitioning the vertices into a set of coherent clusters, the resulting clusters must be ordered into a cycle such as to maximize the total net flow in the forward direction of the cycle. We provide a problem-specific binary programming formulation and compare it to a formulation based on the reformulation-linearization technique (RLT). We present theoretical results on the polytope associated with our custom formulation and develop primal heuristics and separation routines for both formulations. In computational experiments on simulation data from biology we find that branch and cut based on the problem-specific formulation outperforms the one based on RLT. Y1 - 2024 U6 - https://doi.org/10.1007/978-3-031-60924-4_8 VL - 14594 ER - TY - CHAP A1 - Ghannam, Mohammed A1 - Mexi, Gioni A1 - Lam, Edward A1 - Gleixner, Ambros T1 - Branch and price for the length-constrained cycle partition problem T2 - Proceedings of INFORMS Optimization Society Conference Y1 - 2024 ER -