cut selection

A novel Pareto-optimal cut selection strategy for Benders Decomposition

  • Lukas Glomb
  • Frauke Liers
  • Florian Rösel
    • Categories (Mixed) Integer Linear Programming Tags ,

    Decomposition methods can be used to create efficient solution algorithms for a wide range of optimization problems. For example, Benders Decomposition can be used to solve scenario-expanded two-stage stochastic optimization problems effectively. Benders Decomposition iteratively generates Benders cuts by solving a simplified version of an optimization problem, the so-called subproblem. The choice of the generated … Read more

    On the depth of cutting planes

  • Laurent Poirrier
  • James Yu
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Cutting Plane Approaches Tags , ,

    We introduce a natural notion of depth that applies to individual cutting planes as well as entire families. This depth has nice properties that make it easy to work with theoretically, and we argue that it is a good proxy for the practical strength of cutting planes. In particular, we show that its value lies … Read more

    Scoring positive semidefinite cutting planes for quadratic optimization via trained neural networks

  • Radu Baltean-Lugojan
  • Pierre Bonami
  • Ruth Misener
  • Andrea Tramontani
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Quadratic Programming Tags , , , , ,

    Semidefinite programming relaxations complement polyhedral relaxations for quadratic optimization, but global optimization solvers built on polyhedral relaxations cannot fully exploit this advantage. This paper develops linear outer-approximations of semidefinite constraints that can be effectively integrated into global solvers. The difference from previous work is that our proposed cuts are (i) sparser with respect to the … Read more