CVXOPT solver equations handling

[8ac3f0f3-bd13-47e7-baee-523ad1646342]

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.

CC: @dimpase @nathanncohen @ingolfured

Component: linear programming

Keywords: CVXOPT

Issue created by migration from https://trac.sagemath.org/ticket/18572

[dimpase]

comment:1

well, where do we start?

[dimpase]

comment:2

It looks pretty unclear to me how add_constraint interacts with a backend. Some (almost all?) backends don't even have add_constraint implemented...

[dimpase]

comment:3

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 ?

[dimpase]

comment:5

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.

[mkoeppe]

comment:6

this now appears as a testcase on #20323.

[mkoeppe]

comment:7

20424 now.