Opened 7 years ago

Closed 7 years ago

Last modified 7 years ago

#11944 closed defect (fixed)

Update Graph.clique_maximum to use MILP

Reported by: ncohen Owned by: tbd
Priority: major Milestone: sage-4.8
Component: graph theory Keywords:
Cc: dcoudert Merged in: sage-4.8.alpha0
Authors: Nathann Cohen Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #11846, #11928 Stopgaps:

Description (last modified by ncohen)

This begins to be a joke, but there is a third method I had forgotten in #11846 and #11928 as noticed by Peter Mueller :-p

This patch updated clique_maximum to use the new MILP formulation of independent set !

Requires :

Apply:

Nathann

Attachments (1)

trac_11944.patch​ (2.3 KB) - added by ncohen 7 years ago.

Download all attachments as: .zip

Change History (10)

comment:1 Changed 7 years ago by ncohen

  • Component changed from PLEASE CHANGE to graph theory
  • Description modified (diff)
  • Status changed from new to needs_review
  • Type changed from PLEASE CHANGE to defect

Changed 7 years ago by ncohen

comment:2 Changed 7 years ago by dcoudert

  • Reviewers set to David Coudert
  • Status changed from needs_review to needs_info

The patch is working correctly, and the documentation is displayed properly.

I have a question concerning the algorithms: wouldn't it be faster to first decompose the graph into 2-connected components, and then try the algorithm on each of them ? This could be interesting for sparse graphs.

comment:3 Changed 7 years ago by ncohen

  • Status changed from needs_info to needs_review

Hello !!!

It would be, but not in this patch, as it does not do anything but asks for the "independent set algorithm" to do it.

The answer, however is "YES", and much more :

I interfaced some time ago an external C code for modular decomposition. With this decomposition, you obtain (given a graph) a recursive decomposition into connected components and anticonnected components (the complement of connectedcomponents). This is what we should use to first educe the graph, as this algorithm is very fast (though it will have no effect for random-looking graphs).

I have had it on my todo list for a while, and right now I am actually writing the ong-awaited Gurobi interface for Sage :-)

Nathann

comment:4 Changed 7 years ago by dcoudert

  • Status changed from needs_review to positive_review

Thank you Nathann for the prompt answer.

So my review for this patch is positive.

comment:5 Changed 7 years ago by ncohen

Thaaaaaaaaaaaanks !! :-)

Nathann

comment:6 Changed 7 years ago by jdemeyer

  • Dependencies changed from 11846, 11928 to #11846, #11928

comment:7 Changed 7 years ago by jdemeyer

  • Merged in set to sage-4.7.3.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:8 Changed 7 years ago by jdemeyer

  • Milestone sage-4.7.3 deleted

Milestone sage-4.7.3 deleted

comment:9 Changed 7 years ago by jdemeyer

  • Merged in changed from sage-4.7.3.alpha0 to sage-4.8.alpha0
  • Milestone set to sage-4.8
Note: See TracTickets for help on using tickets.