Tweet

Increase your income via IT outsourcing!

From OpenOpt

Maximum stable set of graph (STAB)

of maximum size subjected to:

---

(requires v. >= 0.42) OpenOpt STAB example

---

We use input argument of type networkx graph. networkx is de-facto standard of graph operations in Python with same permissive license (BSD). However, we could also provide direct assignment (via lists of vertex and edges) if you have problems with networkx dependense, e.g. due to rare platform / OS.

Unlike networkx maximum_independent_set() our API includes much more:

• Limitations on time, cputime, "enough" value (you should pass them to p.solve() function; works for interalg and cplex only, because glpk and lpSolve has no OpenOpt iterfcn connected yet)
• basic GUI features (run/pause, "enough")
• Optional arguments includedNodes / excludedNodes - nodes that must be present / absent in solution

Available solvers:

• interalg - pro: BSD license; cons: Python code with some slow parts (probably will be inhanced by PyPy); focused for non-linear problems and thus MILP solvers work better.
• MILP solvers

---

Future plans include:

• interalg can be adjusted to search for all STAB solutions
• Maybe other graph problems

---

See also:

• Independent set in wikipedia
• TSP - traveling salesman problem
• MCP - maximum clique problem

Made by Dmitrey