Inverse Shortest Path Models Based on Fundamental Cycle Bases

Mikael Call () and Kaj Holmberg ()
Additional contact information
Mikael Call: Link öping University
Kaj Holmberg: Link öping University

A chapter in Operations Research Proceedings 2011, 2012, pp 77-82 from Springer

Abstract: Abstract The inverse shortest path problem has received considerable attention in the literature since the seminal paper by Burton and Toint from 1992. Given a graph and a set of paths the problem is to find arc costs such that all specified paths are shortest paths. The quality of the arc costs is measured by the deviation from some ideal arc costs. Our contribution is a novel modeling technique for this problem based on fundamental cycle bases. For ’LP compatible’ norms we present a cycle basis model equivalent to the LP dual. The LP dual of our cycle basis model is a path based model that only requires a polynomial number of path constraints. This model is valid also for ’LP incompatible’ norms. This yields the first polynomial sized path formulation of the original problem.

Date: 2012
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:oprchp:978-3-642-29210-1_13

Ordering information: This item can be ordered from
http://www.springer.com/9783642292101

DOI: 10.1007/978-3-642-29210-1_13

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().