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 dimpase

  • Cc ncohen added

well, where do we start?

comment:2 Changed 4 years ago by dimpase

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: Changed 4 years ago by 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 comparing lower_bound and upper_bound ?

comment:4 Changed 4 years ago by dimpase

  • Cc ingolfured added

comment:5 in reply to: ↑ 3 Changed 4 years ago by dimpase

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 comparing lower_bound and upper_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.

Last edited 4 years ago by dimpase (previous) (diff)

comment:6 Changed 4 years ago by mkoeppe

this now appears as a testcase on #20323.

comment:7 Changed 4 years ago by mkoeppe

#20424 now.

Note: See TracTickets for help on using tickets.