Drake's solver wrappers do not support constraints with repeated variables

[mpetersen94]

What happened?

If a linear constraint (and potentially other constraints) has a repeated variable, it causes Gurobi to fail to solve with the error condition 'num_gurobi_linear_constraints == num_gurobi_linear_constraints_expected' failed. A test that demonstrates this failure can be found here.

Relates #18076

Version

42448c0af1b39f0c46f760e7ae37d77097689ad3

What operating system are you using?

Ubuntu 20.04

What installation option are you using?

compiled from source code using Bazel

Relevant log output

No response

[mpetersen94]

In the previous issue @hongkai-dai suggested Binding should throw on construction when a variable is repeated. I agree with Russ that it would be better if repeated variables was supported. I don't think that would require a major rewrite of the solvers. While investigating this bug, I passed the same optimization to Mosek and CSDP, neither of which complained about the repeated variable. Hopefully they are more indicative of how the solvers handle repeated variables.

[RussTedrake]

While properly supporting it is my preference, of course throwing on construction is unquestionably better than failing mysteriously.

[hongkai-dai]

While investigating this bug, I passed the same optimization to Mosek and CSDP, neither of which complained about the repeated variable. Hopefully they are more indicative of how the solvers handle repeated variables.

In MosekSolver is fine because I reparsed the linear expression in https://github.com/RobotLocomotion/drake/blob/f09225fe9daf29390d371fa520465dce3112dc90/solvers/mosek_solver_internal.cc#L184-L186 to handle potential duplicated entries. But this only applies to linear constraints in Mosek. For other constraints like psd constraint, I can't promise it should work fine with duplicated entries.

How about we do this

1. Temporarily we throw an error in Binding class if the variable contain duplicated entries. We can do this in one PR
2. A sequence of PRs to make sure each solver can handle duplicated entries for every constraints. This can potentially take many PRs.

[RussTedrake]

it's aok with me. it might be interesting to see how many tests fail in master when you add in that throw.

[jwnimmer-tri]

Temporarily we throw an error in Binding class if the variable contain duplicated entries. We can do this in one PR

If we plan to support duplicates on a per-solver-backend basis, then it seems to me like the solvers should be throwing this error, not the Binding itself? If the Binding throws, then no solver can opt-in to allowing this. The Binding could offer helper function(s) for doing the check, but seems like performing the checking should be part of DoSolve?

[hongkai-dai]

I realize that when I create Binding<PositiveSemidefiniteConstraint> on a symmetric matrix variable, this symmetric matrix will contain duplicate entries X(i, j) = X(j, i).

So I think I should not throw an error about duplicated variables when constructing Binding, but fix the solver (with added test examples on duplicated variables)

[hongkai-dai]

@mpetersen94 I found that although with Mosek the code doesn't crash, still the solver result is incorrect if Binding::variables() contain duplicate entries. So GCS might suffer form incorrect results.

[hongkai-dai]

I will file a sequence of PRs to fix the problem for each constraints/costs types in each solver

• [x] Mosek (#18280)
• [x] Gurobi (#18291)
• [x] SCS (#18318)
• [x] CSDP (#18320)
• [x] SNOPT (#18401)
• [x] IPOPT (#18503)
• [ ] NLOPT
• [x] OSQP
• [x] CLP

[RussTedrake]

fwiw -- i just saw a student run into this with snopt.

[hongkai-dai]

I will work on SnoptSolver.