#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:
----------------------------------+-----------------------------------------
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_add_only_new_constraints_to_lp_using_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]
This patch depends on #11588.
--
Comment(by john_perry):
I just noticed that the patch included depends on the patch for #11588
(copying a linear program), and changed the description to reflect this.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11606#comment:20>
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.
