We investigate linear programming based branch-and-bound using general disjunctions and derive the first super-polynomial exponential lower bound (in the encoding length of the integer program) for the size of a general branch-and-bound tree for a particular class of integer programs. This is achieved by showing that general branch-and-bound admits quasi-feasible monotone real interpolation. Specialized to a certain integer program expressing that no graph can have both a k-coloring and a (k+1)-clique, this property states that any branch-and-bound tree for this program can be turned into a monotone real circuit of similar size, distinguishing between graphs with a k-coloring and graphs with a (k+1)-clique. This allows to utilize known lower-bounds for such circuits.
Moreover, using the recently introduced notion of infeasibility certificates of Hrubeš and Pudlák, we can show that it is exponentially hard to prove infeasibility of certain random CNFs by general branch-and-bound with high probability via the same technique.

A branch-and-bound (BB) tree certifies a dual bound on the value of an integer program. In this work, we introduce the tree compression problem (TCP): Given a BB tree T that certifies a dual bound, can we obtain a smaller tree with the same (or stronger) bound by either (1) applying a different disjunction at some node in T or (2) removing leaves from T? We believe such post-hoc analysis of BB trees may assist in identifying helpful general disjunctions in BB algorithms. We initiate our study by considering computational complexity and limitations of TCP. We then conduct experiments to evaluate the compressibility of realistic branch-and-bound trees generated by commonly-used branching strategies, using both an exact and a heuristic compression algorithm.

Cutting planes are a crucial tool in mixed-integer programming. When measuring the strength of a specific class of cutting planes, a key question is whether the corresponding cut closure is polyhedral, meaning that finitely many cuts are sufficient to obtain the closure. The vast amount of literature investigating polyhedrality for different kinds of cutting planes indicates that the field has not yet settled on a universal solution to this problem. In this talk, we will look at cutting plane generation through a unifying framework and establish conditions that ensure polyhedrality of cut closures. This enables us to prove polyhedrality for a broad range of cutting plane families more easily.

While many classes of cutting planes described in the literature have been effective in terms of gap closure, they are often computationally demanding to generate and offer only modest improvements in running times. Taking into account that many discrete optimization problems are solved repeatedly with only slight variations in input data, in this talk we investigate the usage of machine learning (ML) methods to accelerate the selection and generation of such cuts. We start by introducing MIPLearn, an extensible open-source framework which uses machine learning (ML) to enhance the performance of state-of-the-art MIP solvers. The framework is compatible with multiple MIP solvers (e.g. Gurobi, CPLEX, SCIP, HiGHS), multiple modeling languages (JuMP, Pyomo, gurobipy) and supports user-provided ML models. We then present computational experiments on using ML to accelerate the generation of rank-1 Gomory mixed-integer (GMI) cuts from multiple tableau bases.