Strengthening V-polyhedral disjunctive cuts

Abstract: The V-polyhedral framework is a recent approach for generating disjunctive cutting planes for mixed-integer linear programs. Unlike the lift-and-project method, which requires the construction of a computationally demanding higher-dimensional formulation, V-polyhedral disjunctive cuts can be computed via a linear program in the same dimension as the original problem. However, without the values of the extra variables used for lift-and-project cuts, one cannot directly apply a posteriori cut strengthening techniques such as monoidal strengthening. We show how the values of those extra variables can be computed efficiently, and thereby lay the groundwork for strengthening arbitrary valid disjunctive cuts. We present computational experiments with this idea on V-polyhedral disjunctive cuts.

game theorymachine learningmathematical softwarecomputer science theorycombinatoricsoptimization and control

Audience: researchers in the topic

Mixed Integer Programming Workshop 2021

Series comments: The 18th Mixed Integer Programming Workshop will be held online on May 24-27, 2021.

It will feature 21 distinguished invited speakers covering most aspects of Mathematical Optimization, an interactive, gamified MIP student poster session with 50 posters, and a casual business meeting.

Registration is free of charge. Register here: fico.zoom.us/webinar/register/2416186463858/WN_DVLhGOToQkKyvKYPiA4cQw

Find the website of MIP2021 at sites.google.com/view/mipworkshop2021/.