You are viewing an old version of this page. View the current version.

Compare with Current View Page History

« Previous Version 10 Next »

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\} \) , i.e. those edges with exactly one endpoint in \( S \) . With a slight abuse of notation, for \( v \in V \) , we also let \( \delta(v) = \delta(\{v\}) \) , i.e. the edges incident to \( 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\\ && x_e &\in\{0,1\}&e&\in E \end{aligned} \]

The first family of constraints say that every node must have degree two, and the second family of constraints say that for any cut separating the graph into two subsets, there must be at least two edges in use across the cut (hence cutset). The solution to the linear programming relaxation of this formulation (when the integrality constraints are dropped) is known as the Held-Karp lower bound. Notice that there are exponentially many subsets of \( V \) , (exactly \( 2^{|V|} \) ), and thus our integer programming formulation has exponentially many constraints.

Set Up your Project

Download this zip file for the project here. Unzip it and import it into your Eclipse workspace. It should already compile (there should be no files with a red 'x' on them). If it does not, fix your build path so all the JARs are properly located.

The Task & Project Organization

You are about to build a TSP solver capable of solving TSP instances with over 500 cities to optimality. The solver will require a variety of algorithms for known combinatorial problems and efficient data structures. These algorithms and data structures have been provided for you, either through libraries (JARs) distributed with the project, or code that has already been written for you. In particular, in the folder tspSolver/lib/,

  • The file cplex.jar provides a Java interface to CPLEX
  • The file guava-14.0-rc1.jar contains the Guava libary. Guava provides some extra features not distributed in the base Java libraries. In particular, it gives a few extra data structures which we will use, most notably the Bimap.
  • The subdirectory jung/ contains the collection of JARs needed to use the JUNG library, which provides the graph data structure we will use to store our TSP instances and algorithms for solving many classical combinatorial problems on graphs including max flow min cut and minimum spanning tree.
  • The subdirectory jgrapht/ contains the collection of JARs needed to use the JGraphT library, another graphical library similar to JUNG. It is no longer under active development (so generally it is better to use JUNG), but it contains a few tools not included in JUNG that we will need for extracting Eulerian tours.

All you need to do is to put everything together. You will test your code on small hand coded test instances using the JUnit test framework and on larger instances in from the (famous) TSPLIB test set. The code to create the test instances has been provided.

Interesting TSP References.

On solving TSPs

TSP Problem Instances

  • No labels