 |
LINE Solver (C++)
Templated C++ port of the LINE queueing solver
|
|
LINE Solver (C++)
Templated C++ port of the LINE queueing solver
|
A sparse LP backend for line::lp::LpModel, on HiGHS (MIT). More...
Go to the source code of this file.
Namespaces | |
| namespace | line |
| namespace | line::lp |
Functions | |
| bool | line::lp::highs_available () |
| True when a sparse backend is compiled in. | |
| template<class T> | |
| LpSolution< T > | line::lp::lp_solve (const LpModel< T > &model, std::size_t dense_max_cols=512) |
| Solve, choosing the backend by arithmetic and size. | |
A sparse LP backend for line::lp::LpModel, on HiGHS (MIT).
WHY IT EXISTS. util/simplex.h carries a DENSE tableau. That is the right choice for what it was written for – it is exact under line::Rational, uses Bland's rule with no tolerance, and needs no dependency – but it costs O(rows * cols) per pivot, so it clears a few hundred columns and stalls on a few thousand. The QRF blocking bounds are MR * B^2 columns (mapqn_qr_bounds_bas.h) and B^2 (mapqn_qr_bounds_rsrd.h), which is 3894 for even example_bas_small.m and tens of thousands for the paper instances. This backend is what makes those reachable.
IT IS NOT A REPLACEMENT, AND MUST NOT BECOME ONE. HiGHS is double precision. Four headers in this tree promise that at T = line::Rational the returned value is the EXACT optimum of the exact polytope, and the mapqn tests assert that as equalities on fractions (3/4, 2/3, 3/7, 6/7), not as tolerances. Routing Rational here would silently turn those equalities into rounding. So the dispatcher below refuses any T other than double, at compile time.
PRESOLVE IS LEFT ON but the caller should know it exists: the QRF equality blocks are heavily redundant (matlab/lib/qrf/qrf_independent_rows.m selects a maximal independent subset by pivoted QR precisely because linprog struggles otherwise), and presolve is what absorbs that redundancy here. If a model ever comes back Infeasible where the dense solver says Optimal, re-run it with presolve off before believing the answer – that is the analogue of the adaptive_rho trap recorded for the OSQP-backed bounds in _kb.
Definition in file lp_highs.h.
1.18.0