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.