Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

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

Closed
nathanncohen mannequin opened this issue Sep 25, 2011 · 7 comments
Closed

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

nathanncohen mannequin opened this issue Sep 25, 2011 · 7 comments
Assignees
@jasongrout @rlmill @nathanncohen
Labels
c: graph theory p: major / 3 t: enhancement
Milestone
sage-4.8

Comments

@nathanncohen
Copy link
Mannequin

nathanncohen mannequin commented Sep 25, 2011

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 attachment: trac_11846.patch

Nathann

Component: graph theory

Author: Nathann Cohen

Reviewer: David Coudert

Merged: sage-4.8.alpha0

Issue created by migration from https://trac.sagemath.org/ticket/11846
@nathanncohen nathanncohen mannequin added this to the sage-4.7.2 milestone Sep 25, 2011
@nathanncohen
Copy link
Mannequin Author

nathanncohen mannequin commented Sep 25, 2011

comment:1

Attachment: trac_11846.patch.gz

@nathanncohen nathanncohen mannequin added the s: needs review label Sep 25, 2011
@nathanncohen

This comment has been minimized.

Sign in to view
@dcoudert
Copy link
Contributor

comment:3

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 #10505 (Round values returned by CPLEX when the variable's type is integer/binary), and without that patch.

@dcoudert
Copy link
Contributor

Reviewer: David Coudert

@jdemeyer jdemeyer modified the milestones: sage-4.7.2, sage-4.8 Oct 16, 2011
@jdemeyer
Copy link

Merged: sage-4.7.3.alpha0

@jdemeyer
Copy link

jdemeyer commented Nov 3, 2011

Milestone sage-4.7.3 deleted

@jdemeyer jdemeyer removed this from the sage-4.8 milestone Nov 3, 2011
@jdemeyer
Copy link

jdemeyer commented Nov 3, 2011

Changed merged from sage-4.7.3.alpha0 to sage-4.8.alpha0

@jdemeyer jdemeyer added this to the sage-4.8 milestone Nov 3, 2011
This was referenced Nov 3, 2011
Closed
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@jasongrout jasongrout

@rlmill rlmill

@nathanncohen nathanncohen

Labels
c: graph theory p: major / 3 t: enhancement
Projects
None yet
Milestone
sage-4.8
Development

No branches or pull requests
3 participants
@jasongrout @jdemeyer @dcoudert