simplex.h File Reference

Templated primal simplex with Bland's rule. More...

#include <cstddef>
#include <string>
#include <vector>
#include "line/num/number.h"
#include "line/util/error.h"

Include dependency graph for simplex.h:

Go to the source code of this file.

Classes
struct	line::lp::LpSolution< T >
class	line::lp::LpModel< T >
	Sparse LP in the natural form, with per-variable bounds. More...

Namespaces
namespace	line
namespace	line::lp

Enumerations
enum class	line::lp::LpStatus { line::lp::Optimal , line::lp::Infeasible , line::lp::Unbounded , line::lp::IterationLimit }
	Outcome of a solve. More...
enum class	line::lp::LpSense { line::lp::LE , line::lp::EQ , line::lp::GE }
	Row relation. More...

Functions
const char *	line::lp::lp_status_name (LpStatus s)
template<class T>
T	line::lp::simplex_tolerance ()
template<class T>
LpSolution< T >	line::lp::simplex_solve (const LpModel< T > &model, std::size_t max_iterations=0)
	Solve the model.

Detailed Description

Templated primal simplex with Bland's rule.

Solves max (or min) c'x subject to A x <= b, Aeq x = beq, l <= x <= u where l and u are per-variable and either bound may be absent.

Why this exists: the mapqn quadratic-reduction bounds are linear programs whose optimum IS the bound being reported. MATLAB reaches it with interior-point linprog and lands a few digits short (see the MATLAB accuracy note in matlab/lib/qrf/mapqn_bnd_qr_ld.m); the JAR reaches it with Apache Commons SimplexSolver in double precision. Instantiated at line::Rational this solver is EXACT: rational data implies a rational optimum, every pivot is a field operation on rationals, and the reported bound is the vertex value with no rounding anywhere. That is the point of the port, so the pivoting rule must not depend on a tolerance.

Bland's rule is what makes that possible. It selects the lowest-index column with a strictly favourable reduced cost and, among the rows attaining the minimum ratio, the one whose basic variable has the lowest index. That pair of rules is enough to prove finite termination with no anti-cycling perturbation and no tolerance, which is why the solver is NOT gated on num_traits<T>::has_transcendental: it uses only +, -, *, / and comparison, all of which Rational supports exactly. At inexact T a small tolerance is used for the sign tests, purely so that round-off does not report a favourable reduced cost that is really zero; at exact T the tolerance is exactly zero and no such fudge exists.

Variable bounds are handled by the solver itself, not by the caller:

• l_j == u_j the variable is substituted out (fixed), which is what makes the mapqn assembly tractable, since its ZERO1/2/3 families fix the majority of variables at zero;
• l_j finite x_j = l_j + y_j with y_j >= 0, and a finite u_j becomes one extra row y_j <= u_j - l_j;
• l_j absent, u_j given x_j = u_j - y_j with y_j >= 0;
• both absent x_j = y_j^+ - y_j^- with both parts >= 0. Callers therefore never need to add explicit 0 <= x <= 1 rows the way the JAR must for Apache SimplexSolver (see the mapqn note in _kb/03-api-layer.md); they call set_bounds and the rows appear internally only where a finite upper bound actually needs one.

Assembly is sparse. LpModel accumulates a row in a dense scratch vector with a touched-index list and emits only the nonzeros, so building the mapqn LPs costs O(nnz) memory rather than the O(rows*cols) a dense builder would need. Repeated add() on the same column accumulates, matching the row(idx) = row(idx) + v idiom the MATLAB reference uses.

The tableau itself is dense: it holds B^{-1}[A I] explicitly. This is a deliberate scope choice – the port targets small and medium instances where exactness is the objective, not the large blocking instances that need a sparse revised simplex with LU updates.

Definition in file simplex.h.