Hi all,

In OpenOpt (free software written in Python language, BSD-licensed) we have implemented new class - STAB - searching for maximum stable set of a graph.

networkx graphs are used as input arguments (networkx is another free Python language software for graphs handling). Unlike networkx function maximum_independent_set() we mostly focus on searching for exact solution (this is NP-Hard problem).

Thus you can also solve maximum clique problem on complementary graph simply via networkx.complement(G)

interalg or OpenOpt-connected MILP solvers (glpk, lpSolve, cplex) are used, some GUI features and stop criterion (e.g. maxTime, maxCPUTime, fEnough) can be used. Also optional arguments are includedNodes and excludedNodes - nodes that have to be present/absent in solution.

Future plans (probably very long-term although) include TSP and some other graph problems with similar API and possibilities.


Regards, Dmitrey.

asked 14 Jul '12, 08:26

Dmitrey's gravatar image

Dmitrey
28311126
accept rate: 0%

edited 15 Sep '12, 10:58

fbahr's gravatar image

fbahr ♦
4.6k716

Be the first one to answer this question!
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×39
×18
×17

Asked: 14 Jul '12, 08:26

Seen: 2,144 times

Last updated: 15 Sep '12, 10:58

OR-Exchange! Your site for questions, answers, and announcements about operations research.