EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
696. A regularized interior point method for sparse optimal transport on graphs
Invited abstract in session TC-38: Modern techniques for network optimization, stream Conic Optimization: Theory, Algorithms, and Applications.
Tuesday, 12:30-14:00Room: 34 (building: 306)
Authors (first author is the speaker)
| 1. | Filippo Zanetti
|
| School of Mathematics, University of Edinburgh | |
| 2. | Jacek Gondzio
|
| School of Mathematics, University of Edinburgh | |
| 3. | Stefano Cipolla
|
| School of Mathematical Sciences, University of Southampton |
Abstract
In this talk, we address the solution of optimal transport problems using Interior Point Methods (IPM). We propose two approaches which exploit the expected sparsity of the optimal solution to enhance the efficiency of the numerical linear algebra required to solve the Newton system.
The first approach deals with classical optimal transport over dense bipartite graphs, enforcing sparsity of the intermediate approximations by means of a column-generation-like approach. The numerical experiments show that this method can achieve scalable results for very large problems.
The second approach deals with optimal transport over sparse graphs, using a proximal stabilized interior point method. The induced primal-dual regularization allows to use sparsified versions of the normal equations to inexpensively generate IPM search directions. The proposed method, despite a potential high level of inexactness in the Newton direction, retains the polynomial complexity of standard IPMs, for suitable choices of the sparsification parameters. Numerical results show that this approach is efficient and robust for large scale problems, and can outperform classical graph algorithms like network simplex and cost scaling.
Keywords
- Interior Point Methods
- Convex Optimization
- Network Flows
Status: accepted
Back to the list of papers