{composition-setup} 
{composition-setup} 


{pagetree:root=Tutorial}


h1. 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-cloak:id=TspIpSolverStart} _Toggle TspIpSolver.java_ 
{cloak:id=TspIpSolverStart|visible=true}
{code}
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}
{cloak}
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)}}
** For each element {mathinline}e{mathinline} of {{set}}, finds the corresponding variable {mathinline}x_e{mathinline} and returns {mathinline}\sum_{e \in \text{set}} x_e {mathinline}
* 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.
{toggle-cloak:id=ConstraintsSolution} _Solution_ 
{cloak:id=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 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 {mathinline}e{mathinline} of {{set}}, gets the corresponding variable {mathinline}x_e{mathinline} from {{variables}} and the number {mathinline}d_e{mathinline} from {{coefficients}} and returns an expression for {mathinline}\sum_{e \in \text{set}} d_e x_e {mathinline}.

{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/]