TSP
From OpenOpt
Traveling salesman problem (TSP)
- Find a hamiltonian cycle of graph with optimal cost
(requires v. >= 0.42) OpenOpt TSP examples:
- (simplest) example 1 (undirected, unconstrained)
- example 2 (directed, constrained)
- example 3 (directed, multigraph, constrained)
- example 4 (directed, multigraph, constrained, nonlinear, multiobjective)
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.
Our API includes:
- 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")
- Some useful optional arguments like returnToStart (default: True), goal (default: min)
Available solvers:
- MILP solvers ("just works" MTZ)
- sa (simulated annealing, code by John Montgomery) - taken from here
- interalg - pro: BSD license; cons: Python code with some slow parts (probably will be enhanced by PyPy); focused for non-linear problems and thus MILP solvers work better
Future plans include:
- several agents
- add constraints and possibility to handle general objective function to sa
- involve parallel computations for sa
- TSP-like problems
- connect to our stochastic programming addon (commercial, although) to solve stochastic TSP
- I (Dmitrey) wrote some code modification to sa that reduces time per iter by factor 2.0...2.3, however, it works for undirected graphs only, for directed graphs some modifications are required; the code hasn't been committed yet
- I have some ideas that could have more efficient convergence than simulated annealing, at least for metric TSP, but it requires much time to implement
See also
- OpenOpt TSP class code (requires some cleanup although, also, some OpenOpt kernel hacks beyond standard kernel-solver API are temporary used)
- STAB - maximum graph stability set
- MCP - maximum clique problem
- KSP - knapsack problem
- BPP - bin packing problem
- MILP - mixed-integer linear problem
- TSP wikipedia page
Made by Dmitrey |