#12716: MILP formulation and test functions for vertex separation
--------------------------------------------------------------------+-------
Reporter: dcoudert |
Owner: jason, ncohen, rlm
Type: enhancement |
Status: needs_work
Priority: major |
Milestone: sage-5.0
Component: graph theory |
Resolution:
Keywords: graph, decomposition, linear ordering, pathwidth | Work
issues:
Report Upstream: N/A |
Reviewers: Nathann Cohen
Authors: David Coudert |
Merged in:
Dependencies: |
Stopgaps:
--------------------------------------------------------------------+-------
Comment (by dcoudert):
Thanks Nathann for the review.
> I also have several questions :
> * 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 ?
Both are optimal. However, in some cases the integral version is faster
than the relaxed one. I don't know why.
> * Is the integrality variable really intended to be False **by
default** ? `O_o;;;`
Yes, because it is in general faster.
> * 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 `O_o`
You are right. Changed.
> * To me ``u[v][t] >= x[v][t]-y[v][t]`` is rather ``x[v][t] ==
u[v][t] + y[v][t]``, 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 `:-)`
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.
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 #12816.
Hope it is better now.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12716#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.
