1237. Branch-and-Cut for Mixed-Integer Programming Games
Invited abstract in session WB-35: MINLP 1, stream Continuous and mixed-integer nonlinear programming: theory and algorithms.
Wednesday, 10:30-12:00Room: Michael Sadler LG15
Authors (first author is the speaker)
| 1. | Aloïs Duguet
|
| Department of Mathematics, Trier University | |
| 2. | Tobias Harks
|
| University of Passau | |
| 3. | Martin Schmidt
|
| Department of Mathematics, Trier University | |
| 4. | Julian Schwarz
|
| University of Passau |
Abstract
Generalized Nash equilibrium problems with mixed-integer variables
form an important class of games in which each player solves a
mixed-integer optimization problem with respect to her own
variables. Those games are hard to solve as they are more general than
both purely continuous games and purely integer games.
In particular, most methods for those two classes are not
applicable to the mixed-integer case.
In this work, we introduce the first branch-and-cut algorithm to
compute exact pure Nash equilibria for different classes of
mixed-integer games with linear constraints. The main idea is to
reformulate the problem of finding Nash equilibria as the problem of
solving a suitable bilevel problem based on the Nikaido--Isoda function.
The proposed branch-and-cut method is applicable to (generalized) Nash
equilibrium problems under reasonable assumptions.
Depending on the specific setting, we use tailored equilibrium or
intersection cuts.
The latter are well-known in mixed-integer linear
optimization and we adapt them to the game setting.
We prove finite termination of the algorithm and present some first
numerical results for knapsack games and capacitated flow games.
Keywords
- Programming, Mixed-Integer
- Game Theory
- Branch and Cut
Status: accepted
Back to the list of papers