A Multiscale Primal-Dual Interior-Point Relaxation Method for Large-Scale Optimal Transport Problems

Rui-Jin Zhang; Ruoyu Diao; Shengyu Sun; Yu-Hong Dai

REVIEW 3 major objections 4 minor 40 references

A Multiscale Primal-Dual Interior-Point Relaxation Method for Large-Scale Optimal Transport Problems

T0 review · 3 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims that discrete optimal transport can be solved at grid resolutions whose full LP has trillions of variables, by solving only a chain of sparse subproblems.

desk verdict Strong algorithmic paper that likely makes discrete OT practical at new scale, but the trillion-variable claim rests on an uncertified global dual residual. read the letter →

arxiv 2608.12060 v1 pith:SIHKLLY6 submitted 2026-08-12 math.OC

Shengyu Sun , Rui-Jin Zhang , Ruoyu Diao , Yu-Hong Dai This is my paper · ORCID

classification math.OC MSC 15A0365K0590C0690C08

keywords optimaltransportmultiscalemethodinterior-pointrelaxationsupportidentificationlarge-scalelinearprogrammingSchurcomplementWassersteindistancewarmstart

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Discrete optimal transport between two $2048\times2048$ images has a full linear-programming formulation with about $18$ trillion transport variables, which no single machine can store. This paper claims that a multiscale outer loop can break that barrier: it solves coarse transport problems first, then uses the support of each coarse solution to predict a small set of active variables at the next finer scale, so each fine-scale problem is a sparse subproblem. An interior-point relaxation method serves as the inner solver, and because it accepts non-interior iterates it can warm start directly from the previous subproblem. The paper reports that a $2048\times2048$ instance is solved with about $7.1\times10^7$ active variables and a KKT residual of $7.5\times10^{-7}$. If the sparse-support mechanism holds, high-resolution optimal transport ceases to be a memory-bound problem.

What carries the argument

Two mechanisms carry the argument. The first is the active-set inheritance rule $N^{[0]}_{\ell} = \bigcup_{(p,q)\in\operatorname{spt}(X^*_{\ell+1})} \operatorname{child}(u_{\ell+1,p}) \times \operatorname{child}(v_{\ell+1,q})$, which turns the coarse optimal support into the fine-scale variable set and is the reason the fine LP is small. The second is the primal-dual interior-point relaxation method, whose relaxed variables $z_j = \tfrac12\bigl(\sqrt{(s_j/\rho - x_j)^2 + 4\mu/\rho} - (s_j/\rho - x_j)\bigr)$ let iterates stay outside the interior while still tracing a perturbed central path; the Newton direction is computed through a Schur complement system whose condition number is shown to stay bounded as $\mu\to0$. The analysis connecting them is the support-identification theorem: for small enough $\mu$, the sign of $z_j - \sqrt{\mu/\rho}$ recovers the exact support of the optimal plan.

What would settle it

Run MSIPRM on a cost and marginals where the fine-scale optimal plan must connect cells that are not children of any coarse-scale supporting edge, such as two narrow modes that only come into contact at fine resolution, and count active-set updates and memory growth as the grid is refined; if the active set grows to a large fraction of the full grid or the KKT residual stops improving, the support-inheritance assumption has failed.

Watch

Extended reading notes

Core claim

The paper's central claim is that the optimal transport plan at fine resolution is sparse in a very specific, learnable way: its support is nearly contained in the union of child cells of the support of the coarser plan, so an active set built by that inheritance rule needs only a few enlargements before it contains an optimal solution. The paper argues that IPRM is the appropriate solver for the resulting subproblems, because its barrier augmented Lagrangian formulation replaces the interior-point strict positivity with a smooth relaxation of complementarity, and the perturbed primal-dual pair it traces makes warm starts and support thresholding rigorous. The theoretical part establishes that almost every marginal vector is primal nondegenerate for every connected active set, gives a threshold condition under which inexact IPRM iterates identify the exact support, proves bounded condition numbers for the Schur complement systems, and shows global convergence with error bound $O(\sqrt{\mu})$ plus local quadratic convergence. The numerical part reports that this combination solves instances whose full models contain trillions of variables, keeping the fine-scale active set to about $7.1\times10^7$ variables on a $2048\times2048$ grid.

