Algorithms for inverse optimization problems

Sara Ahmadian, Umang Bhaskar, Laura Sanità, Chaitanya Swamy

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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 [9, 3, 4], which finds applications in shortest-path 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 ℓ 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 1-approximation algorithm for multicommodity ISP with node-disjoint commodities, which we show is tight assuming P ≠ NP. We then consider the integral-cost inverse versions of various other fundamental combinatorial optimization problems, including min-cost flow, max/min-cost bipartite matching, and max/min-cost basis in a matroid, and obtain tight or nearly-tight 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 ℓp-norm minimization of the integral cost vector, and distance-minimization from an initial cost vector.

Original languageEnglish
Title of host publication26th European Symposium on Algorithms, ESA 2018
EditorsHannah Bast, Grzegorz Herman, Yossi Azar
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Print)9783959770811
DOIs
Publication statusPublished - 1 Aug 2018
Externally publishedYes
Event26th European Symposium on Algorithms, ESA 2018 - Helsinki, Finland
Duration: 20 Aug 201822 Aug 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume112
ISSN (Print)1868-8969

Conference

Conference26th European Symposium on Algorithms, ESA 2018
CountryFinland
CityHelsinki
Period20/08/1822/08/18

Keywords

  • Approximation algorithms
  • Combinatorial optimization
  • Inverse optimization
  • Linear programming
  • Polyhedral theory
  • Shortest paths

Fingerprint Dive into the research topics of 'Algorithms for inverse optimization problems'. Together they form a unique fingerprint.

Cite this