ERGO-Code
Simple convex QP cannot be solved
Hi all, I'm interfacing the HiGHS QP solver with my solver Uno, and while running a trust-region SQP method on the instance nlp-cvx-expr/110_010 from the MINLPTests.jl benchmark, I encountered a simple convex QP that cannot be solved:
using JuMP, HiGHS
model = Model(HiGHS.Optimizer)
@variable(model, -10 <= x <= 10)
@variable(model, -10 <= y <= 10)
@objective(model, Min, x^2/2 + x)
@constraint(model, 0*x + 0*y <= 1)
optimize!(model)
produces
Running HiGHS 1.11.0 (git hash: 364c83a51e): Copyright (c) 2025 HiGHS under MIT licence terms
QP has 1 rows; 2 cols; 0 matrix nonzeros; 2 Hessian nonzeros
Coefficient ranges:
Cost [1e+00, 1e+00]
Bound [1e+01, 1e+01]
RHS [1e+00, 1e+00]
Iteration Objective NullspaceDim
0 40.00001 0 0.01s
100 -0.49999495 1 0.01s
200 -0.49999495 1 0.01s
300 -0.49999495 1 0.01s
400 -0.49999495 1 0.01s
500 -0.49999495 1 0.01s
600 -0.49999495 1 0.01s
700 -0.49999495 1 0.01s
800 -0.49999495 1 0.01s
900 -0.49999495 1 0.01s
1000 -0.49999495 1 0.01s
2000 -0.49999495 1 0.01s
3000 -0.49999495 1 0.01s
4000 -0.49999495 1 0.01s
5000 -0.49999495 1 0.01s
6000 -0.49999495 1 0.01s
7000 -0.49999495 1 0.02s
8000 -0.49999495 1 0.02s
9000 -0.49999495 1 0.02s
10000 -0.49999495 1 0.02s
20000 -0.49999495 1 0.03s
30000 -0.49999495 1 0.03s
40000 -0.49999495 1 0.04s
50000 -0.49999495 1 0.05s
60000 -0.49999495 1 0.05s
70000 -0.49999495 1 0.06s
80000 -0.49999495 1 0.07s
90000 -0.49999495 1 0.08s
100000 -0.49999495 1 0.08s
200000 -0.49999495 1 0.16s
300000 -0.49999495 1 0.23s
400000 -0.49999495 1 0.31s
500000 -0.49999495 1 0.39s
600000 -0.49999495 1 0.46s
700000 -0.49999495 1 0.54s
800000 -0.49999495 1 0.61s
900000 -0.49999495 1 0.69s
1000000 -0.49999495 1 0.77s
2000000 -0.49999495 1 1.52s
3000000 -0.49999495 1 2.27s
4000000 -0.49999495 1 3.01s
5000000 -0.49999495 1 3.77s
6000000 -0.49999495 1 4.51s
...
Obviously the QP looks a bit weird (the constraint is trivially satisfied and the y variable doesn't appear in the objective). But I assumed that, because y is bounded, the solver would return an arbitrary finite value for y.
Note that I'm using the HiGHS C++ interface. Hope you can figure this one out :)
Thank you,
Charlie
I can reproduce this:
#include "interfaces/highs_c_api.h"
#include <stdlib.h>
#include <assert.h>
int main(int argc, char *argv[]) {
void* highs = Highs_create();
assert(Highs_addCol(highs, 1.0, -2.0, 2.0, 0, NULL, NULL) == 0);
assert(Highs_addCol(highs, 0.0, -2.0, 2.0, 0, NULL, NULL) == 0);
assert(Highs_addRow(highs, 0.0, 0.0, 0, NULL, NULL) == 0);
int start[2] = {0, 1};
int index[1] = {0};
double value[1] = {1.0};
int format = kHighsHessianFormatTriangular;
assert(Highs_passHessian(highs, 2, 1, format, start, index, value) == 0);
assert(Highs_run(highs) == 0);
Highs_destroy(highs);
return 0;
}
Thanks @cvanaret
My C++ reproduces this, and triggers an assert with HiGHS compiled in debug
So, the assert was a red herring, and I now reproduce the behaviour in debug.
It would appear to be doing in active set QP, the equivalent of cycling in simplex.
I've not got time to dig into the QP solver to identify how this can be avoided. Maybe the constraint coefficients being zero is a trigger.