Sage: Ticket #11606: simplify constraints in linear programs
https://trac.sagemath.org/ticket/11606
<p>
<a class="missing wiki">MixedIntegerLinearProgram?</a> doesn't notice when it is given constraints that already exist in the program, or that are constant multiples. A simple example:
</p>
<pre class="wiki">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)
</pre><p>
Notice that the same constraint appears 10 different times.
</p>
<p>
Apply:
</p>
<ul><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/11606/trac_11606_add_only_new_constraints_to_lp_using_sets.patch" title="Attachment 'trac_11606_add_only_new_constraints_to_lp_using_sets.patch' in Ticket #11606">trac_11606_add_only_new_constraints_to_lp_using_sets.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/11606/trac_11606_add_only_new_constraints_to_lp_using_sets.patch" title="Download"></a>
</li></ul><p>
This patch depends on <a class="closed ticket" href="https://trac.sagemath.org/ticket/11588" title="defect: copying a linear program crashes Sage (closed: fixed)">#11588</a>.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/11606
Trac 1.1.6john_perrySun, 24 Jul 2011 22:19:48 GMT
https://trac.sagemath.org/ticket/11606#comment:1
https://trac.sagemath.org/ticket/11606#comment:1
<p>
To emphasize the need for this, in a sample application I'm working on, the number of constraints is decreased by an order of magnitude (93 vs. 787); in larger systems the different would likely be much larger.
</p>
Ticketjohn_perryTue, 23 Aug 2011 07:51:20 GMTattachment set
https://trac.sagemath.org/ticket/11606
https://trac.sagemath.org/ticket/11606
<ul>
<li><strong>attachment</strong>
set to <em>trac_11606_add_only_new_constraints_to_lp.patch</em>
</li>
</ul>
Ticketjohn_perryTue, 23 Aug 2011 08:04:19 GMTstatus changed; author set
https://trac.sagemath.org/ticket/11606#comment:2
https://trac.sagemath.org/ticket/11606#comment:2
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>author</strong>
set to <em>john_perry</em>
</li>
</ul>
<p>
The attached file is a first attempt at solving the problem. An optional argument, <code>check_redundant</code>, which defaults to <code>False</code>, is used to control whether to invoke the change. If so:
</p>
<ul><li>it proceeds row by row of the constraint matrix
</li><li>it checks whether the same variables are nonzero
</li><li>if so, it computes the ratio <code>r</code> between the coefficients of the "leading" variables
</li><li>if it is negative, add the constraint
</li></ul><blockquote>
<blockquote>
<p>
(if <code>r</code> is negative, the constraint is not so obviously redundant)
</p>
</blockquote>
</blockquote>
<ul><li>if the ratio of the lower & upper bounds disagrees with <code>r</code>, add the constraint
</li><li>now check the ratio of the remaining variables in the current row; if it differs from <code>r</code>, add the constraint
</li></ul><p>
This is meant to be a preliminary implementation rather than an efficient implementation; the best option is probably to visit the matrix & compare, but this would require going into each back end, which is probably a bad idea right now.
</p>
TicketkcrismanTue, 23 Aug 2011 14:57:05 GMTcc set
https://trac.sagemath.org/ticket/11606#comment:3
https://trac.sagemath.org/ticket/11606#comment:3
<ul>
<li><strong>cc</strong>
<em>ncohen</em> added
</li>
</ul>
Ticketjohn_perryThu, 25 Aug 2011 19:31:32 GMTkeywords set
https://trac.sagemath.org/ticket/11606#comment:4
https://trac.sagemath.org/ticket/11606#comment:4
<ul>
<li><strong>keywords</strong>
<em>sd32</em> added
</li>
</ul>
TicketncohenWed, 31 Aug 2011 11:18:32 GMTstatus changed
https://trac.sagemath.org/ticket/11606#comment:5
https://trac.sagemath.org/ticket/11606#comment:5
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
<p>
Hello John !
</p>
<p>
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.
</p>
<p>
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.
</p>
<p>
In this case, the simplify_constraints would be a parameter of the <a class="missing wiki">MixedntegerLinearProgram?</a> <span class="underline">init</span> method, so that the Set object is created and maintained from beginning to end when the user asks the constraints to be simplified.
</p>
<p>
Well, my two cents <code>:-)</code>
</p>
<p>
athann
</p>
Ticketjohn_perryWed, 31 Aug 2011 14:00:01 GMT
https://trac.sagemath.org/ticket/11606#comment:6
https://trac.sagemath.org/ticket/11606#comment:6
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11606#comment:5" title="Comment 5">ncohen</a>:
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
I had thought of this, too. I think the only reason I didn't do it at the time is a law I've seen attributed to David Knuth: premature optimization is the root of all evil. I can certainly try it.
</p>
<blockquote class="citation">
<p>
This could also be rewritten as an interator to avoid the cost of memory...
</p>
</blockquote>
<p>
I'm not quite following how to do this.
</p>
<blockquote class="citation">
<p>
then again have no idea how large your LP can be...
</p>
</blockquote>
<p>
Hard data: a problem that exhausted memory on a 4GB machine a month ago computed yesterday in about 40MB.
</p>
<blockquote class="citation">
<p>
In this case, the simplify_constraints would be a parameter of the <a class="missing wiki">MixedntegerLinearProgram?</a> <span class="underline">init</span> method, so that the Set object is created and maintained from beginning to end when the user asks the constraints to be simplified.
</p>
</blockquote>
<p>
I'll try that, thanks.
</p>
TicketncohenThu, 01 Sep 2011 16:19:23 GMT
https://trac.sagemath.org/ticket/11606#comment:7
https://trac.sagemath.org/ticket/11606#comment:7
<blockquote class="citation">
<blockquote class="citation">
<p>
This could also be rewritten as an interator to avoid the cost of memory...
</p>
</blockquote>
<p>
I'm not quite following how to do this.
</p>
</blockquote>
<p>
Oh. For the moment your patch returns a list of tuples, representing the constraints. Instead of that (which requires to build the whole list first, then to return it, thus doubling the memory cost), python can return the list element by element using the "yield" keyword. This would avoid doubling the memory, especially if you just want to check something for each constraint returned.
</p>
Ticketjohn_perryThu, 01 Sep 2011 17:57:49 GMT
https://trac.sagemath.org/ticket/11606#comment:8
https://trac.sagemath.org/ticket/11606#comment:8
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11606#comment:7" title="Comment 7">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<blockquote class="citation">
<p>
This could also be rewritten as an interator to avoid the cost of memory...
</p>
</blockquote>
<p>
I'm not quite following how to do this.
</p>
</blockquote>
<p>
Oh. For the moment your patch returns a list of tuples, representing the constraints. Instead of that (which requires to build the whole list first, then to return it, thus doubling the memory cost), python can return the list element by element using the "yield" keyword. This would avoid doubling the memory, especially if you just want to check something for each constraint returned.
</p>
</blockquote>
<p>
Are you thinking of <a class="closed ticket" href="https://trac.sagemath.org/ticket/11607" title="enhancement: read constraints from linear program (closed: fixed)">#11607</a> here? This patch only affects the return value in one place; it returns <code>None</code>, and then only if the constraint is redundant.
</p>
Ticketjohn_perryThu, 01 Sep 2011 20:41:13 GMT
https://trac.sagemath.org/ticket/11606#comment:9
https://trac.sagemath.org/ticket/11606#comment:9
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11606#comment:5" title="Comment 5">ncohen</a>:
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
I have a working implementation along these lines, but there's one difficulty. In order to normalize the constraint, the code divides by the coefficient of the variable with the smallest index. For example, given the constraint <code>2*x_1-2*x_0<=2</code>, the code converts this to <code>x_1-x_0<=1</code>.
</p>
<p>
In order to do this, I want to use the <code>min()</code> command to determine the smallest non-zero key, determine its coefficient, and divide:
</p>
<pre class="wiki"> i = min(f.keys())
c = f[i]
C = [(v,coeff/c) for (v,coeff) in f.iteritems() if v != -1]
</pre><p>
The problem with this is that <code>min</code> is a parameter to the function, so this provokes an error.
</p>
<p>
I can rename the parameters as <code>min_value</code> and <code>max_value</code>, but this would break people's existing code. Alternately, I can define <code>self._min = min</code> in <code>__init__</code>, and call <code>self._min()</code> where I would ordinarily call <code>min()</code>.
</p>
<p>
I am attaching a patch that uses the latter approach, but if you have suggestions for a better solution, I'm all ears. It wouldn't surprise me if there is one.
</p>
<p>
BTW, does it matter if I use <code>Set</code> or <code>set</code>? You wrote the former, but currently I'm using the latter.
</p>
Ticketjohn_perryThu, 01 Sep 2011 20:43:49 GMTdescription changed
https://trac.sagemath.org/ticket/11606#comment:10
https://trac.sagemath.org/ticket/11606#comment:10
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11606?action=diff&version=10">diff</a>)
</li>
</ul>
Ticketjohn_perryThu, 01 Sep 2011 21:31:49 GMTstatus changed
https://trac.sagemath.org/ticket/11606#comment:11
https://trac.sagemath.org/ticket/11606#comment:11
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
More rigorous testing showed that I had overlooked an issue with the keys (variables whose coefficients are zero). Fixed in the revision of the patch.
</p>
<p>
(Just noticed: it helps if one executes <code>hg qrefresh</code> before <code>hg export tip</code>...)
</p>
Ticketjohn_perryThu, 01 Sep 2011 21:32:24 GMTattachment set
https://trac.sagemath.org/ticket/11606
https://trac.sagemath.org/ticket/11606
<ul>
<li><strong>attachment</strong>
set to <em>trac_11606_simplify_with_sets.patch</em>
</li>
</ul>
TicketncohenFri, 02 Sep 2011 13:58:22 GMTstatus changed
https://trac.sagemath.org/ticket/11606#comment:12
https://trac.sagemath.org/ticket/11606#comment:12
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Hello John ! <code>:-)</code>
</p>
<p>
I really didn't think at first this method would need to use either min or max later on :-)
</p>
<p>
Hopefully, this trick should work :
</p>
<pre class="wiki">from __builtin__ import min as min_function
</pre><p>
Could you also add in the explanation of the check_redundant parameter what is a "redundant" constraint ? Something like "(two constraints are redundant when one can be obtained from the other scalar by multiplication)" or something of the kind ? <code>:-)</code>
</p>
<p>
Oh, and it looks like there are some missing "::" before the beginning of Python code in the doctests, so those will not be properly formatted when building the documentation.
</p>
<pre class="wiki">sage -docbuild reference html
</pre><p>
Two other remarks :
</p>
<ul><li>Set is a Sage version of set, the latter being a purely Python thing. The interest of Set is that it is hashable and immutable, while the "set" can be modified. When you do not need the elements to be immutable, I'm told the best is to use set. And this I was probably told after writing this part <code>:-)</code>
</li></ul><ul><li>I thought that
<pre class="wiki">min( x for x in range(3) if x != 0 )
</pre>would be faster than
<pre class="wiki">min([ x for x in range(3) if x != 0 ])
</pre></li></ul><p>
</p>
<blockquote>
<p>
as you do not create the list first, but it looks like the iterators have a cost too :
</p>
</blockquote>
<pre class="wiki">sage: %timeit min( x for x in range(10000) if x != 0 )
125 loops, best of 3: 5.51 ms per loop
sage: %timeit min([ x for x in range(10000) if x != 0 ])
125 loops, best of 3: 4.56 ms per loop
sage: %timeit min(x for x in range(10) if x != 0)
625 loops, best of 3: 7.41 µs per loop
sage: %timeit min([ x for x in range(10) if x != 0 ])
625 loops, best of 3: 6.81 µs per loop
</pre><p>
Nathann
</p>
Ticketjohn_perryFri, 02 Sep 2011 22:07:47 GMTdescription changed
https://trac.sagemath.org/ticket/11606#comment:13
https://trac.sagemath.org/ticket/11606#comment:13
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11606?action=diff&version=13">diff</a>)
</li>
</ul>
<p>
Alright! The new patch imports <code>min</code> via <code>__builtin__</code>, and fixes those issues with the documentation. The doctests take about twice as long to run on my machine now. :-(
</p>
<p>
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 <code>C</code>, but Cython defied me, claiming that generators weren't acceptable. That's when I noticed that you had placed <em>you</em> definition of <code>C</code> in a list. So, I didn't think to use it in the <code>min_function</code> (maybe I even tried).
</p>
Ticketjohn_perryFri, 02 Sep 2011 22:08:49 GMTstatus changed
https://trac.sagemath.org/ticket/11606#comment:14
https://trac.sagemath.org/ticket/11606#comment:14
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
Ticketjohn_perryFri, 02 Sep 2011 22:13:30 GMT
https://trac.sagemath.org/ticket/11606#comment:15
https://trac.sagemath.org/ticket/11606#comment:15
<p>
By the way, when reading the section on docstring markup in <a href="http://www.sagemath.org/doc/developer/conventions.html#docstring-markup-with-rest-and-sphinx">Conventions for Coding in Sage</a>, I noticed this:
</p>
<blockquote>
<p>
<strong>Warning:</strong> Functions whose names start with an underscore do not currently appear in the reference manual, so avoid putting crucial documentation in their docstrings. In particular, if you are defining a class, you might put a long informative docstring after the class definition, not for the <code>__init__</code> method.
</p>
</blockquote>
<p>
Should we move that documentation out of <code>__init__</code>?
</p>
<p>
(You have to scroll fairly far down to find the warning, or else do a search.)
</p>
Ticketjohn_perryFri, 02 Sep 2011 22:53:42 GMT
https://trac.sagemath.org/ticket/11606#comment:16
https://trac.sagemath.org/ticket/11606#comment:16
<p>
Forgot about copying -- we would want to copy the flag for checking redundancy, as well as the constraints.
</p>
Ticketjohn_perrySat, 03 Sep 2011 00:03:23 GMT
https://trac.sagemath.org/ticket/11606#comment:17
https://trac.sagemath.org/ticket/11606#comment:17
<p>
Forgot about copying <em>sets</em>, not just assigning pointers...
</p>
Ticketjohn_perryMon, 05 Sep 2011 19:14:53 GMTstatus changed
https://trac.sagemath.org/ticket/11606#comment:18
https://trac.sagemath.org/ticket/11606#comment:18
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Something isn't working correctly with the normalization, <strong>sometimes</strong>. I'm trying to figure out what changed that is causing the issue I'm seeing...
</p>
Ticketjohn_perryMon, 05 Sep 2011 19:24:51 GMTstatus changed
https://trac.sagemath.org/ticket/11606#comment:19
https://trac.sagemath.org/ticket/11606#comment:19
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_info</em>
</li>
</ul>
<p>
As I suspected, it's a typing problem. Normalization performs a division, and <code>1/2</code> simplifies to <code>0</code> if <code>1</code> is an <code>int</code>. If <code>1</code> is an <code>Integer</code> or a <code>Rational</code>, then <code>1/2</code> simplifies to a <code>Rational</code>.
</p>
<p>
This strikes me as a matter best left to the client: the normalization shouldn't choose the type of the coefficients of the constraints; it's not even clear we can guess this <em>a priori</em>. So this isn't a bug after all.
</p>
<p>
But, I'd like someone else's opinion.
</p>
Ticketjohn_perryTue, 06 Sep 2011 00:54:09 GMTdescription changed
https://trac.sagemath.org/ticket/11606#comment:20
https://trac.sagemath.org/ticket/11606#comment:20
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11606?action=diff&version=20">diff</a>)
</li>
</ul>
<p>
I just noticed that the patch included depends on the patch for <a class="closed ticket" href="https://trac.sagemath.org/ticket/11588" title="defect: copying a linear program crashes Sage (closed: fixed)">#11588</a> (copying a linear program), and changed the description to reflect this.
</p>
Ticketjohn_perryTue, 06 Sep 2011 00:57:04 GMTdescription changed
https://trac.sagemath.org/ticket/11606#comment:21
https://trac.sagemath.org/ticket/11606#comment:21
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11606?action=diff&version=21">diff</a>)
</li>
</ul>
<p>
Yep, depends on <a class="closed ticket" href="https://trac.sagemath.org/ticket/11607" title="enhancement: read constraints from linear program (closed: fixed)">#11607</a>, too. That can be removed, and I'll do so in the near future.
</p>
TicketncohenThu, 08 Sep 2011 12:11:18 GMT
https://trac.sagemath.org/ticket/11606#comment:22
https://trac.sagemath.org/ticket/11606#comment:22
<blockquote class="citation">
<p>
but Cython defied me, claiming that generators weren't acceptable.
</p>
</blockquote>
<p>
Oops, that's right. The current version of Cython doesn't like generators, this feature should be included in the next Cython release, and I assure you that we have been waiting for generators in Cython for a loooooooong time here. There are patches I haven't written yet \
waiting for that, others that contain as a comment "Change this as soon as we have iterators".. Sigh :-)
</p>
<blockquote class="citation">
<p>
Should we move that documentation out of <span class="underline">init</span>?
</p>
</blockquote>
<p>
Well, the current documentation of the <span class="underline">init</span> method of the <a class="missing wiki">MixedIntegerLinearProgram?</a> class also appears just before, in the section's documentation (and that appears in the doc). But you are right : it's probably best to remove it just to avoid later mistakes.
</p>
<p>
Actually, it should just contain the line "Constructor" and the doctests. The command
</p>
<pre class="wiki">sage -coverage file.pyx
</pre><p>
is a statistic telling you whether all the functions have documentation and tests. It's nice to have around, but that's also why this <span class="underline">init</span> function should have a minimal set of doctests -- so that the output of this software doesn't report that some doc is missing :-)
</p>
<blockquote class="citation">
<p>
This strikes me as a matter best left to the client: the normalization shouldn't choose the type of the coefficients of the constraints
</p>
</blockquote>
<p>
You are right in general, though in this special situation the answer has been taken from us. When a constraint is added, it is forwarded to the solver backend which is the only place where it is saved. Now, all of CPLEX/GLPK/Coin only accept floats as data. As mip.pyx is\
</p>
<blockquote>
<p>
a Cython file, the best is probably to deal with float variables. By the way, why do you create so many lists ? Instead of
</p>
</blockquote>
<pre class="wiki">i = min_function([v for (v,coeff) in f.iteritems() if coeff != 0])
c = f[i]
</pre><p>
What about
</p>
<pre class="wiki">cdef int i = 0
cdef float c
for i, c in f.iteritems():
if c!= 0:
break
</pre><p>
Sorry about the delay again. I'm getting back to the point where I can deal with tasks on-the-fly, and not with the ones that should have been settled the week before :-)
</p>
<p>
Nathann
</p>
Ticketjohn_perryThu, 08 Sep 2011 17:33:45 GMT
https://trac.sagemath.org/ticket/11606#comment:23
https://trac.sagemath.org/ticket/11606#comment:23
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11606#comment:22" title="Comment 22">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Well, the current documentation of the <span class="underline">init</span> method of the <a class="missing wiki">MixedIntegerLinearProgram?</a> class also appears just before, in the section's documentation (and that appears in the doc). But you are right : it's probably best to remove it just to avoid later mistakes.
</p>
<p>
Actually, it should just contain the line "Constructor" and the doctests.
</p>
</blockquote>
<p>
Will do.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
This strikes me as a matter best left to the client: the normalization shouldn't choose the type of the coefficients of the constraints
</p>
</blockquote>
<p>
You are right in general, though in this special situation the answer has been taken from us. When a constraint is added, it is forwarded to the solver backend which is the only place where it is saved. Now, all of CPLEX/GLPK/Coin only accept floats as data. As mip.pyx is a Cython file, the best is probably to deal with float variables.
</p>
</blockquote>
<p>
Are you saying I should coerce everything to floats, or leave it be? I thought to leave it be in case some future back end accepted rationals; the backends can do their own coercion.
</p>
<blockquote class="citation">
<p>
By the way, why do you create so many lists ?
</p>
</blockquote>
<p>
You seem to think I know something about proper P/Cython programming. <code>:-)</code> Thanks for the suggestion; that will help speed things up a bit, though I think my real problem lies elsewhere.
</p>
<blockquote class="citation">
<p>
Sorry about the delay again. I'm getting back to the point where I can deal with tasks on-the-fly, and not with the ones that should have been settled the week before :-)
</p>
</blockquote>
<p>
No problem. I'm in a bit of a fix myself, so it may take a few days before another patch is ready, anyway.
</p>
<p>
By the way, do you know what those colored balls next to "opened: ... weeks ago" mean?
</p>
TicketncohenThu, 08 Sep 2011 18:28:50 GMT
https://trac.sagemath.org/ticket/11606#comment:24
https://trac.sagemath.org/ticket/11606#comment:24
<blockquote class="citation">
<p>
Are you saying I should coerce everything to floats, or leave it be? I thought to leave it be in case some future back end accepted rationals; the backends can do their own coercion.
</p>
</blockquote>
<p>
Well, I think the doubles wouldn't hurt. And I guess it would be the same for rationals if it gets implemented. The constraints in the LP would not change, all that matters is that equivalent constraints get coerced to the same values <code>:-)</code>
</p>
<blockquote class="citation">
<p>
that will help speed things up a bit, though I think my real problem lies elsewhere.
</p>
</blockquote>
<p>
Yep, unfortunately <code>:-)</code>
</p>
<blockquote class="citation">
<p>
By the way, do you know what those colored balls next to "opened: ... weeks ago" mean?
</p>
</blockquote>
<p>
Oh. Did you try clicking on them ? The patches uploaded on a trac ticket are automatically applied and tested on a Sage install, and this ball prints the status of this operation. Browse the other tickets waiting for review and see how it changes <code>;-)</code>
</p>
<p>
Nathann
</p>
Ticketjohn_perryThu, 08 Sep 2011 18:47:01 GMT
https://trac.sagemath.org/ticket/11606#comment:25
https://trac.sagemath.org/ticket/11606#comment:25
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11606#comment:24" title="Comment 24">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Oh. Did you try clicking on them ?
</p>
</blockquote>
<p>
I did, and I don't seem any status of an automatic patch and test. It seems only to summarize the data. Then there's a long horizontal line & white space.
</p>
<p>
The only thing I've noticed is that different patches sometimes have different colors.
</p>
TicketncohenThu, 08 Sep 2011 18:49:29 GMT
https://trac.sagemath.org/ticket/11606#comment:26
https://trac.sagemath.org/ticket/11606#comment:26
<p>
<a class="ext-link" href="http://trac.sagemath.org/sage_trac/ticket/11279"><span class="icon"></span>http://trac.sagemath.org/sage_trac/ticket/11279</a>
</p>
Ticketjohn_perryThu, 08 Sep 2011 21:25:52 GMT
https://trac.sagemath.org/ticket/11606#comment:27
https://trac.sagemath.org/ticket/11606#comment:27
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11606#comment:26" title="Comment 26">ncohen</a>:
</p>
<blockquote class="citation">
<p>
<a class="ext-link" href="http://trac.sagemath.org/sage_trac/ticket/11279"><span class="icon"></span>http://trac.sagemath.org/sage_trac/ticket/11279</a>
</p>
</blockquote>
<p>
???
</p>
TicketncohenFri, 09 Sep 2011 05:43:53 GMT
https://trac.sagemath.org/ticket/11606#comment:28
https://trac.sagemath.org/ticket/11606#comment:28
<p>
(On this ticket the circle is yellow and you will have more complete information if yo click on it)
</p>
Ticketjohn_perryMon, 12 Sep 2011 23:50:51 GMTstatus changed
https://trac.sagemath.org/ticket/11606#comment:29
https://trac.sagemath.org/ticket/11606#comment:29
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
The new patch reflects changes described above.
</p>
Ticketjohn_perryMon, 17 Oct 2011 20:09:47 GMT
https://trac.sagemath.org/ticket/11606#comment:30
https://trac.sagemath.org/ticket/11606#comment:30
<p>
The only change was to rebase the patch against the revised <a class="closed ticket" href="https://trac.sagemath.org/ticket/11607" title="enhancement: read constraints from linear program (closed: fixed)">#11607</a>.
</p>
Ticketjohn_perryTue, 06 Dec 2011 21:44:07 GMT
https://trac.sagemath.org/ticket/11606#comment:31
https://trac.sagemath.org/ticket/11606#comment:31
<p>
<strong>*bump</strong>* any chance of a review?
</p>
TicketncohenWed, 07 Dec 2011 09:24:10 GMT
https://trac.sagemath.org/ticket/11606#comment:32
https://trac.sagemath.org/ticket/11606#comment:32
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/11606#comment:31" title="Comment 31">john_perry</a>:
</p>
<blockquote class="citation">
<p>
<strong>*bump</strong>* any chance of a review?
</p>
</blockquote>
<p>
Rightrightrightright. You did well <code>:-D</code>
</p>
<p>
Nathann
</p>
TicketncohenThu, 08 Dec 2011 00:19:41 GMTstatus changed
https://trac.sagemath.org/ticket/11606#comment:33
https://trac.sagemath.org/ticket/11606#comment:33
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Hellooooooo again !
</p>
<p>
I have less than 30 minutes of battery left but it should be ok <code>:-D</code>
</p>
<p>
So. First, and before anything else, this patch needs to be rebased on the current version of Sage. This patch defines two methods (<code></code>constraints<code></code> and <code></code>number of contraints<code></code>) which have been added by another patch already, so Sage refuses to run when this patch is applied.
</p>
<p>
Short of this, the patch looks good, so once this is settled it should be good to go <code>:-)</code>
</p>
<p>
Nathann
</p>
Ticketjohn_perryWed, 21 Dec 2011 21:32:58 GMTattachment set
https://trac.sagemath.org/ticket/11606
https://trac.sagemath.org/ticket/11606
<ul>
<li><strong>attachment</strong>
set to <em>trac_11606_add_only_new_constraints_to_lp_using_sets.patch</em>
</li>
</ul>
Ticketjohn_perryWed, 21 Dec 2011 21:41:42 GMTstatus changed
https://trac.sagemath.org/ticket/11606#comment:34
https://trac.sagemath.org/ticket/11606#comment:34
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
I have rebased the patch against <code>sage-4.8.alpha4</code>. This patch <strong>no longer</strong> introduces the function <code>constraints()</code> that existed in the previous patch, and that caused the conflict. It does not provoke any doctest failures on my version of <code>sage-4.8.alpha4</code>.
</p>
<p>
However, I did notice that three doctest failures currently occur with <code>sage-4.8.alpha4</code>:
</p>
<pre class="wiki">File "/Applications/sage-4.8.alpha4/devel/sage-main/sage/numerical/mip.pyx", line 523:
sage: p.show()
Expected:
...
File "/Applications/sage-4.8.alpha4/devel/sage-main/sage/numerical/mip.pyx", line 685:
sage: p.write_lp(SAGE_TMP+"/lp_problem.lp")
Exception raised:
...
File "/Applications/sage-4.8.alpha4/devel/sage-main/sage/numerical/mip.pyx", line 322:
sage: p
Expected:
...
</pre><p>
Since these exist in an unpatched <code>sage-4.8.alpha4</code>, they have no bearing on this ticket, but is this a known issue? I'll open a new ticket if not. My machine is a <a class="missing wiki">MacBook?</a> Pro running OSX 10.6.8.
</p>
TicketncohenWed, 21 Dec 2011 21:50:35 GMTstatus, author changed; reviewer set
https://trac.sagemath.org/ticket/11606#comment:35
https://trac.sagemath.org/ticket/11606#comment:35
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Nathann Cohen</em>
</li>
<li><strong>author</strong>
changed from <em>john_perry</em> to <em>John Perry</em>
</li>
</ul>
<p>
Positive review to this patch, which passes all tests ! <code>:-)</code>
</p>
<p>
John, I do not see the errors you mentionned on my alpha4. The fact that the write_lp and p.show return errors lead me to think that you have CBC installed. Is this true ? <code>:-)</code>
Through <a class="missing wiki">OsiCbcSolverInterface?</a>, I did not find how to write those files and some "names" in the structure of a LP were not available (like the "name of the lp", or the "name of the objective function"), and because of that I did not enable the names in the CBc interface. Perhaps this is one of the things that would be fixed by a real interface with Cbc. But anyway, I guess those bugs only appear on your install because of Cbc. They can also be "fixed" by adding "solver= GLPK"in the doctests above.
</p>
<p>
Thank you for this patch ! <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketjdemeyerThu, 22 Dec 2011 16:42:04 GMTmilestone changed
https://trac.sagemath.org/ticket/11606#comment:36
https://trac.sagemath.org/ticket/11606#comment:36
<ul>
<li><strong>milestone</strong>
changed from <em>sage-4.8</em> to <em>sage-5.0</em>
</li>
</ul>
Ticketjohn_perryFri, 23 Dec 2011 15:54:32 GMT
https://trac.sagemath.org/ticket/11606#comment:37
https://trac.sagemath.org/ticket/11606#comment:37
<p>
Weird. I saw jdemeyer's change yesterday, but not ncohen's change two days ago.
</p>
<blockquote class="citation">
<p>
John, I do not see the errors you mentionned on my alpha4. The fact that the write_lp and p.show return errors lead me to think that you have CBC installed. Is this true ? :-)
</p>
</blockquote>
<p>
Bingo!
</p>
<p>
As I see, Cbc is a real problem for us, even though it seems good for me personally... then again, maybe not if I look at it long enough :-(
</p>
TicketncohenFri, 23 Dec 2011 15:57:43 GMT
https://trac.sagemath.org/ticket/11606#comment:38
https://trac.sagemath.org/ticket/11606#comment:38
<blockquote class="citation">
<p>
As I see, Cbc is a real problem for us, even though it seems good for me personally... then again, maybe not if I look at it long enough :-(
</p>
</blockquote>
<p>
Well, if you find out how to solve a MIP using Coin's library without using <a class="missing wiki">OsiCbcSolverInterface?</a>, just let me know. This solver is driving me mad <code>:-p</code>
</p>
<p>
Nathann
</p>
TicketjdemeyerWed, 18 Jan 2012 08:15:46 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/11606#comment:39
https://trac.sagemath.org/ticket/11606#comment:39
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-5.0.beta1</em>
</li>
</ul>
TicketdavidloefflerMon, 12 Mar 2012 17:35:54 GMT
https://trac.sagemath.org/ticket/11606#comment:40
https://trac.sagemath.org/ticket/11606#comment:40
<p>
Apply trac_11606_add_only_new_constraints_to_lp_using_sets.patch
</p>
<p>
(for legacy patchbots running 4.8)
</p>
Ticket