TL;DR
This paper introduces Tulip, a new open-source interior-point solver for linear optimization written in Julia. Tulip's key innovation is its modular design, which decouples the core algorithm from linear algebra, enabling seamless integration of specialized routines for structured problems and the use of arbitrary precision arithmetic. This flexibility leads to competitive performance on general problems and significant speedups on structured instances, outperforming commercial solvers.
What Problem Does This Paper Address?
Linear programming (LP) is a fundamental tool in optimization, underpinning many advanced techniques like mixed-integer programming and decomposition methods. While interior-point methods (IPMs) are highly effective for solving LPs, their performance can be significantly impacted by the efficiency of their underlying linear algebra routines, especially when dealing with problems exhibiting specific structures (e.g., block-angular matrices common in stochastic programming or decomposition). Furthermore, many modern optimization tasks require high precision arithmetic or face numerical challenges with standard double-precision solvers. Existing IPMs often lack the flexibility to easily incorporate specialized linear algebra or handle extended precision, leading to a "two-language problem" where developers must switch to lower-level languages for performance-critical tasks. This paper addresses these challenges by developing a modular, flexible, and robust IPM solver.
Methods
Tulip is built on a regularized homogeneous interior-point algorithm. This approach is chosen for its ability to handle unbounded and infeasible problems, providing certificates of infeasibility which are crucial for decomposition methods. The algorithm incorporates multiple centrality corrections to improve convergence.
The core innovation lies in Tulip's modular design, achieved through Julia's multiple dispatch. This allows the algorithmic framework to be completely disentangled from:
- Linear algebra implementations: Users can plug in different linear algebra solvers without modifying the core IPM logic.
- Model arithmetic: Tulip can operate with arbitrary precision arithmetic (e.g., quadruple precision) by simply changing the data type.
For structured problems, Tulip leverages this modularity to integrate specialized linear algebra routines. This involves defining custom matrix types and solver interfaces that exploit the problem's specific structure, such as the block-angular form common in Dantzig-Wolfe decomposition.
Datasets
The paper evaluates Tulip on several datasets:
- H. Mittelmann's benchmark of barrier LP solvers: A collection of 43 medium to large-scale general LP instances.
- Structured problems from Dantzig-Wolfe decomposition:
- Distributed Energy Resources (DER) coordination instances: Generated from a specific problem setup with varying numbers of resources and time horizons.
- Two-stage stochastic programming (TSSP) problems: Instances with at least 1,000 scenarios.
- Numerically problematic instances: A subset of 6 instances from the Mittelmann benchmark that required more than 100 IPM iterations, used to test extended precision capabilities.
Key Insights and Ideas
- Modularity is key: Decoupling the IPM algorithm from linear algebra and arithmetic is a powerful design principle that enables flexibility, extensibility, and easier integration of specialized solvers.
- Julia's strengths shine: Julia's multiple dispatch and high-level syntax with high performance make it an ideal language for developing such modular optimization software, avoiding the "two-language problem."
- Homogeneous IPMs for robustness: The use of a homogeneous interior-point algorithm is beneficial for handling infeasible/unbounded problems, which are common in decomposition contexts.
- Structure exploitation pays off: Specialized linear algebra routines for structured problems can yield dramatic speedups, even outperforming commercial solvers on large-scale instances.
- Extended precision as a debugging and robustness tool: The ability to easily switch to higher precision arithmetic is invaluable for diagnosing numerical issues and solving problems that are ill-conditioned in standard precision.
Key Results
- General LP instances: Tulip is competitive with other open-source IPM solvers when using generic sparse linear algebra.
- Structured LP instances (Dantzig-Wolfe decomposition): Specialized linear algebra routines for block-angular master problems resulted in a tenfold speedup on large and dense instances, outperforming state-of-the-art commercial solvers like CPLEX, Gurobi, and Mosek.
- Extended precision: Tulip successfully solved previously problematic instances (e.g.,
neos2,ns1688926) in quadruple precision, often with a significant reduction in IPM iterations and overall solve time, demonstrating its robustness. For example, thens1688926instance was solved significantly faster in double-double precision than in standard double precision.
Limitations and Future Work
- Limitations:
- The current implementation is single-threaded, although external linear algebra libraries may exploit multiple threads.
- Free variables are handled by reformulation, which can introduce numerical instability.
- While Tulip can solve problems in extended precision, it's not positioned as a competitive tool for this purpose but rather as a prototyping/debugging aid due to the performance cost.
- Future Work:
- Investigate the use of iterative methods for solving linear systems.
- Develop more general structured linear algebra routines and their multi-threaded implementations.
- Explore more efficient algorithmic techniques for solving problems in extended precision.
- The paper suggests that algorithmic improvements aimed at reducing the number of IPM iterations could further enhance Tulip's performance.
Summary updated