Load-bearing premise

The load-bearing premise is that the fine-scale optimal transport plan is essentially supported on the child cells of the coarse-scale support, so the active set only needs a few enlargements; if that inheritance fails for a particular cost or marginals, the memory and time advantages of the method shrink.

Editorial extensions

If this is right

The active-set update loop in Algorithm 2 is stated to terminate after finitely many enlargements, enumerating the supporting variables of a full optimal solution, with the objective value nonincreasing at each step.
Almost every marginal vector, in the measure-theoretic sense, makes every feasible connected sparse OT problem primal constraint nondegenerate, which implies uniqueness of the dual optimal solution and a rigorous basis for support identification.
IPRM enjoys a global convergence result with error bound $\operatorname{dist}((x^{(k)},\lambda^{(k)}),\mathcal{S}) \le C\sqrt{\mu^{(k)}}$ and quadratic local convergence under strict complementarity.
The Schur complement systems are provably well conditioned in the limit $\mu\to0$, so the linear algebra at the heart of the solver does not inherit classical IPM ill-conditioning.
Numerically, the method reports solved grid problems up to $2048\times2048$ with full-model sizes around $1.8\times10^{13}$ variables and active sets only a few tens of millions of variables.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Beyond the paper's own claims: if the 2048-by-2048 result is representative, the method makes Wasserstein-2 distances on high-resolution grids essentially routine on a single workstation, which would change how generative models and image barycenters are benchmarked.
The paper leaves implicit that the support-inheritance assumption is the true bottleneck: for costs whose fine-scale structure is invisible at the coarse scale, the active set would need many enlargements and the savings would erode; this can be tested by counting active-set updates on such costs.
The fine-scale overhead reported from evaluating $c - \bar{A}^\top\lambda$ suggests that a parallel evaluation of that residual would directly multiply throughput, an engineering extension the paper does not pursue.
The support-identification threshold $\sqrt{\mu/\rho}$ for $z_j$ is a cheap active-set predictor that could be reused as a warm-start heuristic for other LP solvers outside the multiscale setting.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Matt — read this one. Sun et al. combine the multiscale outer loop from Schmitzer/Oberman-Ruan with their own IPRM inner solver and get real results: 2048x2048 OT instances, 7.1e7 active variables, KKT residual 7.5e-7, on a single machine. If that holds up, it's a genuine step forward for the field. The component-wise novelty is modest, but the integration and the support-identification theory are new. The nondegeneracy theorem (almost every marginal makes every optimal solution primal nondegenerate) is clean, and the Schur complement condition number bounds are useful.

What the paper does well: the multiscale support inheritance works in practice, the active-set updates are simpler than MSSN's, and the warm-starting of IPRM from previous subproblem solutions is natural. The numerical comparisons against HOT, Sp-Sinkhorn, and network simplex are extensive and mostly fair; the 2048x2048 scaling experiment is the headline.

Now the soft spots, in order of severity.

First, the global optimality certificate. The termination criterion KKTres,out includes the dual infeasibility ||(c-A^T lambda)_-||/(1+||c||) over all m*n pairs. For a 2048x2048 grid that is 1.8e13 entries. The paper says cost entries are generated on demand and that the overhead is dominated by evaluating c-A^T lambda, but it never specifies how the maximum violation is found without enumerating everything. If the dual residual is only checked on the active set or a geometrically local candidate set, the reported 7.5e-7 does not certify optimality of the full LP. This matters directly for Proposition 2, which assumes complete knowledge of violated constraints to guarantee finite termination. The stress-test note has this right: it is a verification gap, not just a performance risk.

Second, the local quadratic convergence theorem assumes exact Newton solves and exact Schur complement solves. The implementation uses PCG. That gap is common in the IPM literature, but should be stated cleanly.

