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

Eva Ley () and Maximilian Merkert ()
Additional contact information
Eva Ley: TU Braunschweig
Maximilian Merkert: TU Braunschweig

Journal of Global Optimization, 2025, vol. 93, issue 1, No 9, 263-298

Abstract: Abstract 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.

Keywords: Bilevel optimization; Inverse problems; Mixed-integer programming; Branch and bound; 90C11; 90C27; 90C26; 90C60; 91A65 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-025-01529-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:93:y:2025:i:1:d:10.1007_s10898-025-01529-x

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-025-01529-x

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().