Verified linear programming.
For a real matrix A (full or sparse) and matching real vectors b, c, this function either computes verified optimal solution x, verified dual optimal solution y and verified optimal value h of the linear programming problem
min c’ * x subject to A * x = b, x ≥ 0,
or verifies (in)feasibility, or verifies unboundedness, or yields no verified result. The respective outcome is always described verbally in the variable flag.
Possible values of flag:
x is verified to enclose a primal optimal solution, y is verified to enclose a dual optimal solution, h is verified to enclose the optimal value,
x is verified to enclose a primal feasible solution xo, and y is verified to enclose a vector yo such that the objective tends to -Inf along the feasible half-line {xo + t * yo |t ≥ 0}, h is empty,
x is verified to enclose a primal feasible solution (neither optimality nor unboundedness could be verified), y, h are empty,
y is verified to enclose a Farkas vector yo satisfying A’ * yo ≥ 0, b’ * yo < 0 (whose existence proves primal infeasibility), x, h are empty,
x, y, and h are empty (no verified result could be found).
Complexity: The algorithm solves at most four linear programming problems (independently of the size of the original problem) and uses a verification procedure which runs approximately in O(m³) time, where m = rows (A).
This work was supported by the Czech Republic National Research Program “Information Society”, project 1ET400300415.
See also: linprog.
Package: interval