PC Seminar: Conflict Analysis for 0-1 Integer Linear Programs

Abstract: Over the past few decades, astonishing progress has been made in Boolean satisfiability (SAT) solving. A key ingredient in this is conflict-driven search and learning, which has led to exponential improvements. Can we generalize this to the much more expressive paradigm of 0-1 integer linear programming?

In this talk, I will first explain conflict analysis in SAT solving. Then I will explain the need to apply cut rules in conflict analysis for 0-1 integer linear programming, and discuss different cut rules inspired by both proof complexity and operations research literature.

This is a seminar in our seminar series on Probability and Combinatorics (PC).

Text