Learning Primal Heuristics for 0–1 Knapsack Interdiction Problems

In interdiction problems, two opposing decision-makers act sequentially: the leader plays first by selecting items to restrict the choices of the follower, while the follower selects those that maximize her profit from the remaining items. In knapsack interdiction, both decision-makers face different budget constraints. We propose a heuristic based on a single-level approximation of the leader-follower problem that we interpret as a combinatorial optimization layer in a machine learning pipeline. The ML pipeline includes a Generalized Linear Model as the first layer, which predicts the parameters of the single-level problem. Using a perturbation approach, we regularize the single-level problem, which enables to make it differentiable and provides a natural loss to train the model. Once trained, the pipeline provides effective ordering heuristics to solve Knapsack Interdiction problems. Extensive computational results on benchmarks from the literature show that the learned ML-based primal heuristics are extremely fast and compute solutions with a small optimality gap.