Home Install Documentation Problems Tree Applications Forum

Increase your income
via IT outsourcing!
Ukrainian HI-TECH Initiative Ukrainian HI-TECH Initiative

DSP

From OpenOpt

Jump to: navigation, search
Dominating set problem (DSP)
For a graph G = (V, E) find a subset D of V such that every vertex not in D is adjacent to at least one member of D

(since v. 0.51) OpenOpt DSP 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 dominating set solvers 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 on non-linear problems and thus MILP solvers work better.
  • MILP solvers

Future plans include:

  • weighted DSP, possibly with edge attributes
  • interalg can be adjusted to search for all DSP solutions
  • Maybe other graph problems

See also:

Made by Dmitrey
Retrieved from "http://openopt.org/DSP"
Personal tools
Latest OOSuite 0.53

from 2014-03-15