TBTimo Berthold

Timo Berthold

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Timo Berthold has a total of 52 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Global Optimization for Combinatorial Geometry Problems Revisited in the Era of LLMs

    by Timo Berthold, Dominik Kamp, Gioni Mexi, Sebastian Pokutta, Imre Pólik

  • Open Access

    Learning to Choose Branching Rules for Nonconvex MINLPs

    by Timo Berthold, Fritz Geis

    Outer-approximation-based branch-and-bound is a common algorithmic framework for solving MINLPs (mixed-integer nonlinear programs) to global optimality, with branching variable selection critically influencing overall performance. In modern global MINLP solvers, it is unclear whether branching on fractional integer variables should be prioritized over spatial branching on variables, potentially continuous, that show constraint violations, with different solvers following different defaults. We address this question using a data-driven approach. Based on a test set of hundreds of heterogeneous public and industrial MINLP instances, we train linear and random forest regression models to predict the relative speedup of the FICO(R) Xpress Global solver when using a branching rule that always prioritizes variables with violated integralities versus a mixed rule, allowing for early spatial branches. We introduce a practical evaluation methodology that measures the effect of the learned model directly in terms of the shifted geometric mean runtime. Using only four features derived from strong branching and the nonlinear structure, our linear regression model achieves an 8-9% reduction in geometric-mean solving time for the Xpress solver, with over 10% improvement on hard instances. We also analyze a random regression forest model. Experiments across solver versions show that a model trained on Xpress 9.6 still yields significant improvements on Xpress 9.8 without retraining. Our results demonstrate how regression models can successfully guide the branching-rule selection and improve the performance of a state-of-the-art commercial MINLP solver.

  • Cut-Based Conflict Analysis in Mixed Integer Programming

    by Gioni Mexi, Felipe Serrano, Timo Berthold, Ambros Gleixner, Jakob Nordström

    For almost two decades, mixed integer programming (MIP) solvers have used graph-based conflict analysis to learn from local infeasibilities during branch-and-bound search. In this paper, we improve MIP conflict analysis by, instead, using reasoning based on cuts inspired by the development of conflict-driven solvers for pseudo-Boolean optimization. Phrased in MIP terminology, this type of conflict analysis can be understood as a sequence of linear combinations, integer roundings, and cut generation. We leverage this MIP perspective to design a new conflict analysis algorithm based on mixed integer rounding cuts, and this theoretically dominates the state-of-the-art method in pseudo-Boolean optimization using Chvátal–Gomory cuts. Furthermore, we extend this cut-based conflict analysis from pure binary programs to mixed binary programs and—in limited form—to general MIP with also integer-valued variables. We perform an empirical evaluation of cut-based conflict analysis as implemented in the open-source MIP solver Solving Constraint Integer Programs (SCIP), testing it on a large and diverse set of MIP instances from MIPLIB2017. Our experimental results indicate that the new algorithm improves the default performance of SCIP in terms of running time, number of nodes in the search tree, and the number of instances solved. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by the Research Campus Modal funded by the German Federal Ministry of Research, Technology, and Space [Grants 05M14ZAM, 05M20ZBM]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0999 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0999 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .


  • Code and Data Repository for Cut-based Conflict Analysis in Mixed Integer Programming

    by Gioni Mexi, Felipe Serrano, Timo Berthold, Ambros Gleixner, Jakob Nordström

    The software and data in this repository are snapshots used in the research reported in the paper Cut-based Conflict Analysis in Mixed Integer Programming by Gioni Mexi, Felipe Serrano, Timo Berthold, Ambros Gleixner, Jakob Nordström.

  • Top Cited Papers

    Learning to use local cuts

    by Timo Berthold, Matteo Francobaldi, Gregor Hendel


  • Open Access

    The MIP Workshop 2023 Computational Competition on reoptimization

    by Suresh Bolusani, Mathieu Besançon, Ambros Gleixner, Timo Berthold, Claudia D’ambrosio, Gonzalo Muñoz, Joseph Paat, Dimitri Thomopulos

    This paper describes the computational challenge developed for a computational competition held in 2023 for the $$20{\text {th}}$$ 20 th 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.


  • Open Access

    Improving Conflict Analysis in MIP Solvers by Pseudo-Boolean Reasoning

    by Gioni Mexi, Timo Berthold, Ambros Gleixner, Jakob Nordström

    Conflict analysis has been successfully generalized from Boolean satisfiability (SAT) solving to mixed integer programming (MIP) solvers, but although MIP solvers operate with general linear inequalities, the conflict analysis in MIP has been limited to reasoning with the more restricted class of clausal constraint. This is in contrast to how conflict analysis is performed in so-called pseudo-Boolean solving, where solvers can reason directly with 0-1 integer linear inequalities rather than with clausal constraints extracted from such inequalities. In this work, we investigate how pseudo-Boolean conflict analysis can be integrated in MIP solving, focusing on 0-1 integer linear programs (0-1 ILPs). Phrased in MIP terminology, conflict analysis can be understood as a sequence of linear combinations and cuts. We leverage this perspective to design a new conflict analysis algorithm based on mixed integer rounding (MIR) cuts, which theoretically dominates the state-of-the-art division-based method in pseudo-Boolean solving. We also report results from a first proof-of-concept implementation of different pseudo-Boolean conflict analysis methods in the open-source MIP solver SCIP. When evaluated on a large and diverse set of 0-1 ILP instances from MIPLIB 2017, our new MIR-based conflict analysis outperforms both previous pseudo-Boolean methods and the clause-based method used in MIP. Our conclusion is that pseudo-Boolean conflict analysis in MIP is a promising research direction that merits further study, and that it might also make sense to investigate the use of such conflict analysis to generate stronger no-goods in constraint programming.

  • Open Access

    A Context-Aware Cutting Plane Selection Algorithm for Mixed-Integer Programming

    by Mark Turner, Timo Berthold, Mathieu Besançon

    The current cut selection algorithm used in mixed-integer programming solvers has remained largely unchanged since its creation. In this paper, we propose a set of new cut scoring measures, cut filtering techniques, and stopping criteria, extending the current state-of-the-art algorithm and obtaining a 5\% performance improvement for SCIP over the MIPLIB 2017 benchmark set.