pseudo-Boolean reasoning

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

    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