Sage: Ticket #12716: MILP formulation and test functions for vertex separation
https://trac.sagemath.org/ticket/12716
<p>
This patch implements a MILP formulation for the vertex separation and some test functions for evaluating the width of linear vertex orderings.
</p>
<p>
APPLY:
</p>
<ul><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/12716/trac_12716-combined.patch" title="Attachment 'trac_12716-combined.patch' in Ticket #12716">trac_12716-combined.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/12716/trac_12716-combined.patch" title="Download"></a>
</li></ul>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/12716
Trac 1.1.6dcoudertWed, 21 Mar 2012 14:45:36 GMTstatus changed
https://trac.sagemath.org/ticket/12716#comment:1
https://trac.sagemath.org/ticket/12716#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
<p>
Some functions are not yet implemented. I should may be create them and raise an eror message like 'not yet implemented. Please feel free to contribute'.
</p>
TicketdcoudertSun, 08 Apr 2012 12:58:34 GMTdescription, summary changed
https://trac.sagemath.org/ticket/12716#comment:2
https://trac.sagemath.org/ticket/12716#comment:2
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/12716?action=diff&version=2">diff</a>)
</li>
<li><strong>summary</strong>
changed from <em>Linear orderings of graphs</em> to <em>MILP formulation and test functions for vertex separation</em>
</li>
</ul>
TicketdcoudertSun, 08 Apr 2012 23:09:04 GMTattachment set
https://trac.sagemath.org/ticket/12716
https://trac.sagemath.org/ticket/12716
<ul>
<li><strong>attachment</strong>
set to <em>trac_12716_MILP.patch</em>
</li>
</ul>
TicketdcoudertSun, 08 Apr 2012 23:13:02 GMT
https://trac.sagemath.org/ticket/12716#comment:3
https://trac.sagemath.org/ticket/12716#comment:3
<p>
Correction of doctests since the ordering given by the MILP depends on the system/solver (but the answer is correct).
</p>
<p>
I have also removed lots of white spaces in both files (although one of them is clearly useless) so that patchbot can pass tests successfully.
</p>
TicketdcoudertMon, 09 Apr 2012 10:52:45 GMTattachment set
https://trac.sagemath.org/ticket/12716
https://trac.sagemath.org/ticket/12716
<ul>
<li><strong>attachment</strong>
set to <em>trac_12716_linear_ordering.patch</em>
</li>
</ul>
TicketncohenTue, 10 Apr 2012 15:48:57 GMTattachment set
https://trac.sagemath.org/ticket/12716
https://trac.sagemath.org/ticket/12716
<ul>
<li><strong>attachment</strong>
set to <em>trac_12716-review.patch</em>
</li>
</ul>
TicketncohenTue, 10 Apr 2012 15:57:01 GMTstatus changed
https://trac.sagemath.org/ticket/12716#comment:4
https://trac.sagemath.org/ticket/12716#comment:4
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Helloooooooooo David !!!
</p>
<p>
Here is a small patch to apply on top of yours.. Here is what it does :
</p>
<ul><li>One or two typoes
</li><li>Simplifies the definition of the LP variables... Could you give it a look, just to check I got nothing wrong ? <code>:-)</code>
</li><li>Replaces some lists operation by set operations. Well, it looked like all you wanted to do was more a set thing than a list thing.
</li><li>Replaces some integer = True by binary = True. The solvers (well, except Coin as usual) have specific types for binary variables, so if we know that they are binary we may as well say it.
</li><li>I also moved several lines of code outside of the try/catch, as list operations usually do not throw MIPSolverExceptions
</li></ul><p>
I also have several questions :
</p>
<ul><li>Could you say in the doc which variables are relaxed when integrality=False, and if it has any specific meaning ? Or is it just a lower bound that you use because it is faster ?
</li><li>Is the integrality variable really intended to be False <strong>by default</strong> ? <code>O_o;;;</code>
</li><li>About constraints 5, 6, and 7 : why aren't they all set by "sum of all y[v][t] for all v is equal to t" ? Or rather to t+1 ? I do not get why you do not say so immediately to the solver <code>O_o</code>
</li><li>To me <code></code>u[v][t] >= x[v][t]-y[v][t]<code></code> is rather <code></code>x[v][t] == u[v][t] + y[v][t]<code></code>, which is the same constraint but in a way I find easier to read.. That's one of the remarks I added to the definition of the variables, though <code>:-)</code>
</li></ul><p>
Well, I think that's all I had to say !
</p>
<p>
Nathann
</p>
TicketdcoudertTue, 10 Apr 2012 19:12:44 GMT
https://trac.sagemath.org/ticket/12716#comment:5
https://trac.sagemath.org/ticket/12716#comment:5
<p>
Thanks Nathann for the review.
</p>
<blockquote class="citation">
<p>
I also have several questions :
</p>
<ul><li>Could you say in the doc which variables are relaxed when integrality=False, and if it has any specific meaning ? Or is it just a lower bound that you use because it is faster ?
</li></ul></blockquote>
<p>
Both are optimal. However, in some cases the integral version is faster than the relaxed one. I don't know why.
</p>
<blockquote class="citation">
<ul><li>Is the integrality variable really intended to be False <strong>by default</strong> ? <code>O_o;;;</code>
</li></ul></blockquote>
<p>
Yes, because it is in general faster.
</p>
<blockquote class="citation">
<ul><li>About constraints 5, 6, and 7 : why aren't they all set by "sum of all y[v][t] for all v is equal to t" ? Or rather to t+1 ? I do not get why you do not say so immediately to the solver <code>O_o</code>
</li></ul></blockquote>
<p>
You are right. Changed.
</p>
<blockquote class="citation">
<ul><li>To me <code></code>u[v][t] >= x[v][t]-y[v][t]<code></code> is rather <code></code>x[v][t] == u[v][t] + y[v][t]<code></code>, which is the same constraint but in a way I find easier to read.. That's one of the remarks I added to the definition of the variables, though <code>:-)</code>
</li></ul></blockquote>
<p>
This is certainly easier to read for you, but this is not the standard way to write linear programs. In general, it is better to provide inequalities rather than equalities to solvers for a better description of the polytopes. So I prefer to let this inequality as it is.
</p>
<p>
I have merge the patchs (MILP, review + additional modifications) into a combined patch. I have changed the top table in accordance with those of patch <a class="closed ticket" href="https://trac.sagemath.org/ticket/12816" title="enhancement: Documentation and list of Graph functions (closed: fixed)">#12816</a>.
</p>
<p>
Hope it is better now.
</p>
TicketdcoudertTue, 10 Apr 2012 19:14:21 GMTstatus, description changed
https://trac.sagemath.org/ticket/12716#comment:6
https://trac.sagemath.org/ticket/12716#comment:6
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/12716?action=diff&version=6">diff</a>)
</li>
</ul>
TicketncohenTue, 10 Apr 2012 23:20:26 GMT
https://trac.sagemath.org/ticket/12716#comment:7
https://trac.sagemath.org/ticket/12716#comment:7
<p>
Hellooooooooo !!
</p>
<p>
Well, everything looks nice, doc and code.... But you still mention in the code constraint number 12, which does not exist in the LaTeX formula anymore, and the comment of constraint 9 (in the code) is wrong.... <code>^^;</code>
</p>
<p>
Nathann
</p>
TicketdcoudertWed, 11 Apr 2012 07:47:53 GMTattachment set
https://trac.sagemath.org/ticket/12716
https://trac.sagemath.org/ticket/12716
<ul>
<li><strong>attachment</strong>
set to <em>trac_12716-combined.patch</em>
</li>
</ul>
TicketdcoudertWed, 11 Apr 2012 07:48:31 GMT
https://trac.sagemath.org/ticket/12716#comment:8
https://trac.sagemath.org/ticket/12716#comment:8
<p>
Corrected.
</p>
TicketncohenWed, 11 Apr 2012 07:59:03 GMTstatus changed
https://trac.sagemath.org/ticket/12716#comment:9
https://trac.sagemath.org/ticket/12716#comment:9
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Well, then .... <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketdcoudertWed, 11 Apr 2012 08:44:02 GMT
https://trac.sagemath.org/ticket/12716#comment:10
https://trac.sagemath.org/ticket/12716#comment:10
<p>
Thank you !
</p>
TicketjdemeyerThu, 19 Apr 2012 09:45:07 GMTmilestone changed
https://trac.sagemath.org/ticket/12716#comment:11
https://trac.sagemath.org/ticket/12716#comment:11
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.0</em> to <em>sage-5.1</em>
</li>
</ul>
TicketjdemeyerSun, 06 May 2012 12:15:38 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/12716#comment:12
https://trac.sagemath.org/ticket/12716#comment:12
<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.1.beta0</em>
</li>
</ul>
Ticket