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

Partial inverse combinatorial optimization problems are bilevel optimization problems in which the leader aims to incentivize the follower to include respectively not include given sets of elements in the solution of their combinatorial problem. If the sets of required and forbidden elements define a complete follower solution and the follower problem is solvable in polynomial time, then the inverse combinatorial problem is also solvable in polynomial time. In contrast, partial inverse problems can be NP-complete when the follower problem is solvable in polynomial time. This applies e.g. to the partial inverse min cut problem. 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, we show that the partial inverse shortest path problem on a directed acyclic graph is NP-complete. Moreover, the partial inverse assignment problem is NP-complete. Both results even hold if there is only one required arc or edge, respectively. 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, we use auxiliary problems that are basically complete inverse problems on similar instances. 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.