1

Is there any python implementation available of TSP using the IBM cplex tool, with Dantzig-Fulkerson-Johnson formulation.

If there is any can I get the link for it?

Vadim Kotov
  • 8,084
  • 8
  • 48
  • 62
ooo
  • 512
  • 1
  • 7
  • 27

1 Answers1

4

The exact same question was asked here. Here is my (slightly modified) answer from there:

The distribution does not have an example implementation in Python, but there is one in OPL: opl/examples/opl/models/TravelingSalesmanProblem/tsp.mod in your installation. This could serve as a good starting point when implementing things in Python.

In the example the problem is solved in a loop: after each solve, subtour elimination constraints are separated. In Python you would probably want to do this using a lazy constraint callback.

In general, subtour elimination constraints are usually not added directly to the model since there exponentially many of them.

Daniel Junglas
  • 5,830
  • 1
  • 5
  • 22
  • I wanted to know how can I do lazy constraint callback to remove sub tour, that is why I am looking for implementation or something close to it. – ooo Mar 04 '20 at 09:36
  • You can find an answer to that question here: https://developer.ibm.com/answers/questions/463342/how-to-implement-a-lazycutcallback-in-docplex.html If that does not help/work then please ask a new question about implementing lazy constraint callbacks in `docplex`. – Daniel Junglas Mar 04 '20 at 09:54
  • I have tried Implementing it by myself But got stuck in `add_lazy_constraint` function, can you take a look at this question https://stackoverflow.com/questions/60543917/implementing-tsp-with-lazy-constraint-callback – ooo Mar 05 '20 at 11:05