#11606: simplify constraints in linear programs
----------------------------------+-----------------------------------------
Reporter: john_perry | Owner: ncohen
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.7.2
Component: linear programming | Keywords: sd32
Work_issues: | Upstream: N/A
Reviewer: | Author: john_perry
Merged: | Dependencies:
----------------------------------+-----------------------------------------
Old description:
> MixedIntegerLinearProgram doesn't notice when it is given constraints
> that already exist in the program, or that are constant multiples. A
> simple example:
> {{{
> sage: lp = MixedIntegerLinearProgram()
> sage: for each in xrange(10):
> ....: lp.add_constraint(lp[0]-lp[1],min=1)
> ....:
> sage: lp.show()
> Maximization:
>
> Constraints:
> 1.0 <= x_0 -x_1
> 1.0 <= x_0 -x_1
> 1.0 <= x_0 -x_1
> 1.0 <= x_0 -x_1
> 1.0 <= x_0 -x_1
> 1.0 <= x_0 -x_1
> 1.0 <= x_0 -x_1
> 1.0 <= x_0 -x_1
> 1.0 <= x_0 -x_1
> 1.0 <= x_0 -x_1
> Variables:
> x_0 is a continuous variable (min=0.0, max=+oo)
> x_1 is a continuous variable (min=0.0, max=+oo)
> }}}
> Notice that the same constraint appears 10 different times.
>
> Apply:
>
> - [attachment:trac_11606_simplify_with_sets.patch]
New description:
MixedIntegerLinearProgram doesn't notice when it is given constraints that
already exist in the program, or that are constant multiples. A simple
example:
{{{
sage: lp = MixedIntegerLinearProgram()
sage: for each in xrange(10):
....: lp.add_constraint(lp[0]-lp[1],min=1)
....:
sage: lp.show()
Maximization:
Constraints:
1.0 <= x_0 -x_1
1.0 <= x_0 -x_1
1.0 <= x_0 -x_1
1.0 <= x_0 -x_1
1.0 <= x_0 -x_1
1.0 <= x_0 -x_1
1.0 <= x_0 -x_1
1.0 <= x_0 -x_1
1.0 <= x_0 -x_1
1.0 <= x_0 -x_1
Variables:
x_0 is a continuous variable (min=0.0, max=+oo)
x_1 is a continuous variable (min=0.0, max=+oo)
}}}
Notice that the same constraint appears 10 different times.
Apply:
-
[attachment:trac_11606_add_only_new_constraints_to_lp_using_sets.patch]
--
Comment(by john_perry):
Alright! The new patch imports `min` via `__builtin__`, and fixes those
issues with the documentation. The doctests take about twice as long to
run on my machine now. :-(
Regarding the iterators: now I understand what you mean. Actually, if
memory serves (and it may deceive -- not sure) I think I tried that when
defining `C`, but Cython defied me, claiming that generators weren't
acceptable. That's when I noticed that you had placed ''you'' definition
of `C` in a list. So, I didn't think to use it in the `min_function`
(maybe I even tried).
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11606#comment:13>
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.
