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

Compare with Current View Page History

« Previous Version 28 Next »

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

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 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 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, located in tspSolver/test/solver/, and on larger instances in from the (famous) TSPLIB 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.

Setting up the problem

Open the file src/solver/TspIpSolver.java by double clicking it from the Project Explorer. This is the file we will be primarily editing. It should contain the following (after the imports):
Toggle TspIpSolver.java 

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;
	}	
}

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

private IloCplex cplex;
private TspInstance<V,E> tspInstance;
private final ImmutableBiMap<E,IloIntVar> edgeVariables;

and initialize them, as below.

	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		
	}

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)
    • For each element \( e \) of set, finds the corresponding variable \( x_e \) and returns \( \sum_{e \in \text{set}} x_e \)
  • From IloCplex, public IloRange addEq(IloNumExpr e, double v)
    • Adds the equality constraint e = v
  • From UndirectedGraph<V,E>, public Collection<E> getIncidentEdges(V vertex)
    • returns the edges of the graph that are incident to vertex

If you are unfamiliar with Java, consider viewing the solution for the constraint, then trying the objective yourself.
Solution

For the objective, we need the functions:

  • From Util, public static <T> IloLinearNumExpr sum(IloCplex cplex, BiMap<T,IloIntVar> variables, Iterable<T> set, Function<? super T,? extends Number> coefficients)
    • For every element \( e \) of set, gets the corresponding variable \( x_e \) from variables and the number \( d_e \) from coefficients and returns an expression for \( \sum_{e \in \text{set}} d_e x_e \) .

Solution

A First Solution by LazyConstraintCallback

Interesting TSP References.

On solving TSPs

TSP Problem Instances

  • No labels