Opened 8 years ago

Closed 7 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 dcoudert)

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)

trac_12716_MILP.patch (21.9 KB) - added by dcoudert 7 years ago.
trac_12716_linear_ordering.patch (35.7 KB) - added by dcoudert 7 years ago.
trac_12716-review.patch (9.0 KB) - added by ncohen 7 years ago.
trac_12716-combined.patch (22.6 KB) - added by dcoudert 7 years ago.

Download all attachments as: .zip

Change History (16)

comment:1 Changed 8 years ago by dcoudert

  • Status changed from new to needs_review

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'.

comment:2 Changed 7 years ago by dcoudert

  • Description modified (diff)
  • Summary changed from Linear orderings of graphs to MILP formulation and test functions for vertex separation

Changed 7 years ago by dcoudert

comment:3 Changed 7 years ago by dcoudert

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 7 years ago by dcoudert

Changed 7 years ago by ncohen

comment:4 follow-up: Changed 7 years ago by ncohen

  • 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 7 years ago 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.

comment:6 Changed 7 years ago by dcoudert

  • Description modified (diff)
  • Status changed from needs_work to needs_review

comment:7 Changed 7 years ago by ncohen

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 7 years ago by dcoudert

comment:8 Changed 7 years ago by dcoudert

Corrected.

comment:9 Changed 7 years ago by ncohen

  • Status changed from needs_review to positive_review

Well, then .... :-)

Nathann

comment:10 Changed 7 years ago by dcoudert

Thank you !

comment:11 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.0 to sage-5.1

comment:12 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.1.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.