ERGO-Code
QP solver infinite loop
For the following very simple QP, the solver gets into an infinite loop
#include "Highs.h" int main() { HighsModel model; HighsLp& lp = model.lp_; HighsHessian& hessian = model.hessian_; lp.num_col_ = 2; lp.num_row_ = 2; lp.col_cost_ = {0, 1}; lp.col_lower_ = {0, 0}; lp.col_upper_ = {kHighsInf, kHighsInf}; lp.a_matrix_.start_ = {0, 2, 4}; lp.a_matrix_.index_ = {0, 1, 0, 1}; lp.a_matrix_.value_ = {800, 400, 1, 1}; lp.row_lower_ = {40000, 30000}; lp.row_upper_ = {kHighsInf, kHighsInf}; hessian.dim_ = lp.num_col_; hessian.start_ = {0, 1, 1}; hessian.index_ = {0}; hessian.value_ = {6}; Highs highs; highs.passModel(model); highs.setOptionValue("time_limit", 0.1); highs.run(); exit(1); }
It also exposes a bug when the time limit is reached for a QP
The loop arises as the QP solver wrongly thinks that the search direction in the second iteration doesn't have curvature (p'Qp is less than a threshold) and thus oversteps. It is fixed by tightening the threshold in computemaxsteplength() in quass.cpp to e.g. 10E-8. I'll need to check whether this potential fix negatively impacts any other instances. I'll also move the hard coded threshold into a solver setting.
What's the issue with the time limit?
I think the time limit is just that the solver doesn't terminate until it hits the time limit.
We don't necessarily need to fix the tolerance (the model is arguably poorly scaled), but if it starts to cycle ideally we should detect that and terminate.
The QP solver stops OK on the time limit, but the next level of HiGHS doesn't handle the situation correctly
That's for me to fix
I'll see what I can do. Detecting overstepping (objective getting worse) is easy, Detecting a loop of length 2 should be doable, but arbitrary length loops without objective change takes massive housekeeping to detect
The simplex solvers have a system for identifying cycling - written by @lgottwald - that hashes a basis to see whether there is a possible repetition. Still non-trivial, though
Tightening the tolerance doesn't appear to break any other QP instances. I'll leave cycle detection for when I'm done with my dissertation