Function: [flag, x, y, h] = verlinprog (A, b, c)

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:

verified optimum

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,

verified unbounded

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,

verified feasible

x is verified to enclose a primal feasible solution (neither optimality nor unboundedness could be verified), y, h are empty,

verified infeasible

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,

no verified result

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