Speaker:
Ismael Regis de Farias
Visiting Scholar, GSIA
Title:
Branch-and-cut for combinatorial optimization problems without auxiliary binary variables
Abstract:
Many optimization problems involve combinatorial constraints on continuous variables. An example of a combinatorial constraint is that at most k out of n nonnegative variables may be positive. Traditionally such problems have been modeled as mixed-integer programs by introducing auxiliary binary variables and additional constraints. Because the number of variables and the number of constraints become larger and the combinatorial constraints are not used to advantage, these mixed-integer programs may not be solved satisfactorily, except for small instances. In this talk I will present a branch-and-cut approach that considers the combinatorial constraints without the introduction of auxiliary binary variables. I will review the development of this approach, and show how strong cuts can be derived using ideas from polyhedral combinatorics. Finally, I will show how this polyhedral study can be applied to mixed-integer programming, both with binary variables and general integer variables.