Sage: Ticket #18466: Optimal dual solution of LP from MixedIntegerLinearProgram
https://trac.sagemath.org/ticket/18466
<p>
Currently, there is no direct way to access the optimal dual solution of a linear optimization problem.
Dual solutions are used for analysing the sensitivity of the optimal solution, and also for column generation.
</p>
<p>
In <a class="missing wiki">MixedIntegerLinearProgram?</a> it is possible to assign a name to constraint and so, to point out dual variables. The following would resolve this ticket:
</p>
<pre class="wiki">sage: LP=MixedIntegerLinearProgram()
sage: x = LP.new_variable()
sage: LP.set_objective(4*x[1]+5*x[2])
sage: LP.add_constraint( x[1]+2*x[2] <= 7, name = 'first' )
sage: LP.add_constraint( 2*x[1]+x[2] <= 5, name = 'second' )
sage: LP.solve()
19.0
sage: LP.get_values(x)
{1: 1. , 2: 3.}
sage: LP.get_dual_values()
{'first': 2. , 'second': 1.}
</pre><p>
Right now, <a class="missing wiki">MixedIntegerLinearProgram?</a> is already a terrific piece of work. But this enhancement would eliminate the need for me to use another interface to LP solvers, in all but few cases.
</p>
<p>
I cannot properly estimate how much extra work it would be to realise, but if the dual variables behaved as dictionaries, just like the current primal variables, the interface would be even more convenient. In my dreams, the following works:
</p>
<pre class="wiki">sage: LP=MixedIntegerLinearProgram()
sage: x = LP.new_variable()
sage: y = LP.new_dual_variable(nonnegative = True)
sage: LP.set_objective(4*x[1]+5*x[2])
sage: LP.add_constraint( x[1]+2*x[2] <= 7, id = y[1] )
sage: LP.add_constraint( 2*x[1]+x[2] <= 5, id = y[2] )
sage: LP.solve()
19.0
sage: LP.get_values(x)
{1: 1. , 2: 3.}
sage: LP.get_values(y)
{1: 2. , 2: 1.}
</pre><p>
It would be nice as well to have a method for changing the coefficient of variable x[i] in constraint y[j], a method to add a whole column to the constraint matrix, and a method for creating the dual.
</p>
<pre class="wiki">sage: LP[x[2],y[1]]= 3
sage: LP.add_dual_constraint(y[1]+7*y[2] == 4, id = x[3])
sage: LP.dual()
Mixed Integer Program ( minimization, 2 variables, 3 constraints )
</pre>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/18466
Trac 1.1.6mkoeppeWed, 15 Jun 2016 04:47:45 GMTcc changed
https://trac.sagemath.org/ticket/18466#comment:1
https://trac.sagemath.org/ticket/18466#comment:1
<ul>
<li><strong>cc</strong>
<em>mkoeppe</em> added; <em>ncohen</em> removed
</li>
</ul>
TicketdcoudertThu, 28 Nov 2019 15:27:15 GMTcc changed
https://trac.sagemath.org/ticket/18466#comment:2
https://trac.sagemath.org/ticket/18466#comment:2
<ul>
<li><strong>cc</strong>
<em>dcoudert</em> added
</li>
</ul>
<p>
I agree that this would be a nice addition, but we should also get a way to extend a constraint (add a variable).
</p>
Ticket