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
&\min & \sum_
d_e x_e
&\text
& \sum_
x_e &= 2&v&\in V
&& \sum_
x_e &\geq 2& S &\subset V&S&\neq V,\emptyset
\end