Timo Berthold

Learning to Choose Branching Rules for Nonconvex MINLPs

  • Timo Berthold
  • Fritz Geis
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization

    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 … Read more

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

  • Timo Berthold
  • Dominik Kamp
  • Gioni Mexi
  • Sebastian Pokutta
  • Imre Pólik
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Optimization Software and Modeling Systems Tags , , ,

    Recent progress in LLM-driven algorithm discovery, exemplified by DeepMind’s AlphaEvolve, has produced new best-known solutions for a range of hard geometric and combinatorial problems. This raises a natural question: to what extent can modern off-the-shelf global optimization solvers match such results when the problems are formulated directly as nonlinear optimization problems (NLPs)? We revisit a … Read more

    Solving MINLPs to global optimality with FICO Xpress Global

  • Pietro Belotti
  • Timo Berthold
  • Tristan Gally
  • Leona Gottwald
  • Imre Pólik
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Optimization Software Design Principles Tags , ,

    We present the architecture and central parts of the FICO Xpress Global optimization solver. In particular, we focus on how we built a global solver for the general class of mixed-integer nonlinear optimization problems by combining and extending two existing components of the FICO Xpress Solver, namely the mixed-integer linear optimization solver and the successive … Read more

    Cut-based Conflict Analysis in Mixed Integer Programming

  • Gioni Mexi
  • Felipe Serrano
  • Timo Berthold
  • Ambros Gleixner
  • jakobnordstrom
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Integer Programming Tags , , , , ,

    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 … Read more

    Tricks from the Trade for Large-Scale Markdown Pricing: Heuristic Cut Generation for Lagrangian Decomposition

  • Robert Streeck
  • Andreas Schmitt
  • Torsten Gellert
  • Asya Dipkaya
  • Vladimir Fux
  • Tim Januschowski
  • Timo Berthold
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences Tags , , , ,

    In automated decision making processes in the online fashion industry, the ‘predict-then-optimize’ paradigm is frequently applied, particularly for markdown pricing strategies. This typically involves a mixed-integer optimization step, which is crucial for maximizing profit and merchandise volume. In practice, the size and complexity of the optimization problem is prohibitive for using off-the-shelf solvers for mixed … Read more

    The MIP Workshop 2023 Computational Competition on Reoptimization

  • Suresh Bolusani
  • Mathieu Besançon
  • Ambros Gleixner
  • Timo Berthold
  • Claudia D'Ambrosio
  • Gonzalo Muñoz
  • Joseph Paat
  • Dimitri Thomopulos
    • Categories Combinatorial Optimization, Integer Programming, Optimization Software and Modeling Systems Tags , , , ,

    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 … Read more

    Improving Conflict Analysis in MIP Solvers by Pseudo-Boolean Reasoning

  • Gioni Mexi
  • Timo Berthold
  • Ambros Gleixner
    • Categories 0-1 Programming, Integer Programming Tags , , ,

    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 … Read more

    Using Multiple Reference Vectors and Objective Scaling in the Feasibility Pump

  • Timo Berthold
  • Gioni Mexi
  • Domenico Salvagnin
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming Tags ,

    The Feasibility Pump (FP) is one of the best-known primal heuristics for mixed-integer programming (MIP): more than 15 papers suggested various modifications of all of its steps. So far, no variant considered information across multiple iterations, but all instead maintained the principle to optimize towards a single reference integer point. In this paper, we evaluate … Read more

    Learning to Use Local Cuts

  • Timo Berthold
  • Matteo Francobaldi
  • Gregor Hendel
    • Categories (Mixed) Integer Linear Programming, Optimization Software Design Principles Tags , ,

    An essential component in modern solvers for mixed-integer (linear) programs (MIPs) is the separation of additional inequalities (cutting planes) to tighten the linear programming relaxation. Various algorithmic decisions are necessary when integrating cutting plane methods into a branch-and-bound (B&B) solver as there is always the trade-off between the efficiency of the cuts and their costs, … Read more

    Learning To Scale Mixed-Integer Programs

  • Timo Berthold
  • Gregor Hendel
    • Categories (Mixed) Integer Linear Programming, Linear Programming, Optimization Software Design Principles Tags , , , , , ,

    Many practical applications require the solution of numerically challenging linear programs (LPs) and mixed-integer programs (MIPs). Scaling is a widely used preconditioning technique that aims at reducing the error propagation of the involved linear systems, thereby improving the numerical behavior of the dual simplex algorithm and, consequently, LP-based branch-and-bound. A reliable scaling method often makes … Read more