pseudo-Boolean optimization

Cut-based Conflict Analysis in Mixed Integer Programming

  • Gioni Mexi
  • Felipe Serrano
  • Ambros Gleixner
  • Timo Berthold
    • 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

    Relaxation strength for multilinear optimization: McCormick strikes back

  • Matthias Walter
    • Categories (Mixed) Integer Linear Programming, Nonlinear Optimization, Polyhedra Tags , , , , ,

    We consider linear relaxations for multilinear optimization problems. In a recent paper, Khajavirad proved that the extended flower relaxation is at least as strong as the relaxation of any recursive McCormick linearization (Operations Research Letters 51 (2023) 146-152). In this paper we extend the result to more general linearizations, and present a simpler proof. Moreover, … Read more