#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: |
Status badges
Description (last modified by )
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)
Change History (8)
Changed 9 years ago by
comment:1 Changed 9 years ago by
- Status changed from new to needs_review
comment:2 Changed 9 years ago by
- Description modified (diff)
comment:3 Changed 9 years ago by
- Reviewers set to David Coudert
- Status changed from needs_review to positive_review
comment:4 Changed 9 years ago by
- Milestone changed from sage-4.7.2 to sage-4.7.3
comment:5 Changed 9 years ago by
- Merged in set to sage-4.7.3.alpha0
- Resolution set to fixed
- Status changed from positive_review to closed
comment:7 Changed 9 years ago by
- 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.
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.