Introduction
This article is a tutorial on using callbacks, a group of advanced CPLEX features. The Traveling Salesmen Problem (TSP) will be used as a running example. CPLEX will be accessed through the Java Concert Technology interface. It will be assumed that the reader has completed all of the prerequisites given here.
Background: The Traveling Salesmen Problem
The Traveling Salesmen Problem (TSP) is as follows: given a set of cities, or vertices
\( V \)
a set of direct routes between cities, or edges
\( E \)
, and for each edge
\( e \)
a distance
\( d_e \)
, what is the shortest tour through all the cities that visits each city exactly once? As this problem is quite difficult, we often consider the special case where
\( d_e \)
is assumed to be metric
, the metric TSP.
One good integer programming formulation for TSP is the cutset formulation. For any \( S \subset V \) , let \( \delta(S) = \{(u,v) \in E \mid u \in S, v \not \in S\} \) . With a slight abuse of notation, for \( v \in V \) , we also let \( \delta(v) = \delta(\{v\}) \) . The cutset formulation is:
\[ \begin{aligned} &\min & \sum_{e \in E} d_e x_e\\ &\text{subject to}& \sum_{e \in \delta(v)} x_e &= 2&v&\in V\\ && \sum_{e \in \delta(S)} x_e &\geq 2& S &\subset V&S&\neq V,\emptyset \end{aligned} \]