Sage: Ticket #18572: CVXOPT solver equations handling
https://trac.sagemath.org/ticket/18572
<p>
The <code>CVXOPT</code> solver doesn't seem to be able to handle equations with <code>==</code> properly. For instance, the following example:
</p>
<pre class="wiki">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}
</pre><p>
The final result shouldn't be a feasible solution considering that <code>x_0 + x_1 == 1</code> should hold. However substituting the final constraint for
</p>
<pre class="wiki">p.add_constraint(1<=x[0] + x[1] <= 1)
</pre><p>
works fine.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/18572
Trac 1.1.6dimpaseMon, 01 Jun 2015 17:33:39 GMTcc changed
https://trac.sagemath.org/ticket/18572#comment:1
https://trac.sagemath.org/ticket/18572#comment:1
<ul>
<li><strong>cc</strong>
<em>ncohen</em> added
</li>
</ul>
<p>
well, where do we start?
</p>
TicketdimpaseMon, 01 Jun 2015 18:32:20 GMT
https://trac.sagemath.org/ticket/18572#comment:2
https://trac.sagemath.org/ticket/18572#comment:2
<p>
It looks pretty unclear to me how <code>add_constraint</code> interacts with a backend. Some (almost all?) backends don't even have <code>add_constraint</code> implemented...
</p>
TicketdimpaseMon, 01 Jun 2015 22:26:27 GMT
https://trac.sagemath.org/ticket/18572#comment:3
https://trac.sagemath.org/ticket/18572#comment:3
<p>
OK, I suppose I see how to fix this. CVXOPT's LP solver needs equations to be put into a
<a class="ext-link" href="http://cvxopt.org/userguide/coneprog.html#linear-programming"><span class="icon"></span>separate data structure</a>,. but this was not done in this code.
</p>
<p>
What I need to understand is how <code>add_linear_constraint</code> in a backend is supposed to know that it deals with an equation. By comparing <code>lower_bound</code> and <code>upper_bound</code> ?
</p>
TicketdimpaseTue, 02 Jun 2015 10:11:46 GMTcc changed
https://trac.sagemath.org/ticket/18572#comment:4
https://trac.sagemath.org/ticket/18572#comment:4
<ul>
<li><strong>cc</strong>
<em>ingolfured</em> added
</li>
</ul>
TicketdimpaseWed, 03 Jun 2015 00:36:35 GMT
https://trac.sagemath.org/ticket/18572#comment:5
https://trac.sagemath.org/ticket/18572#comment:5
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18572#comment:3" title="Comment 3">dimpase</a>:
</p>
<blockquote class="citation">
<p>
OK, I suppose I see how to fix this. CVXOPT's LP solver needs equations to be put into a
<a class="ext-link" href="http://cvxopt.org/userguide/coneprog.html#linear-programming"><span class="icon"></span>separate data structure</a>,. but this was not done in this code.
</p>
<p>
What I need to understand is how <code>add_linear_constraint</code> in a backend is supposed to know that it deals with an equation. By comparing <code>lower_bound</code> and <code>upper_bound</code> ?
</p>
</blockquote>
<p>
this is certainly not an optimal way; in fact <code>add_constraint</code> in <code>mip.pyx</code> 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.
</p>
TicketmkoeppeSun, 10 Apr 2016 07:55:01 GMT
https://trac.sagemath.org/ticket/18572#comment:6
https://trac.sagemath.org/ticket/18572#comment:6
<p>
this now appears as a testcase on <a class="closed ticket" href="https://trac.sagemath.org/ticket/20323" title="enhancement: Common TestSuite for MIP backends (closed: fixed)">#20323</a>.
</p>
TicketmkoeppeWed, 27 Apr 2016 08:31:07 GMT
https://trac.sagemath.org/ticket/18572#comment:7
https://trac.sagemath.org/ticket/18572#comment:7
<p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/20424" title="defect: More tests for common MIP TestSuite: add_col, solve; some fixes for ... (closed: fixed)">#20424</a> now.
</p>
Ticket