@inproceedings{GhannamGleixner, author = {Ghannam, Mohammed and Gleixner, Ambros}, title = {Hybrid genetic search for dynamic vehicle routing with time windows}, series = {Proceedings of Conference of the Society for Operations Research in Germany}, booktitle = {Proceedings of Conference of the Society for Operations Research in Germany}, language = {en} } @article{EiflerGleixner, author = {Eifler, Leon and Gleixner, Ambros}, title = {Safe and verified Gomory mixed integer cuts in a rational MIP framework}, series = {SIAM Journal on Optimization}, volume = {34}, journal = {SIAM Journal on Optimization}, number = {1}, doi = {10.1137/23M156046X}, abstract = {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.}, language = {en} } @inproceedings{HoenOertelGleixneretal., author = {Hoen, Alexander and Oertel, Andy and Gleixner, Ambros and Nordstr{\"o}m, Jakob}, title = {Certifying MIP-based presolve reductions for 0-1 integer linear programs}, series = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2024}, volume = {14742}, booktitle = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2024}, doi = {10.1007/978-3-031-60597-0_20}, abstract = {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.}, language = {en} } @article{BolusaniBesanconGleixneretal., author = {Bolusani, Suresh and Besan{\c{c}}on, Mathieu and Gleixner, Ambros and Berthold, Timo and D'Ambrosio, Claudia and Mu{\~n}oz, Gonzalo and Paat, Joseph and Thomopulos, Dimitri}, title = {The MIP workshop 2023 computational competition on reoptimization}, series = {Mathematical Programming Computation}, volume = {16}, journal = {Mathematical Programming Computation}, doi = {10.1007/s12532-024-00256-w}, pages = {255 -- 266}, abstract = {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.}, language = {en} } @inproceedings{EiflerWitzigGleixner, author = {Eifler, Leon and Witzig, Jakob and Gleixner, Ambros}, title = {Branch and cut for partitioning a graph into a cycle of clusters}, series = {Combinatorial Optimization. ISCO 2024}, volume = {14594}, booktitle = {Combinatorial Optimization. ISCO 2024}, doi = {10.1007/978-3-031-60924-4_8}, abstract = {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.}, language = {en} } @inproceedings{GhannamMexiLametal., author = {Ghannam, Mohammed and Mexi, Gioni and Lam, Edward and Gleixner, Ambros}, title = {Branch and price for the length-constrained cycle partition problem}, series = {Proceedings of INFORMS Optimization Society Conference}, booktitle = {Proceedings of INFORMS Optimization Society Conference}, language = {en} }