Ahmadian, Sara ;
Bhaskar, Umang ;
Sanità, Laura ;
Swamy, Chaitanya
Algorithms for Inverse Optimization Problems
Abstract
We study inverse optimization problems, wherein the goal is to map given solutions to an underlying optimization problem to a cost vector for which the given solutions are the (unique) optimal solutions. Inverse optimization problems find diverse applications and have been widely studied. A prominent problem in this field is the inverse shortest path (ISP) problem [D. Burton and Ph.L. Toint, 1992; W. BenAmeur and E. Gourdin, 2004; A. Bley, 2007], which finds applications in shortestpath routing protocols used in telecommunications. Here we seek a cost vector that is positive, integral, induces a set of given paths as the unique shortest paths, and has minimum l_infty norm. Despite being extensively studied, very few algorithmic results are known for inverse optimization problems involving integrality constraints on the desired cost vector whose norm has to be minimized.
Motivated by ISP, we initiate a systematic study of such integral inverse optimization problems from the perspective of designing polynomial time approximation algorithms. For ISP, our main result is an additive 1approximation algorithm for multicommodity ISP with nodedisjoint commodities, which we show is tight assuming P!=NP. We then consider the integralcost inverse versions of various other fundamental combinatorial optimization problems, including mincost flow, max/mincost bipartite matching, and max/mincost basis in a matroid, and obtain tight or nearlytight approximation guarantees for these. Our guarantees for the first two problems are based on results for a broad generalization, namely integral inverse polyhedral optimization, for which we also give approximation guarantees. Our techniques also give similar results for variants, including l_pnorm minimization of the integral cost vector, and distanceminimization from an initial cost vector.
BibTeX  Entry
@InProceedings{ahmadian_et_al:LIPIcs:2018:9464,
author = {Sara Ahmadian and Umang Bhaskar and Laura Sanit{\`a} and Chaitanya Swamy},
title = {{Algorithms for Inverse Optimization Problems}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {1:11:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770811},
ISSN = {18688969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9464},
URN = {urn:nbn:de:0030drops94646},
doi = {10.4230/LIPIcs.ESA.2018.1},
annote = {Keywords: Inverse optimization, Shortest paths, Approximation algorithms, Linear programming, Polyhedral theory, Combinatorial optimization}
}
2018
Keywords: 

Inverse optimization, Shortest paths, Approximation algorithms, Linear programming, Polyhedral theory, Combinatorial optimization 
Seminar: 

26th Annual European Symposium on Algorithms (ESA 2018)

Issue date: 

2018 
Date of publication: 

2018 