2574. Learning Primal Heuristics for 0-1 Knapsack Interdiction Problems
Invited abstract in session WC-34: Business Applications of Knowledge and Technology, stream Advancements of OR-analytics in statistics, machine learning and data science.
Wednesday, 12:30-14:00Room: Michael Sadler LG10
Authors (first author is the speaker)
| 1. | Luca Ferrarini
|
| LIPN, Sorbonne Paris Nord | |
| 2. | Stefano Gualandi
|
| Pavia, Department of Mathematics, "Felice Casorati" | |
| 3. | Axel Parmentier
|
| CERMICS, Ecole des Ponts ParisTech |
Abstract
Knapsack Interdiction Problems (KIP) are NP-hard problems of significant interest, as they model scenarios where two opposing forces interact within a leader-follower framework. The leader moves first, selecting items to restrict the follower’s choices, while the follower subsequently selects items that maximize their profit from the remaining options. Despite the development of various algorithms to tackle these problems, efficiently solving large instances remains a challenge.
In this work, we propose a heuristic that relaxes the interdiction constraint by solving two separate linear problems, achieving a balance between computational efficiency and solution quality.
Our method leverages a Machine Learning model incorporating an InferOpt layer, a framework designed to integrate combinatorial optimization into ML pipelines by differentiating through optimization solvers. The output of this pipeline serves as the cost vector for one of the linear problems, which are then solved exactly to generate an approximate solution for the KIP. Through extensive experiments, we demonstrate that our heuristic ensures low computational time while maintaining a small optimality gap.
Keywords
- Machine Learning
- Combinatorial Optimization
- Programming, Mixed-Integer
Status: accepted
Back to the list of papers