Page History

h1. 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|Cut Generation, Heuristics and Callbacks Workshop]. 

h1. Background: The Traveling Salesmen Problem

The Traveling Salesmen Problem (TSP) is as follows: given a set of cities, or vertices {mathinline}V{mathinline} a set of direct routes between cities, or edges {mathinline}E{mathinline}, and for each edge {mathinline}e{mathinline} a distance {mathinline}d_e{mathinline}, 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 {mathinline}d_e{mathinline} is assumed to be [metric|http://en.wikipedia.org/wiki/Metric_(mathematics)#Definition], the metric TSP.

One good integer programming formulation for TSP is the _cutset_ formulation.  For any {mathinline}S \subset V{\mathinline}, let {mathinline}\delta(S) = \{(u,v) \in E \mid u \in S, v \not \in S\}{mathinline}.  With a slight abuse of notation, for {mathinline}v \in V{mathinline}, we also let {mathinline}\delta(v) = \delta(\{v\}){mathinline}.  The cutset formulation is:
{mathdisplay}
\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}
{mathdisplay}