Page History

{composition-setup} 
{composition-setup} 

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}, i.e. those edges with exactly one endpoint in {mathinline}S{mathinline}.  With a slight abuse of notation, for {mathinline}v \in V{mathinline}, we also let {mathinline}\delta(v) = \delta(\{v\}){mathinline}, i.e. the edges incident to {mathinline}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\\
&& x_e &\in\{0,1\}&e&\in E
\end{aligned}
{mathdisplay}
The first family of constraints say that every node must have degree two, and will be referred to as the *degree constraints*.   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, and will be referred to as the *cutset constraints*.  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 {mathinline}V{mathinline}, (exactly {mathinline}2^{|V|}{mathinline}), and thus our integer programming formulation has exponentially many constraints.

h1. Set Up your Project

Close Eclipse.  Download the project in [this zip archive|^tspSolverV1.zip].  Unzip it and put the folder _tspSolver_ inside the directory of your Eclipse workspace.  Now open Eclipse.  Go to _File → Import_, then select _General → Existing Projects into Workspace_ and hit the _Next_ button.  You will now be asked to _Select a directory to search for existing Eclipse projects._  Click the top radio button for _Select a root directory:_ then click the _Browse_ button.  A file selector should open already in your workspace directory.  Select the folder _tspSolver_ that we just put here.  In the panel below labeled _Projects:_, _tspSolver_ should pop with with a check box next to it already checked.  Go the bottom and hit _Finish_.  The project should now be visible in in the _Project Explorer_ on the left panel of the Eclipse GUI.  Expand the project and the _src_ folder.  Make sure everything compiles (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 (ask a TA).

Open the file _src/solver/TspIpSolver.java_ by double clicking it from the Project Explorer.  This is the file we will be primarily editing.

h1. 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.

The libraries distributed with the project are located in the folder _tspSolver/lib/_.  We now summarize their functions:

* The file _cplex.jar_ provides a Java interface to CPLEX.
* The file _guava-14.0-rc1.jar_ contains the [Guava|http://code.google.com/p/guava-libraries/wiki/GuavaExplained?tm=6] 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|http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/BiMap.html].
* The subdirectory _jung/_ contains the collection of JARs needed to use the [JUNG library|http://jung.sourceforge.net/], which provide 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, minimum spanning tree, and connected components.
* The subdirectory _jgrapht/_ contains the collection of JARs needed to use the [JGraphT library|http://jgrapht.org/], 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|http://en.wikipedia.org/wiki/Eulerian_path].

In algorithms and data structures implemented for you are located in the directories _tspSolver/src/instances_ and _tspSolver/src/solver/_.  Most importantly, the code here includes

* _src/instances/TspInstance.java_ provides the data structures used the store the graph and edge weights that are the inputs for solving a TSP problem.  Some utility methods for computing properties of cuts and tours are also provided.
* _solver/Util.java_ provides a few methods for making the CPLEX API more Java friendly and integrating the various libraries we are using.
* _src/solver/MinCutSolver.java_ provides a light weight wrapper around [the JUNG implementation of the Edmonds Karp algorithm|http://jung.sourceforge.net/doc/api/edu/uci/ics/jung/algorithms/flows/EdmondsKarpMaxFlow.html] for solving max flow min cut.
* _src/solver/ChristofidesSolver.java_ provides an implementation of Christofides algorithm that can additionally take a set of suggested edges as a _hint_.
* _src/solver/TwoOpt.java_ provides a naïve implementation of the the [two opt|http://www2.research.att.com/~dsj/papers/TSPchapter.pdf] local search algorithm.


To complete the tutorial, all you need to do is to put everything together.  The file

_tspSolver/src/solver/TspIpSolver.java_

is the only file you will need to modify.  It begins almost blank, and we provide step by step instructions on how to complete it.

You will test your code on small hand coded test instances using the [JUnit test framework|http://www.vogella.com/articles/JUnit/article.html], located in _tspSolver/test/solver/_, and on larger instances in from the (famous) [TSPLIB|http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/] test set.  The project is distributed with the TSPLIB data in the directory _tspSolver/sampleData/TSPLIB_.  The code to create the {{TspInstance}} objects by parsing the data files is in _tspSolver/src/tspLib/TspLibParser.java_, but has already been called for you from _tspSolver/src/main/Main.java_, the entry point for the program.

h1. Setting up the problem

Open _src/solver/TspIpSolver.java_ (if you haven't already).  It should contain the following (after the imports):
{code}
{toggle-cloak:id=TspIpSolverStart} _Toggle TspIpSolver.java_ 
{cloak:id=TspIpSolverStart|visible=true}
public class TspIpSolver<V,E> {
	
	public static enum Option{
		lazy,userCut, randomizedUserCut, christofidesApprox, christofidesHeuristic,twoOpt,incumbent;
	}
	
	public TspIpSolver(TspInstance<V,E> tspInstance) throws IloException{
		this(tspInstance,EnumSet.of(Option.lazy, Option.userCut, 
		Option.christofidesApprox, Option.christofidesHeuristic));
	}
	
	public TspIpSolver(TspInstance<V,E> tspInstance, EnumSet<Option> options) throws IloException{}
	
	public void solve() throws IloException{		
	}
	
	public ImmutableSet<E> getEdgesInOpt(){
		return null;
	}
	
	public double getOptVal(){
		return 0;
	}	
}
{code}

The {{Option}} arguments will be needed later.  First, we need to set up the objective and the degree constraints.  First, add the following fields to the class
{code}
private IloCplex cplex;
private TspInstance<V,E> tspInstance;
private final ImmutableBiMap<E,IloIntVar> edgeVariables;
{code}
and initialize them, as below.
{code}
	public TspIpSolver(TspInstance<V,E> tspInstance, EnumSet<Option> options) throws IloException{
		this.options = options;
		this.tspInstance = tspInstance;
		this.cplex = new IloCplex();
		UndirectedGraph<V,E> graph = tspInstance.getGraph(); //for convenience, we will be using this a lot
		this.edgeVariables = Util.makeBinaryVariables(cplex, graph.getEdges());
		//the degree constraints
		//the objective		
	}
{code}
The constraints and objective still need to be added to the {{cplex}} object.  Try adding them yourself!  The following methods should be useful for making the constraints:
* From {{Util}}, {{public static <T> IloLinearIntExpr integerSum(IloCplex cplex, BiMap<T,IloIntVar> variables, Iterable<T> set)}}
* From {{IloCplex}}, {{public IloRange addEq(IloNumExpr e, double v)}}
* From {{UndirectedGraph<V,E>}}, {{public Collection<E> getIncidentEdges(V vertex)}}
If you are unfamiliar with Java, consider viewing the solution for the constraint, then trying the objective yourself.
{toggle-cloak:id=ConstraintsSolution} _Solution_ 
{cloak:id=Bits ConstraintsSolution|visible=false}
{code}
		//the degree constraints
		for(V vertex: graph.getVertices()){
			cplex.addEq(Util.integerSum(cplex, edgeVariables, 
					graph.getIncidentEdges(vertex)), 2);
		}
{code}
{cloak}
For the objective, we need one more function:
* From
{toggle-cloak:id=ObjectiveSolution} _Solution_ 
{cloak:id=ObjectiveSolution|visible=false}
{code}
		//the objective
		cplex.addMinimize(Util.integerSum(
				cplex, edgeVariables, graph.getEdges(),tspInstance.getEdgeWeights()));
{code}
{cloak}

h1. A First Solution by LazyConstraintCallback


h1. Interesting TSP References.

On solving TSPs
* [http://www.seas.gwu.edu/~simhaweb/champalg/tsp/tsp.html]
* On Construction and Improvement Heuristics: [http://www2.research.att.com/~dsj/papers/TSPchapter.pdf]

TSP Problem Instances
* [http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/]