Tentative Program
| 9:00 - 10:00 |
Santanu S. Dey – A general overview on cutting planes Cutting-planes are an integral part of the modern integer programming solvers. We will present a brief introduction to cutting-plane theory. We begin by discussing various paradigms of cutting-plane generation: geometric cutting-planes, structured relaxations-based cutting-planes, subadditive cutting-planes, and cutting-planes via extended formulations and algebraic properties. The presentation will emphasize how these seemingly different cutting-planes generation paradigms are related to each other, and how these techniques may be generalized to the mixed-integer nonlinear setting. Finally, we will discuss the question of cutting-plane selection and challenges related to this. |
| 10:00 - 10:20 | Coffee Break |
| 10:20 - 11:05 |
Santanu S. Dey – A general overview on cutting planes Cutting-planes are an integral part of the modern integer programming solvers. We will present a brief introduction to cutting-plane theory. We begin by discussing various paradigms of cutting-plane generation: geometric cutting-planes, structured relaxations-based cutting-planes, subadditive cutting-planes, and cutting-planes via extended formulations and algebraic properties. The presentation will emphasize how these seemingly different cutting-planes generation paradigms are related to each other, and how these techniques may be generalized to the mixed-integer nonlinear setting. Finally, we will discuss the question of cutting-plane selection and challenges related to this. |
| 11:05 - 11:15 | Break |
| 11:15 - 12:00 |
Robert Hildebrand - Intersection Cuts: Geometry, algorithms, and strength There is beautiful mathematics to be discovered when visualizing cutting planes from a geometric perspective. Enter the idea of intersection cuts. This perspective was initiated by Balas in the 1970’s and developed significantly in recent years. We will see how intersection cuts can be described using the geometry of the feasible set and computed efficiently via the tableau through the corner polyhedron relaxation. We will begin with a discussion in the context of linear integer programming and how these ideas generalize to non-convex mixed integer nonlinear programming. |
| 12:00 - 1:45 | Lunch |
| 1:45 - 2:45 |
Robert Hildebrand - Intersection Cuts: Geometry, algorithms, and strength There is beautiful mathematics to be discovered when visualizing cutting planes from a geometric perspective. Enter the idea of intersection cuts. This perspective was initiated by Balas in the 1970’s and developed significantly in recent years. We will see how intersection cuts can be described using the geometry of the feasible set and computed efficiently via the tableau through the corner polyhedron relaxation. We will begin with a discussion in the context of linear integer programming and how these ideas generalize to non-convex mixed integer nonlinear programming. |
| 2:45 - 3:05 | Coffee Break |
| 3:05 - 4:05 |
Jean-Philippe (JP) Richard - Cutting Planes for MINLP Leveraging problem structure has emerged as a useful strategy for generating strong cutting planes in integer programming. The expressive nature of nonlinear functions greatly expands the range of structured sets that can be explored in mixed-integer nonlinear programming. This presentation highlights the pivotal role of multilinear functions, which invariably appear when relaxing factorable nonlinear programs, i.e., problems characterized by constraints and objectives derived through recursive compositions of sums and products of intermediate functions, originating from a set of base univariate functions. Beginning with foundational concepts surrounding the Boolean quadric polytope, we explore how polyhedral partitions, lifting, and disjunctive approaches, among others, can be employed to gain insights and derive cutting planes for these structures. |
| 4:05 - 4:15 | Break |
| 4:15 - 5:00 |
Jean-Philippe (JP) Richard - Cutting Planes for MINLP Leveraging problem structure has emerged as a useful strategy for generating strong cutting planes in integer programming. The expressive nature of nonlinear functions greatly expands the range of structured sets that can be explored in mixed-integer nonlinear programming. This presentation highlights the pivotal role of multilinear functions, which invariably appear when relaxing factorable nonlinear programs, i.e., problems characterized by constraints and objectives derived through recursive compositions of sums and products of intermediate functions, originating from a set of base univariate functions. Beginning with foundational concepts surrounding the Boolean quadric polytope, we explore how polyhedral partitions, lifting, and disjunctive approaches, among others, can be employed to gain insights and derive cutting planes for these structures. |