CAREER: Disjunctive Cutting Plane Selection via Machine Learning for Mixed Integer Programming

This Faculty Early Career Development Program (CAREER) grant will fund research that looks to advance the field of optimization by providing a new generation of learning-enabled cutting planes that can equip commercial optimization solvers with significant new capabilities. Cutting planes can refine a problem's formulation and certify solution quality, complementing other approaches that primarily seek feasible decisions without guarantees.

However, stronger cutting planes incur a higher computational cost and radiate effects through the optimization process. This research project intends to develop novel learning architectures to judiciously deploy cutting plane strategies intending to improve current data-agnostic techniques by exploiting the presence of shared structure in modern optimization settings.

The improvements will enable faster solution times and more complex models for challenging operational problems, exhibited in the project by engineering applications in power systems, logistics, and healthcare. The educational plan will extend a current partnership in the non-profit sector to increase accessibility of valuable optimization expertise and provide student engagement through engineering senior design projects.

Integer programming solvers currently rely on restricted cuts from a broader disjunction-based family of inequalities, which are derived from tightening the feasible region via subproblems. Incorporating cuts from stronger disjunctions with more terms is hindered by a lack of generalizable understanding of what makes a cut useful and how solver components interact.

Towards addressing these obstacles, this project will employ theoretical analysis and computational experiments to create efficient learning-based cut and disjunction selection strategies by: (1) classifying when cuts help; (2) adaptively identifying beneficial disjunctions and subsets of cuts; (3) tailoring models for unit commitment, vehicle routing, and organ exchange market problems; and (4) applying the new methods to optimize logistics at local nonprofits in combination with student capstone and research opportunities. The investigation will yield deeper, transparent, and actionable insights into cuts and disjunctions, informing algorithms for which implementations will be open sourced and whose performance will be evaluated on a curated and publicly-releasable benchmark dataset.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.