2861. A Branch-and-Bound Scheme for a Class of Partial Inverse Combinatorial Optimization Problems
Invited abstract in session TD-4: Robust and Multi-Level Optimization, stream MINLP.
Tuesday, 14:30-16:00Room: 1001 (building: 202)
Authors (first author is the speaker)
| 1. | Maximilian Merkert
|
| Institute for Mathematical Optimization, TU Braunschweig | |
| 2. | Eva Ley
|
| Institute for Mathematical Optimization |
Abstract
We consider partial inverse optimization problems, which are bilevel optimization problems in which the leader aims to incentivize the follower to include a given set of elements in the solution of their combinatorial problem. For solving partial inverse combinatorial optimization problems with only weight increases, we present a new branch-and-bound scheme.
In this talk, we focus on the partial inverse shortest path problem with only weight increases. Branching on follower variables, the scheme relies on two different methods that are basically complete inverse shortest path problems on similar graphs, which are known to be solvable in polynomial time. Computational experiments suggest that for dense graphs our branch-and-bound scheme outperforms an MPCC reformulation as well as a decomposition scheme.
Keywords
- Branch and Cut
- Combinatorial Optimization
- Game Theory
Status: accepted
Back to the list of papers