Third, no code is released, and some tolerances and parameters (epsilon0, theta1, theta2, chi, IPRM's mu0, rho0, etc.) are not fully specified. That makes the headline experiments hard to reproduce.

None of these sink the paper. The central idea is sound and the experimental evidence is strong. But the trillion-variable claim should be phrased as 'solved to the accuracy certified by our screening procedure' until the global dual residual computation is specified and, ideally, implemented via an exact nearest-neighbor search (the squared Euclidean cost makes that feasible).

Recommendation: send it to review. I'd like to see a revision that releases code, documents the residual evaluation, and reconciles the PCG practice with the exact-Newton theory. Worth citing as the current practical state of the art for large-scale discrete OT.

Referee Report

3 major / 4 minor

Summary. The paper proposes MSIPRM, a multiscale primal-dual interior-point relaxation method for discrete optimal transport. An outer multiscale hierarchy constructs coarse-to-fine OT problems, and at each level the solver restricts optimization to an adaptively refined active set initialized from the previous level's support. The inner solver, IPRM, is the authors' earlier barrier augmented Lagrangian method, which allows non-interior warm starts. The paper derives preprocessing and decomposition routines for sparse subproblems, proves generic primal constraint nondegeneracy, gives support-identification guarantees based on perturbed LP stability, analyzes Schur complement conditioning, and proves global and local convergence results. Numerical experiments compare MSIPRM against HOT, a CPLEX-based multiscale network simplex, Sp-Sinkhorn, and LEMON's network simplex on DOTmark and on synthetic 1024x1024 and 2048x2048 instances, reporting that the full 2048x2048 formulation contains about 1.8e13 variables while MSIPRM keeps about 7.1e7 active variables and reports a KKT residual of 7.5e-7.

Significance. If the reported numerical claims are certified, the paper would be a meaningful advance in practical large-scale discrete OT: it demonstrates that a single-machine solver can handle formulations with trillions of variables, and it outperforms several strong baselines on the tested benchmarks. The theoretical sections also contain solid contributions: Theorem 1 gives a measure-theoretic guarantee of generic primal constraint nondegeneracy, Lemma 4 and Theorem 2 provide support-stability and support-identification results, Proposition 4 gives explicit Schur complement condition-number bounds, and Theorem 4 establishes a global error bound. The proofs in the appendices are detailed and generally self-contained. The main caveats are that the global KKT residual reported at the largest scales is not certified by the manuscript, and the local quadratic convergence theorem assumes exact Newton solves while the implementation uses PCG; both issues are fixable but currently block full verification of the central claims.

major comments (3)

[§3.2, §6.1 (Algorithm 2 and KKTres,out)] The manuscript does not specify a certified procedure for evaluating the global dual-infeasibility term ||(c−Ā^Tλ)_−||/(1+||c||) over all m·n variables. Section 3.2 states only that cost entries are 'generated on demand' to detect violated dual constraints, and Section 6.4 mentions the overhead of evaluating c−Ā^Tλ, but no algorithm is provided for finding the global maximum violation over all pairs, e.g., an exact additively weighted nearest-neighbor query exploiting the separability of C_ij=||u_i−v_j||^2. Consequently, the KKTres,out values in Tables 4–5, including 7.5e-7 at 2048×2048, are not certified in the manuscript as residuals of the full LP; the paper does not establish that they were evaluated globally rather than only on the active set or a screened subset. This gap also affects Proposition 2, whose finite-termination proof requires the sets T_rel and T_abs in Algorithm 2 to be known over all pairs. Please describe the exact global screening procedure used, or explicitly restrict the optimality claims to certified active-set residuals.
[§4.4 and §5 (Theorem 5)] Theorem 5 asserts local quadratic convergence for Algorithm 3, but the proof assumes exact Newton directions. In Section 4.4, however, the Schur complement system (29) is solved either by PCG with preconditioner U or by a direct Cholesky factorization. The PCG option is an inexact linear solve, and the paper gives no stopping criterion or inexact-Newton analysis that would make Theorem 5 applicable to the implemented algorithm. Please either add an inexact-Newton variant of Theorem 5 with explicit accuracy requirements for the PCG iterates, or state clearly that the quadratic-convergence theorem applies only to the direct-factorization variant.
[§4.1, Eq. (15)] The scalability of MSIPRM, and in particular the trillion-variable demonstration in Section 6.4, rests on the support-inheritance assumption encoded in Eq. (15): the fine-scale optimal plan is assumed to be supported essentially on the union of child cells of the coarse-scale support. The paper provides empirical evidence and single-level support-identification results (Lemma 4 and Theorem 2), but no theorem shows that the supports of the exact optimal plans at successive levels are nested under the random cost perturbations in Eq. (14). If this assumption fails, Algorithm 2 would need to introduce many new variables, and the memory and time advantages would shrink. I regard this as a performance risk rather than a correctness error in the reported experiments, but the paper should state it as an explicit assumption and discuss its limits.

minor comments (4)

[§6.1] Please specify how ||c|| is computed in the definition of KKTres,out when the full cost matrix is not stored; the scaling of this term affects the interpretation of the reported residuals.
[Tables 4 and 5] The K–W distance for the same pair at 1024×1024 is 121.61 in Table 4 and 243.13 in Table 5; the footnote explaining the factor-of-two scaling convention should appear at the first occurrence, and the convention should be stated in the main text.
[Appendix C, proof of Lemma 4] The bound on ||A_P^{-1}A_Q|| would be easier to check if the paper explicitly stated that A_P^{-1} is integral because A_P is a nonsingular submatrix of a totally unimodular matrix.
[Table 4] In the rows for Test 1–Test 5 and Test 2–Test 4, the entries '31740.508.3E-07' and '15250.208.4E-07' are missing separators and should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the multiscale integration, support-identification guarantees, and convergence results are derived from stated assumptions and validated against external baselines.

full rationale

The paper's central claims—multiscale active-set construction, support identification (Lemma 4, Theorem 2), Schur complement conditioning (Proposition 4), and global/local convergence (Theorems 4–5)—are either proved in the manuscript or rely on published, parameter-free results (IPRM in [20,38–40]) whose assumptions do not include the target theorem. Equation (15) defines the fine-level initial active set from the coarse-level support, but the paper presents this as an initialization heuristic supported by stability results and numerical evidence, not as a definitional guarantee that the fine support equals the inherited set. The reported KKT residuals and speedups are checked against external solvers (HOT, CPLEX network simplex, Sp-Sinkhorn, LEMON), and the MCPLEX-NS reference used for Gap is a diagnostic with a different inner solver, so the benchmark comparison is not self-referential. The 'trillion-variable' statement is an empirical scalability report rather than a derived equivalence. The reviewer-identified absence of a certified exact search for the global dual-infeasibility maximum at 2048×2048 is a verification/correctness gap in the KKT certificate, not a circular reduction of a prediction to its own fitted input.

Assumptions & free parameters 5 free parameters · 4 assumptions · 0 invented entities

The central claim rests on standard LP/OT theory, a small set of user-chosen algorithmic parameters, and two domain assumptions: generic nondegeneracy and multiscale support inheritance. No new physical or mathematical entities are postulated.

free parameters (5)

epsilon0 = not stated
Mass-imbalance tolerance in Algorithm 1; user-chosen, not fitted to data.
theta1, theta2 = not stated
Active-set growth rates in Algorithm 2; chosen by hand.
chi = not stated
Oversampling factor for relaxed support estimate in Algorithm 4; chosen greater than 1.
IPRM parameters (mu0, rho0, delta, sigma, tau, gamma0, eta) = not stated
Barrier, penalty, and step-size parameters inherited from [20]; values not reported.
inner/outer tolerances tolin/tolout = 1E-8 to 1E-6
KKT stopping tolerances set per resolution level in Section 6.1.

assumptions (4)

domain assumption Primal and dual constraint nondegeneracy hold at optimal solutions of the OT subproblems.
Required by Theorem 2 and Theorem 5; argued to be generic via Theorem 1 and cost perturbation, but not guaranteed for every instance.
domain assumption Fine-scale optimal support is approximated by children of coarse-scale support cells.
Used in Eq. (15) to initialize active sets; supported by stability results [34,25] and Figure 1, but unproven for all costs and marginals.
domain assumption The IPRM convergence theorems of Liu-Dai-Huang [20] apply to the OT subproblems.
The paper imports the inner solver's global and local convergence properties from [20] instead of re-proving them.
standard math Hoffman error bound and total unimodularity of incidence matrices are valid.
Standard results used in Theorem 4 and Lemma 4; cited from [27] and [31].

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Multiscale Primal-Dual Interior-Point Relaxation Method for Large-Scale Optimal Transport Problems." pith.science (2026). https://pith.science/paper/SIHKLLY6

@misc{pith2026260812060,
  author       = {Pith},
  title        = {Pith review of: A Multiscale Primal-Dual Interior-Point Relaxation Method for Large-Scale Optimal Transport Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SIHKLLY6}},
  note         = {Machine review of arXiv:2608.12060}
}

