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:
\[ \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 \end{aligned} \]