Opened 8 years ago
Closed 8 years ago
#12716 closed enhancement (fixed)
MILP formulation and test functions for vertex separation
Reported by: | dcoudert | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-5.1 |
Component: | graph theory | Keywords: | graph, decomposition, linear ordering, pathwidth |
Cc: | ncohen | Merged in: | sage-5.1.beta0 |
Authors: | David Coudert | Reviewers: | Nathann Cohen |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
This patch implements a MILP formulation for the vertex separation and some test functions for evaluating the width of linear vertex orderings.
APPLY:
Attachments (4)
Change History (16)
comment:1 Changed 8 years ago by
- Status changed from new to needs_review
comment:2 Changed 8 years ago by
- Description modified (diff)
- Summary changed from Linear orderings of graphs to MILP formulation and test functions for vertex separation
Changed 8 years ago by
comment:3 Changed 8 years ago by
Correction of doctests since the ordering given by the MILP depends on the system/solver (but the answer is correct).
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.
Changed 8 years ago by
Changed 8 years ago by
comment:4 follow-up: ↓ 5 Changed 8 years ago by
- Status changed from needs_review to needs_work
Helloooooooooo David !!!
Here is a small patch to apply on top of yours.. Here is what it does :
- One or two typoes
- Simplifies the definition of the LP variables... Could you give it a look, just to check I got nothing wrong ?
:-)
- 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.
- 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.
- I also moved several lines of code outside of the try/catch, as list operations usually do not throw MIPSolverExceptions
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 ?
- Is the integrality variable really intended to be False by default ?
O_o;;;
- 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
- 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
:-)
Well, I think that's all I had to say !
Nathann
comment:5 in reply to: ↑ 4 Changed 8 years ago by
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.
comment:6 Changed 8 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
comment:7 Changed 8 years ago by
Hellooooooooo !!
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.... ^^;
Nathann
Changed 8 years ago by
comment:8 Changed 8 years ago by
Corrected.
comment:9 Changed 8 years ago by
- Status changed from needs_review to positive_review
Well, then .... :-)
Nathann
comment:10 Changed 8 years ago by
Thank you !
comment:11 Changed 8 years ago by
- Milestone changed from sage-5.0 to sage-5.1
comment:12 Changed 8 years ago by
- Merged in set to sage-5.1.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
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'.