Opened 4 years ago
Last modified 4 years ago
#18572 new defect
CVXOPT solver equations handling
Reported by: | ptigwe | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.8 |
Component: | linear programming | Keywords: | CVXOPT, linear programming |
Cc: | dimpase, ncohen, ingolfured | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
The CVXOPT
solver doesn't seem to be able to handle equations with ==
properly. For instance, the following example:
p = MixedIntegerLinearProgram(solver='CVXOPT', maximization=False) x = p.new_variable(nonnegative=True) y = p.new_variable(nonnegative=False) p.add_constraint( 2 * x[0] + x[1] - y[0] <= 0) p.add_constraint(x[0] + 3 * x[1] - y[0] <= 0) p.add_constraint(x[0] + x[1] == 1) p.set_objective(y[0]) p.solve() p.get_values(x) {0: 0.26990679350380004, 1: 0.1691067035243196}
The final result shouldn't be a feasible solution considering that x_0 + x_1 == 1
should hold. However substituting the final constraint for
p.add_constraint(1<=x[0] + x[1] <= 1)
works fine.
Change History (7)
comment:1 Changed 4 years ago by
- Cc ncohen added
comment:2 Changed 4 years ago by
It looks pretty unclear to me how add_constraint
interacts with a backend. Some (almost all?) backends don't even have add_constraint
implemented...
comment:3 follow-up: ↓ 5 Changed 4 years ago by
OK, I suppose I see how to fix this. CVXOPT's LP solver needs equations to be put into a separate data structure,. but this was not done in this code.
What I need to understand is how add_linear_constraint
in a backend is supposed to know that it deals with an equation. By comparing lower_bound
and upper_bound
?
comment:4 Changed 4 years ago by
- Cc ingolfured added
comment:5 in reply to: ↑ 3 Changed 4 years ago by
Replying to dimpase:
OK, I suppose I see how to fix this. CVXOPT's LP solver needs equations to be put into a separate data structure,. but this was not done in this code.
What I need to understand is how
add_linear_constraint
in a backend is supposed to know that it deals with an equation. By comparinglower_bound
andupper_bound
?
this is certainly not an optimal way; in fact add_constraint
in mip.pyx
simply throws away the information on whether we have an equation, or not. In general it is not straightforward to get it back, as some loss of precision can happen.
comment:6 Changed 4 years ago by
this now appears as a testcase on #20323.
comment:7 Changed 4 years ago by
#20424 now.
well, where do we start?