Inverse optimal transport
- Creators
- Stuart, Andrew M.
- Wolfram, Marie-Therese
Abstract
Discrete optimal transportation problems arise in various contexts in engineering, the sciences, and the social sciences. Often the underlying cost criterion is unknown, or only partly known, and the observed optimal solutions are corrupted by noise. In this paper we propose a systematic approach to infer unknown costs from noisy observations of optimal transportation plans. The algorithm requires only the ability to solve the forward optimal transport problem, which is a linear program, and to generate random numbers. It has a Bayesian interpretation and may also be viewed as a form of stochastic optimization. We illustrate the developed methodologies using the example of international migration flows. Reported migration flow data captures (noisily) the number of individuals moving from one country to another in a given period of time. It can be interpreted as a noisy observation of an optimal transportation map, with costs related to the geographical position of countries. We use a graph-based formulation of the problem, with countries at the nodes of graphs and nonzero weighted adjacencies only on edges between countries which share a border. We use the proposed algorithm to estimate the weights, which represent cost of transition, and to quantify uncertainty in these weights.
Additional Information
© 2020 Society for Industrial and Applied Mathematics. Received by the editors May 10, 2019; accepted for publication (in revised form) December 4, 2019; published electronically February 25, 2020. The work of the first author was supported by U.S. National Science Foundation (NSF) under grant DMS 1818977 and by AFOSR grant FA9550-17-1-0185. The work of the second author was partially supported by the Royal Society International Exchanges grant IE 161662. The authors are grateful to Venkat Chandrasekaran for helpful discussions about the literature in inverse linear programming.Attached Files
Published - 19m1261122.pdf
Submitted - 1905.03950.pdf
Files
Name | Size | Download all |
---|---|---|
md5:e88b31aa15cb3eafc63f8ff0ad80aeeb
|
3.9 MB | Preview Download |
md5:7c2df592889914413de54e359a9e85fb
|
3.9 MB | Preview Download |
Additional details
- Eprint ID
- 97307
- Resolver ID
- CaltechAUTHORS:20190722-082837777
- DMS-1818977
- NSF
- FA9550-17-1-0185
- Air Force Office of Scientific Research (AFOSR)
- IE 161662
- Royal Society
- Created
-
2019-07-22Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field