Opened 7 years ago

Closed 7 years ago

Last modified 7 years ago

#11846 closed enhancement (fixed)

Independent set through Linear Programming (sometimes, it is faster !)

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

Description (last modified by ncohen)

Hello !!

Dealing with highly regular graphs, I noticed Cliquer sometimes didn't spot regular structures and spent some time that a LP could ignore. This patch adds the formulation to the independent_set method. I believe it was there a looooong time ago :-)

Apply trac_11846.patch

Nathann

Attachments (1)

trac_11846.patch (3.8 KB) - added by ncohen 7 years ago.

Download all attachments as: .zip

Change History (8)

Changed 7 years ago by ncohen

comment:1 Changed 7 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 7 years ago by ncohen

  • Description modified (diff)

comment:3 Changed 7 years ago by dcoudert

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

The MILP model is correct, the patch is working properly, and the doc is OK.

Remark: The test line 3820 is surprising, but it has the advantage of working both with patch http://trac.sagemath.org/sage_trac/ticket/10505 (Round values returned by CPLEX when the variable's type is integer/binary), and without that patch.

comment:4 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-4.7.2 to sage-4.7.3

comment:5 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:6 Changed 7 years ago by jdemeyer

  • Milestone sage-4.7.3 deleted

Milestone sage-4.7.3 deleted

comment:7 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.