Partial inverse combinatorial optimization problems 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. If the set of required elements defines a complete follower solution, the inverse combinatorial problem is solvable in polynomial time as soon as this holds true for the follower problem. In contrast, the same is not necessarily true for partial inverse problems, e.g. the partial inverse min cut problem has been shown to be NP-complete. In this paper, we consider partial inverse combinatorial optimization problems in which weights can only be increased. Furthermore, we assume that the lower-level combinatorial problem can be solved as a linear program. In this setting of allowing only weight increases, we show that the partial inverse shortest path problem on a directed acyclic graph is NP-complete even if only a single arc is required to be part of a shortest path. Moreover, the partial inverse assignment problem with a single required edge is NP-complete. For solving partial inverse combinatorial optimization problems with only weight increases, we present a novel branch-and-bound scheme that exploits the difference in complexity between complete inverse and partial inverse versions of a problem. For both primal heuristics and node relaxations, our scheme uses auxiliary problems that are basically complete inverse problems on similar instances, while branching is done on follower variables. We test our approach on partial inverse shortest path, assignment and min cut problems, and computationally compare it to an MPCC reformulation as well as a decomposition scheme.

## Article

Download

View Solution methods for partial inverse combinatorial optimization problems in which weights can only be increased