A Machine Learning Approach for Knapsack Interdiction Problems

Knapsack Interdiction Problems (KIP) belong to the family of bilevel optimization problems, a group of NP hard problems of great interest since they can model different concrete situations. In the literature a lot of algorithms have been presented that can solve or approximate them, achieving good results in therms of computational time or accuracy, but nowadays there are still some instances unsolved (computation exceeds time limit). With this work we change the approach, trying to break interdiction problems into two separate linear problems that are easier to solve. We lose some accuracy, because we remove all the interaction that characterizes those type of problems, but we obtain a good level of approximation and we can guarantee a low computational time. To achieve this goal we use some Machine Learning techniques that help us to train a pipeline that specializes into turning bilevel into single level problems. The main instrument we work with is InferOpt, a powerful mean that turns Combinatorial Optimization problems into functional Machine Learning layers.