RobotLocomotion
CLP Fails to Solve Simple QP
What happened?
ClpSolver cannot solve the following very simple QP:
from pydrake.all import ClpSolver, ClarabelSolver, MathematicalProgram
prog = MathematicalProgram()
x = prog.NewContinuousVariables(2)
prog.AddLinearConstraint(x[0] + x[1] == 1)
prog.AddBoundingBoxConstraint(0, 1, x[1])
prog.AddQuadraticErrorCost(1, [-0.1, 0], x)
solver = ClpSolver()
result = solver.Solve(prog)
print(result.is_success())
solver = ClarabelSolver()
result = solver.Solve(prog)
print(result.is_success())
Version
No response
What operating system are you using?
No response
What installation option are you using?
No response
Relevant log output
CLP is excluded from ChooseBestSolver for QPs because it tripped a valgrind error (#14933). The example prints a warning:
>>> result = solver.Solve(prog)
WARNING:drake:Currently CLP solver has a memory issue when solving a QP. The user should be aware of this risk.
I am not sure if the memory error is still present (we've upgraded CLP since then), but that could be one explanation.
I would say the primary bug is that our documentation says that CLP cannot solve QPs but yet it claims that it can at runtime, which seems like it's a consequence of not following up on #14933 and the TODO in #15541. Until we decide one way or other other whether it's supposed to work, we can't tell whether the expected behavior here should have been "solve it and return true" or "throw an exception that QPs are not supported".
I would suggest that this example is strong evidence that CLP cannot solve QPs. Happy to PR a change to make it not claim it can solve QPs at runtime.
(And if so, would it be a breaking change? Bugfix? Would it need to follow the deprecation schedule?)
On the other hand, CLP has a bunch of QP unit tests in solvers/test/clp_solvers_test.cc which are passing.
I'll use #22988 to see whether the valgrind report is still a problem.
Edit: No longer a problem.
Here's a C++ version of the test, that can be added into solvers/test/clp_solvers_test.cc. This really is a very simple and obviously feasible QP, so either CLP can't be trusted to solve QPs, or there's a bug somewhere in the parsing.
GTEST_TEST(ClpSolverTest, QuadraticProgram22985) {
MathematicalProgram prog;
auto x = prog.NewContinuousVariables(2);
prog.AddLinearConstraint(x[0] + x[1] == 1);
prog.AddBoundingBoxConstraint(0, 1, x[1]);
prog.AddQuadraticErrorCost(1, Eigen::Vector2d(-0.1, 0), x);
ClpSolver solver;
auto result = solver.Solve(prog, {}, {});
EXPECT_TRUE(result.is_success());
}
I've tried to investigate this a little further. Looks like CLP returns the solution status 10, which may be the secondary status described here?
Regardless, I think we should probably be including a more detailed warning if the user tries to solve a QP with CLP. Right now, we just say
WARNING:drake:Currently CLP solver has a memory issue when solving a QP. The user should be aware of this risk.
(which seems to no longer be the case per #22988), but says nothing about the fact that it may straight up return the wrong answer. I'm happy to make that PR.
(Really, I think we shouldn't allow solving QPs with CLP at all, but it seems the jury is still out on that question.)
FWIW: #247 claims there is an issue with the presolver when solving QPs in CLP and this program is trivial to pre-solve x0 away. I haven't actually looked that this is the issue, but I wouldn't be surprised if it is.
I tried disabling the presolve by setting dblParam_[ClpPresolveTolerance] to 0 (or even -1) in ClpModel.cpp, but it still failed. So it seems like the presolve might not be the problem.
Sorry for the late reply. I will write the optimization program in CLP native API, not through Drake, and then reproduce the error so that we can report on CLP upstream.
I can reproduce the problem using CLP native code without using Drake's code. I filed the issue in CLP upstream https://github.com/coin-or/Clp/issues/316
BTW, we do have a warning inside ClpSolver when the user attempts to solve a QP with CLP https://github.com/RobotLocomotion/drake/blob/23c696b59ea3739dbfc21e5b9701735781b71165/solvers/clp_solver.cc#L37C1-L41C47
Thank you for filing the issue upstream!
BTW, we do have a warning inside ClpSolver when the user attempts to solve a QP with CLP
Yes, I added that warning in #23199.
Yes, I added that warning in https://github.com/RobotLocomotion/drake/pull/23199.
Ah I see, thank you very much for adding the warning, very helpful!
As suggested by the CLP author https://github.com/coin-or/Clp/issues/316#issuecomment-3096258927, we could switch to the most up-to-date CLP.