Abstract
We introduce a class of specially structured linear programming (LP) problems, which has favorable modeling capability for important application problems in different areas such as optimal transport, discrete tomography and economics. To solve these generally large-scale LP problems efficiently, we design an implementable inexact entropic proximal point algorithm (iEPPA) combined with an easy-to-implement dual block coordinate descent method as a subsolver. Unlike existing entropy-type proximal point algorithms, our iEPPA employs a more practically checkable stopping condition for solving the associated subproblems while achieving provable convergence. Moreover, when solving the capacity constrained multi-marginal optimal transport (CMOT) problem (a special case of our LP problem), our iEPPA is able to bypass the underlying numerical instability issues that often appear in the popular entropic regularization approach, since our algorithm does not require the proximal parameter to be very small in order to obtain an accurate approximate solution. Numerous numerical experiments show that our iEPPA is efficient and robust for solving large-scale CMOT problems. The experiments on the discrete tomography problem also highlight the potential modeling power of our model.
Introduction
Linear Programming (LP) remains a cornerstone of modern optimization. However, as datasets grow, problems in fields such as optimal transport and discrete tomography frequently scale into millions of variables. In these high-dimensional regimes, traditional solvers—including Simplex and Interior Point methods—often encounter significant bottlenecks, either exceeding available memory or requiring prohibitive computation time to reach convergence.
To address these challenges, researchers often turn to entropic regularization (e.g., the Sinkhorn algorithm). While these methods are fast, they suffer from a fundamental trade-off: achieving high precision requires an extremely small regularization parameter, which inevitably triggers numerical instability (underflow or overflow). This paper presents the inexact Entropic Proximal Point Algorithm (iEPPA), a framework designed to maintain the speed of regularized approaches while providing the stability and accuracy of traditional solvers.
Methodology
The iEPPA framework is built upon three primary pillars designed to exploit the specific structure of large-scale LP problems:
1. Proximal Point Framework
Rather than solving a single regularized version of the LP problem, iEPPA solves a sequence of subproblems. This iterative approach allows the algorithm to converge to the exact solution of the original LP. Crucially, it does so while maintaining a moderate proximal parameter, thereby avoiding the numerical instability inherent in methods that push the parameter toward zero.
2. Dual Block Coordinate Descent (BCD)
To solve the resulting subproblems, the algorithm operates in the dual mathematical space. The target problems possess a specific structure where constraints are largely non-overlapping (defined in the paper as Assumption 1). This structure allows the BCD method to utilize simple, closed-form formulas, making the subsolver exceptionally fast and memory-efficient.
3. Checkable Stopping Conditions
A core theoretical contribution of this work is the development of a "practically checkable" stopping condition. While many proximal algorithms require subproblems to be solved to a level of precision that is difficult to measure during execution, the authors provide a mathematically rigorous condition that can be easily monitored by a computer in real-time, ensuring both convergence and efficiency.
Experimental Evaluation
The performance of iEPPA was evaluated against state-of-the-art solvers like Gurobi and entropy-based competitors like DyKL across two primary domains:
- Capacity Constrained Multi-marginal Optimal Transport (CMOT): The authors tested synthetic CMOT problems with dimensions reaching up to 98 million variables.
- Discrete Tomography: The model was tasked with reconstructing 256x256 pixel images (including medical scans of lungs and brains) from 1D projections. Unlike standard models that use high-order tensors, this approach represents variables as a matrix, significantly reducing the memory footprint.
Key Results
- Superior Speed: In large-scale 2-marginal transport tests ($7000 \times 14000$), iEPPA outperformed Gurobi by a factor of at least 10.
- Memory Footprint: iEPPA demonstrated high efficiency, requiring only 15GB of RAM for problems where Gurobi required 55GB.
- Numerical Robustness: By utilizing a fixed proximal parameter ($\epsilon = 0.05$), iEPPA reached high-precision KKT residuals ($10^{-5}$) consistently. In contrast, competing entropic methods often failed to reach such precision due to numerical errors.
- Tomographic Accuracy: The algorithm successfully reconstructed complex images from limited data (20 to 80 projections), with the Peak Signal-to-Noise Ratio (PSNR) scaling linearly with the amount of projection data.
Discussion and Limitations
The efficiency of iEPPA is heavily dependent on the structural characteristics of the LP problem, specifically the non-overlapping nature of the constraints. While this structure is prevalent in transport, tomography, and certain economic models, iEPPA is not intended as a universal replacement for general-purpose LP solvers. It is a specialized tool optimized for a specific, albeit broad, class of large-scale problems.
Future research directions include a deeper numerical investigation into the applications of discrete tomography and the extension of the iEPPA+BCD framework to stochastic network problems, which share a compatible mathematical structure.
Conclusion
The iEPPA provides a robust and efficient alternative for solving massive, structured linear programs. By combining the proximal point framework with a dual BCD subsolver and practical stopping conditions, it bypasses the numerical instability of traditional entropic regularization while maintaining a significantly lower memory and computational profile than commercial interior-point solvers.
Summary updated