read the original abstract

Large-scale optimal transport (OT) problems involve a vast number of transport variables, leading to prohibitive memory and computational costs. To address these challenges, we propose a multiscale primal-dual interior-point relaxation method (MSIPRM). The multiscale outer framework constructs a hierarchy of standard OT problems at progressively finer levels. At each level, the OT problem is solved over a sequence of adaptively refined active sets initialized based on the solution support at the previous level. This yields a sequence of closely related sparse subproblems, thereby substantially reducing memory requirements. The primal-dual interior-point relaxation method (IPRM) serves as the inner solver for each sparse subproblem. Since IPRM does not require strictly interior iterates, it can readily use the solution of the previous subproblem as a warm start. To efficiently obtain the Newton direction, we solve a reduced Schur complement system derived from the normal equations. Furthermore, we develop an effective support-identification strategy based on the approximate solutions obtained by IPRM. We establish condition number estimates for the Schur complement matrices and analyze the global and local convergence properties of the algorithm. Numerical experiments on large-scale test problems demonstrate the computational efficiency and scalability of MSIPRM and show that it compares favorably with existing solvers. In particular, MSIPRM can handle instances whose full formulations contain trillions of transport variables.

Figures

Figures reproduced from arXiv: 2608.12060 by the authors.

**Figure 2.** An example of the multiscale scheme for a discrete set on an [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗

**Figure 3.** Running-time performance profiles for OT problems at different image resolutions [PITH_FULL_IMAGE:figures/full_fig_p028_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Test measures generated by discretizing two-dimensional probability distributions on a [PITH_FULL_IMAGE:figures/full_fig_p029_4.png]

**Figure 5.** Figure 5: Computational details of MSIPRM for solving an OT problem on a [PITH_FULL_IMAGE:figures/full_fig_p030_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

40 extracted references · 37 canonical work pages

[1]

Andersen, E.D., Ye, Y.: Combining interior-point and pivoting algorithms for linear pro- gramming. Manage. Sci. 42(12), 1719–1731 (1996)

work page 1996
[2]

Auricchio, G., Bassetti, F., Gualandi, S., Veneroni, M.: Computing Kantorovich– Wasserstein distances on d-dimensional histograms using (d + 1) -partite graphs. Adv. Neural Inform. Process. Syst. 31 (2018)

work page 2018
[3]

Benson, H.Y., Shanno, D.F.: An exact primal–dual penalty method approach to warm- starting interior-point methods for linear programming. Comput. Optim. Appl. 38(3), 371–399 (2007)

work page 2007
[4]

Cartis, C., Yan, Y.: Active-set prediction for interior point methods using controlled per- turbations. Comput. Optim. Appl. 63(3), 639–684 (2016)

work page 2016
[5]

Chan, Z.X., Sun, D.: Constraint nondegeneracy, strong regularity, and nonsingularity in semidefinite programming. SIAM J. Optim. 19(1), 370–396 (2008)

work page 2008
[6]

Chen, X., Tran, A.P., Elkin, R., Benveniste, H., Tannenbaum, A.R.: Visualizing fluid flows via regularized optimal mass transport with applications to neuroscience. J. Sci. Comput. 97, 26 (2023)

work page 2023
[7]

Chen, Y.H., Liu, H.: Neural solver for Wasserstein geodesics and optimal transport dy- namics. J. Sci. Comput. 108, 39 (2026)

work page 2026
[8]

Chiappori, P.A., McCann, R.J., Nesheim, L.P.: Hedonic price equilibria, stable matching, and optimal transport: equivalence, topology, and uniqueness. Econ. Theory 42(2), 317– 354 (2010)

work page 2010

Show all 40 references

[9]

European J

Cipolla, S., Gondzio, J., Zanetti, F.: A regularized interior point method for sparse optimal transport on graphs. European J. Oper. Res. 319(2), 413–426 (2024)

2024
[10]

MIT Press, Cambridge, MA (2009)

Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge, MA (2009)

2009
[11]

Cuturi, M.: Sinkhorn distances: Lightspeed computation of optimal transport. Adv. Neural Inform. Process. Syst. 26 (2013)

2013
[12]

Dvurechensky, P., Gasnikov, A., Kroshnin, A.: Computational optimal transport: com- plexity by accelerated gradient descent is better than by Sinkhorn’s algorithm. In: Int. Conf. Mach. Learn., pp. 1367–1376. PMLR (2018)

2018
[13]

INFORMS J

Ge, D., Wang, C., Xiong, Z., Ye, Y.: From an interior point to a corner point: smart crossover. INFORMS J. Comput. 37(6), 1670–1688 (2025)

2025
[14]

In: IEEE Conf

Ge, Z., Liu, S., Li, Z., Yoshie, O., Sun, J.: OTA: Optimal transport assignment for object detection. In: IEEE Conf. Comput. Vis. Pattern Recog., pp. 303–312 (2021)

2021
[15]

Godsil, C., Royle, G.: Algebraic Graph Theory, vol. 207. Springer, New York (2001)

2001
[16]

Gondzio, J., González-Brevis, P.: A new warmstarting strategy for the primal–dual column generation method. Math. Program. 152(1), 113–146 (2015)

2015
[17]

ACM Trans

Hou, D., Liang, L., Toh, K.C.: A sparse smoothing Newton method for solving discrete optimal transport problems. ACM Trans. Math. Softw. 50(3), 1–26 (2024)

2024
[18]

Kovács, P.: Minimum-cost flow algorithms: an experimental evaluation. Optim. Methods Softw. 30(1), 94–127 (2015)

2015
[19]

Liang, L., Sun, D., Toh, K.C.: A squared smoothing Newton method for semidefinite programming. Math. Oper. Res. 50(4), 2873–2908 (2024)

2024
[20]

Liu, X.W., Dai, Y.H., Huang, Y.K.: A primal–dual interior-point relaxation method with global and rapidly local convergence for nonlinear programs. Math. Meth. Oper. Res. 96(3), 351–382 (2022) MSIPRM FOR LARGE-SCALE OPTIMAL TRANSPORT PROBLEMS 39

2022
[21]

Liu, Y.Y., Wen, Z.W., Yin, W.T.: A multiscale semi-smooth Newton method for optimal transport. J. Sci. Comput. 91(2), 39 (2022)

2022
[22]

arXiv preprint arXiv:2407.19689 (2024)

Lu, H., Yang, J.: PDOT: A practical primal–dual algorithm and a GPU-based solver for optimal transport. arXiv preprint arXiv:2407.19689 (2024)

2024 arXiv
[23]

In: Comput

Mérigot, Q.: A multiscale approach to optimal transport. In: Comput. Graph. Forum, vol. 30, pp. 1583–1592. Wiley Online Library (2011)

2011
[24]

Springer, New York (2006)

Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, New York (2006)

2006
[25]

arXiv preprint arXiv:1509.03668 (2015)

Oberman, A.M., Ruan, Y.: An eﬀicient linear programming method for optimal trans- portation. arXiv preprint arXiv:1509.03668 (2015)

2015 arXiv
[26]

Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Math. Program. 58(1), 353–367 (1993)

1993
[27]

Linear Algebra Appl

Robinson, S.M.: Bounds for error in the solution set of a perturbed linear program. Linear Algebra Appl. 6, 69–81 (1973)

1973
[28]

In: Mathematical Programming at Oberwolfach II, pp

Robinson, S.M.: Local structure of feasible sets in nonlinear programming, Part II: Non- degeneracy. In: Mathematical Programming at Oberwolfach II, pp. 217–230. Springer, Berlin, Heidelberg (1984)

1984
[29]

Schmitzer, B.: A sparse multiscale algorithm for dense optimal transport. J. Math. Imaging Vis. 56(2), 238–259 (2016)

2016
[30]

Schmitzer, B.: Stabilized sparse scaling algorithms for entropy regularized transport prob- lems. SIAM J. Sci. Comput. 41(3), A1443–A1481 (2019)

2019
[31]

Wiley Interscience Series in Discrete Mathematics and Optimization

Schrijver, A.: Theory of Linear and Integer Programming. Wiley Interscience Series in Discrete Mathematics and Optimization. Wiley, London (1998)

1998
[32]

Marcel Dekker, New York (2002)

Sierksma, G.: Linear and Integer Programming: Theory and Practice, 2nd edn. Marcel Dekker, New York (2002)

2002
[33]

Tarjan, R.E.: Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm. Math. Program. 78(2), 169–177 (1997)

1997
[34]

Villani, C.: Optimal Transport: Old and New, vol. 338. Springer, Berlin (2008)

2008
[35]

Yildirim, E.A., Wright, S.J.: Warm-start strategies in interior-point methods for linear programming. SIAM J. Optim. 12(3), 782–810 (2002)

2002
[36]

INFORMS J

Zanetti, F., Gondzio, J.: An interior-point-inspired algorithm for linear programs arising in discrete optimal transport. INFORMS J. Comput. 35(5), 1061–1078 (2023)

2023
[37]

IEEE Trans

Zhang, G., Gu, Z., Yuan, Y., Sun, D.: HOT: an eﬀicient Halpern accelerating algorithm for optimal transport problems. IEEE Trans. Pattern Anal. Mach. Intell. 47(8), 6703–6714 (2025)

2025
[38]

Zhang, R.J., Liu, X.W., Dai, Y.H.: IPRQP: a primal–dual interior-point relaxation algo- rithm for convex quadratic programming. J. Global Optim. 87(2), 1027–1053 (2023)

2023
[39]

Zhang, R.J., Liu, X.W., Dai, Y.H.: IPRSDP: a primal–dual interior-point relaxation algo- rithm for semidefinite programming. Comput. Optim. Appl. 88(1), 1–36 (2024)

2024
[40]

Zhang, R.J., Wang, Z.W., Liu, X.W., Dai, Y.H.: IPRSOCP: a primal–dual interior-point relaxation algorithm for second-order cone programming. J. Oper. Res. Soc. China 14(1), 1–31 (2026)

2026

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.

[1] [1]

Andersen, E.D., Ye, Y.: Combining interior-point and pivoting algorithms for linear pro- gramming. Manage. Sci. 42(12), 1719–1731 (1996)

work page 1996

[2] [2]

Auricchio, G., Bassetti, F., Gualandi, S., Veneroni, M.: Computing Kantorovich– Wasserstein distances on d-dimensional histograms using (d + 1) -partite graphs. Adv. Neural Inform. Process. Syst. 31 (2018)

work page 2018

[3] [3]

Benson, H.Y., Shanno, D.F.: An exact primal–dual penalty method approach to warm- starting interior-point methods for linear programming. Comput. Optim. Appl. 38(3), 371–399 (2007)

work page 2007

[4] [4]

Cartis, C., Yan, Y.: Active-set prediction for interior point methods using controlled per- turbations. Comput. Optim. Appl. 63(3), 639–684 (2016)

work page 2016

[5] [5]

Chan, Z.X., Sun, D.: Constraint nondegeneracy, strong regularity, and nonsingularity in semidefinite programming. SIAM J. Optim. 19(1), 370–396 (2008)

work page 2008

[6] [6]

Chen, X., Tran, A.P., Elkin, R., Benveniste, H., Tannenbaum, A.R.: Visualizing fluid flows via regularized optimal mass transport with applications to neuroscience. J. Sci. Comput. 97, 26 (2023)

work page 2023

[7] [7]

Chen, Y.H., Liu, H.: Neural solver for Wasserstein geodesics and optimal transport dy- namics. J. Sci. Comput. 108, 39 (2026)

work page 2026

[8] [8]

Chiappori, P.A., McCann, R.J., Nesheim, L.P.: Hedonic price equilibria, stable matching, and optimal transport: equivalence, topology, and uniqueness. Econ. Theory 42(2), 317– 354 (2010)

work page 2010