5
$\begingroup$

In TSP wiki it is said that delayed column generation method is used to solve Dantzig-Fulkerson-Johnson formulation as it has an exponential number of possible constraints. I wanted to know whether it is available in the IBM cplex tool or it is a concept needs to be implemented by self.

I am looking for some links where the delayed column generation method is implemented.

Improve this question
$\endgroup$
  • 4
    $\begingroup$ I don't know why it says delayed column generation. That is usually referred to in relation with Dantzig-Wolfe decomposition. For TSP you can try the Concorde solver. If you want CPLEX you need to do the cuts yourself using the callback functionality. $\endgroup$ – Simon Spoorendonk Feb 29 '20 at 13:31
  • 2
    $\begingroup$ Instead, the DFJ approach uses row generation, aka constraint generation or cutting planes. $\endgroup$ – RobPratt Feb 29 '20 at 15:20
  • $\begingroup$ I am looking for some links where it is implemented/used in TSP or some other related problem. $\endgroup$ – ooo Feb 29 '20 at 16:31
  • $\begingroup$ To add others mentioned, one of the best ways to solve the TSP problem with an exact method is Branch and Cut. (specifically using callback functions.). There are some implementations of such method on the commercial or open-source solvers host, like CPLEX, Gurobi, SCIP, MIPCL etc. (E.g. here by SCIP or here by MIPCL.). $\endgroup$ – A.Omidi Mar 1 '20 at 7:34
  • $\begingroup$ Also, there are some useful webinars which could be found here and here. Indeed, there is an implementation of delayed column generation using gams. I hope they will be helpful. $\endgroup$ – A.Omidi Mar 1 '20 at 7:41
3
$\begingroup$

I agree with others that solving TSP with DFJ constraint for subtour elimination does not require implementing a column generation-type algorithm. Instead, you need to implement a cutting plane algorithm or a branch & cut (B&C) algorithm. In the former, you start with the assignment problem formulation, solve the problem, and add the necessary DFJ cuts for the violated subtour elimination constraints. Then, you solve the resulting new problem (commonly, known as the master problem). This process is repeated until no subtour elimination constraint is violated. This process could be time-consuming as you are solving the master problem from scratch every time. The latter approach could enhance the performance as you are solving a MIP formulation using the branch and bound technique, but adding the DFJ cuts for the violated subtour elimination constraints whenever you found a new integer incumbent within the branch and bound tree.

From the implementation perspective, you can implement the cutting plane approach using a simple for loop within a programming language. The B&C approach is more tricky as it requires using the callbacks in CPLEX. In older versions of CPLEX, you should use the lazy constraint callback, but you might use the generic callback in the more recent versions. I've not come across any available example for either approach on the web, but you might find it with some luck. Alternatively, you might consult the benders ATSP example within the CPLEX example repository (the corresponding list for each programming language is available from here). The example is discussing how to solve the asymmetric TSP using B&C, but adding benders decomposition-type constraint, instead. Changing the code to accommodate for DFJ cuts would be relatively easy from there. You should keep in mind that finding the violated subtour elimination constraints for TSP is equivalent to a graph connectivity problem.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ There's an implementation of TSP with subtour elimination constraints added via lazy constraint callbacks (using CPLEX) available here; note that it uses JuMP version 0.18 rather than 0.19+, so you would need to change the code if you were going to use the latest version of JuMP. $\endgroup$ – Ryan Cory-Wright Mar 1 '20 at 1:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.