#18466: Optimal dual solution of LP from MixedIntegerLinearProgram
---------------------------+---------------------------------------
Reporter: Rudi | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-wishlist
Component: numerical | Keywords: Linear optimization
Merged in: | Authors:
Reviewers: | Report Upstream: N/A
Work issues: | Branch:
Commit: | Dependencies:
Stopgaps: |
---------------------------+---------------------------------------
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.
In MixedIntegerLinearProgram it is possible to assign a name to constraint
and so, to point out dual variables. The following would resolve this
ticket:
{{{
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.}
}}}
Right now, MixedIntegerLinearProgram 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.
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:
{{{
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.}
}}}
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.
{{{
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 )
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/18466>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
