# Inverse optimization problems with multiple weight functions

arXiv: https://arxiv.org/abs/2201.03078 · HTML: https://mlsanity.com/paper/2201.03078/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jan 2022.

## Built on by (most cited first, 1 of 1)

- [Matchings, Predictions and Counterfactual Harm in Refugee Resettlement Processes](https://mlsanity.com/paper/2407.13052/) (2024)

## Abstract (arXiv)

We introduce a new class of inverse optimization problems in which an input solution is given together with k linear weight functions, and the goal is to modify the weights by the same deviation vector p so that the input solution becomes optimal with respect to each of them, while minimizing |p|1. In particular, we concentrate on three problems with multiple weight functions: the inverse shortest s-t path, the inverse bipartite perfect matching, and the inverse arborescence problems. Using LP duality, we give min-max characterizations for the ℓ1-norm of an optimal deviation vector. Furthermore, we show that the optimal p is not necessarily integral even when the weight functions are so, therefore computing an optimal solution is significantly more difficult than for the single-weighted case. We also give a necessary and sufficient condition for the existence of an optimal deviation vector that changes the values only on the elements of the input solution, thus giving a unified understanding of previous results on arborescences and matchings.