LP warm-started via setBasis returns status Optimal with a solution that is not the basic solution of its own returned basis
Version: official v1.15.1 release binary and current latest (6dd8b97) behave bit-identically. Deterministic, 10 of 10 runs, ~0.25 s per run.
Summary
A pure LP (11877 rows, 21553 cols). Solved cold it returns Optimal at 818203670.005, which two independent solvers and a from-text KKT recomputation confirm as the optimum. Warm-started with a basis that Highs_setBasis accepts (returns kOk), the same library on the same file returns Optimal at 818203761.820, which is 91.81 dearer (relative 1.1e-7, but the objective coefficients reach 2.4e7, so this is far above tolerance dust). My understanding is that an LP's optimum does not depend on the starting basis.
Reproducer
warmstart-reproducer.zip, warmstart-basis.txt (column and row status arrays, one line each, numeric HighsBasisStatus codes), hbasis-replay.c.txt (readModel, setBasis, run; ~40 lines of logic). All options at defaults.
hbasis-replay warmstart-wrong-optimal.mps /dev/null warmstart-basis.txt -> Optimal 818203761.81996739 (2654 iters) WRONG
hbasis-replay warmstart-wrong-optimal.mps /dev/null - -> Optimal 818203670.00500774 (3201 iters) correct
The basis is one our application constructs from a related prior solve: 2595 basic columns plus 3656 basic rows, so 6251 basic in an 11877-row LP. It is alien in exactly the sense HighsBasis documentation permits, and Highs_setBasis accepts it with kOk.
Why the Optimal result is false
HiGHS's own info reports max_primal_infeasibility 1.09e-11 and dual infeasibility and complementarity exactly 0. Recomputing from the MPS text and the returned solution instead: one row is violated by 1.17e-05, and 100 basic columns have reduced costs up to 0.025 when z = c - A'y is formed from HiGHS's own returned row duals (a basic column must have z = 0). The same checker run on the cold solution is clean, which validates its conventions.
The defect is in the returned values, not the pivoting
Feeding the warm solve's FINAL basis (from Highs_getBasis) to a fresh Highs instance certifies Optimal in 0 iterations at the correct objective 818203670.005. So the warm-started solve does reach an optimal basis. What it returns alongside that basis is stale: the entire 91.81 discrepancy is a single basic column with cost 7.8e6 reported at 1.17493e-05 where the true basic solution of that basis has it at 0 (plus knock-on drift through 80 related columns; the products c_j times the value error sum to exactly 91.81496). The same 1.17e-05 appears as the row residual above. Every returned nonbasic value does sit on its status bound, so the drift is confined to basic values, and the internal feasibility and KKT checks evidently measure against the same drifted values, which is why nothing trips.
Discriminators (all measured on this input, default options unless stated)
- dual simplex (default) from the supplied basis: wrong, 818203761.820
dual_simplex_cost_perturbation_multiplier=0, same basis: correctsimplex_strategy=4 (primal), same basis: correct- logical basis via setBasis (all rows basic): correct
- supplied column statuses with logical rows: correct
- logical columns with supplied row statuses: correct
- cold: correct
So the failure needs the joint structure of this under-complete alien basis together with the dual simplex path with cost perturbation active.
As stated previously, I know the model is badly scaled (costs 1e-6 to 2.4e7; HiGHS warns on load). The range is inherent to the market rules being modelled and is what I have to work with. Hostile numerics can excuse slow progress or a degraded path, but not an internally inconsistent solution and basis pair certified Optimal at default tolerances, with the library's own KKT report showing zeros while the true residuals are 6 orders larger.
Suggested direction
After termination from an alien start, recompute the primal values from the final factorization before reporting (the 0-iteration re-solve proves the correct values are available at that basis), or invalidate the value state carried out of the alien-basis completion. I will try to create a PR with a fix.
LP warm-started via setBasis returns status Optimal with a solution that is not the basic solution of its own returned basis
Version: official v1.15.1 release binary and current
latest(6dd8b97) behave bit-identically. Deterministic, 10 of 10 runs, ~0.25 s per run.Summary
A pure LP (11877 rows, 21553 cols). Solved cold it returns Optimal at 818203670.005, which two independent solvers and a from-text KKT recomputation confirm as the optimum. Warm-started with a basis that
Highs_setBasisaccepts (returns kOk), the same library on the same file returns Optimal at 818203761.820, which is 91.81 dearer (relative 1.1e-7, but the objective coefficients reach 2.4e7, so this is far above tolerance dust). My understanding is that an LP's optimum does not depend on the starting basis.Reproducer
warmstart-reproducer.zip, warmstart-basis.txt (column and row status arrays, one line each, numeric HighsBasisStatus codes), hbasis-replay.c.txt (readModel, setBasis, run; ~40 lines of logic). All options at defaults.
The basis is one our application constructs from a related prior solve: 2595 basic columns plus 3656 basic rows, so 6251 basic in an 11877-row LP. It is alien in exactly the sense
HighsBasisdocumentation permits, andHighs_setBasisaccepts it with kOk.Why the Optimal result is false
HiGHS's own info reports max_primal_infeasibility 1.09e-11 and dual infeasibility and complementarity exactly 0. Recomputing from the MPS text and the returned solution instead: one row is violated by 1.17e-05, and 100 basic columns have reduced costs up to 0.025 when z = c - A'y is formed from HiGHS's own returned row duals (a basic column must have z = 0). The same checker run on the cold solution is clean, which validates its conventions.
The defect is in the returned values, not the pivoting
Feeding the warm solve's FINAL basis (from
Highs_getBasis) to a fresh Highs instance certifies Optimal in 0 iterations at the correct objective 818203670.005. So the warm-started solve does reach an optimal basis. What it returns alongside that basis is stale: the entire 91.81 discrepancy is a single basic column with cost 7.8e6 reported at 1.17493e-05 where the true basic solution of that basis has it at 0 (plus knock-on drift through 80 related columns; the products c_j times the value error sum to exactly 91.81496). The same 1.17e-05 appears as the row residual above. Every returned nonbasic value does sit on its status bound, so the drift is confined to basic values, and the internal feasibility and KKT checks evidently measure against the same drifted values, which is why nothing trips.Discriminators (all measured on this input, default options unless stated)
dual_simplex_cost_perturbation_multiplier=0, same basis: correctsimplex_strategy=4(primal), same basis: correctSo the failure needs the joint structure of this under-complete alien basis together with the dual simplex path with cost perturbation active.
As stated previously, I know the model is badly scaled (costs 1e-6 to 2.4e7; HiGHS warns on load). The range is inherent to the market rules being modelled and is what I have to work with. Hostile numerics can excuse slow progress or a degraded path, but not an internally inconsistent solution and basis pair certified Optimal at default tolerances, with the library's own KKT report showing zeros while the true residuals are 6 orders larger.
Suggested direction
After termination from an alien start, recompute the primal values from the final factorization before reporting (the 0-iteration re-solve proves the correct values are available at that basis), or invalidate the value state carried out of the alien-basis completion. I will try to create a PR with a fix.