MIP 2024 Logo

Mixed Integer Programming Workshop 2024

June 2, 2024 (summer school)

June 3-6, 2024 (regular workshop)

University of Kentucky

Summer School

The 2024 edition of the MIP workshop hosts a summer school on cutting planes. The summer school takes place at Room 121 of Don and Cathy Jacobs Science Building of the University of Kentucky on Sunday June 2, 2024.

Attendees of the summer school are required to register for the MIP workshop. There will be no additional fees for the summer school though.

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. (slides)

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. (slides)

11:05 - 11:15 Break
11:15 - 12: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. (slides)

12:00 - 1:45 Lunch
1:45 - 2:45

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.

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.

Credits

Logo-Design by ©Julia Silbermann (Font-Credits: Cornerstone, by Zac Freeland). Website hosted at GitHub Pages, layout based on skeleton using Raleway font