228. Solving the Partial Inverse Knapsack Problem
Invited abstract in session WC-2: Bilevel Optimization, stream Discrete and Combinatorial Optimization.
Wednesday, 13:30-15:00Room: H4
Authors (first author is the speaker)
| 1. | Nikolas Lykourinos
|
| TU Clausthal | |
| 2. | Andreas M. Tillmann
|
| Institute for Mathematics, TU Clausthal | |
| 3. | Maximilian Merkert
|
| Institute for Mathematical Optimization, TU Braunschweig | |
| 4. | Eva Ley
|
| Institute for Mathematical Optimization |
Abstract
We investigate the partial inverse knapsack problem. In this NP-hard bilevel optimization problem, the follower subproblem is a classical 0/1-knapsack problem with fixed item weights and item values, which are determined by the leader. Specifically, the leader problem is a partial inverse problem, i.e., the leader seeks a minimal change to given item values such that there is a follower optimum selecting or discarding items according to two given disjoint subsets. Partial inverse problems appear, e.g., in economic applications when a planner wants to incentivize rational followers to act in a desired way or to estimate unknown parameters in a model to (partially) explain certain observations such as market agent behavior. Based on a single-level mixed-integer formulation for the considered problem, we develop a branch-and-cut solution algorithm that utilizes a new exponential-size class of valid inequalities for the leader. We demonstrate in computational experiments that these cuts allow to reduce the number of iterations and the overall solution time.
Keywords
- Mixed-Integer Programming
- Polyhedral Combinatorics
- Computational Experiments
Status: accepted
Back to the list of papers