5 papers
On the Computational Complexity of Bilevel Integer Linear Programming
Nagisa Sugishita, Margarida Carvalho
We investigate the computational complexity of bilevel integer linear programming. While Jeroslow~(1985) established that the decision version of this problem is -complete…
Intermediate Bilevel Optimization: Modeling Endogenous Follower Tie-Breaking Behavior
Maria Bazotte, Margarida Carvalho, Thibaut Vidal
In bilevel optimization, optimistic and pessimistic follower behaviors are the most commonly used forms to define how the follower ties-breaks among multiple optimal solutions. In…
Price of Coupling in Multilevel Linear Programming
Nagisa Sugishita, Margarida Carvalho
Multilevel programming is the standard framework for modeling hierarchical decision-making. In this paper, we characterize the computational complexity of deciding the existence of…
Decision Problems in Multilevel Linear Programming
Nagisa Sugishita, Margarida Carvalho
We study the computational complexity of decision problems in -level linear programming (LP). Seminal work by Jeroslow establishes that determining whether the optimal objective…
On the completeness of several fortification-interdiction games in the Polynomial Hierarchy
Alberto Boggio Tomasaz, Margarida Carvalho, Roberto Cordone +1
Fortification-interdiction games are tri-level adversarial games where two opponents act in succession to protect, disrupt and simply use an infrastructure for a specific purpose.…