#11606: simplify constraints in linear programs
----------------------------------+-----------------------------------------
Reporter: john_perry | Owner: ncohen
Type: enhancement | Status: needs_info
Priority: major | Milestone: sage-4.7.2
Component: linear programming | Keywords: sd32
Work_issues: | Upstream: N/A
Reviewer: | Author: john_perry
Merged: | Dependencies:
----------------------------------+-----------------------------------------
Changes (by ncohen):
* status: needs_review => needs_info
Comment:
Hello John !
I was thinking again about what I told you by email : in order to simplify
constraints more efficiently, one could add the constraints to a Set
object when adding it to the solvers, and add a new constraint only when
it is not already included in the set. The search is then much more
efficient, and handled by Python. If you also want to test for constraints
which may be formaly different (i.e. the original constraint multiplied by
two), you but have to insert the "normalized" constraint in the set
instead of the one which is given.
This would mean doubling in memory the size of the stored constraints, as
it would mean that the LP constraint's are remembered both by the backend
and by a Set object in the MILP class, but this is also what is happening
right now when returning the list of all constraints. This could also be
rewritten as an interator to avoid the cost of memory, then again have no
idea how large your LP can be, but perhaps if you have many constraints
this Set trick would help you much more.
In this case, the simplify_constraints would be a parameter of the
MixedntegerLinearProgram __init__ method, so that the Set object is
created and maintained from beginning to end when the user asks the
constraints to be simplified.
Well, my two cents `:-)`
athann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11606#comment:5>
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 post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
