Problem Formulation

First, we will add the following fields to the class so we can easily reference our problem data from any method. Add

}
{section} 
{column:width=300px} 
{pagetree:root=Tutorial} 
{column} 
{column} 

h1. Problem Formulation

First, we will add the following fields to the class so we can easily reference our problem data from any method.  Add
{code}
private EnumSet<Option> options;
private IloCplex cplex;
private TspInstance<V,E> tspInstance;
private 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}

Next, we need to add the objective and the degree constraints to the {{IloCplex}} instance.  Try adding them yourself!  The following methods (as defined in [Solver Specification] and [Java Style for CPLEX]) should be useful for making the degree constraints:

* From {{Util}}, the static method {{integerSum(IloCplex cplex, BiMap<T,IloIntVar> variables, Iterable<T> set)

}}
* From {{IloCplex}}, the method {{addEq(IloNumExpr e, double v)

}}
* From {{UndirectedGraph<V,E>}}, the method {{getIncidentEdges(V vertex)

}}

{toggle-cloak

:id

=ConstraintsSolution

For the objective, we need the functions:

• From Util, the static method sum(IloCplex cplex, BiMap<T,IloIntVar> variables, Iterable<T> set, Function<? super T,? extends Number> coefficients)
• From UndirectedGraph<V,E>, the method getEdges()
• From TspInstance, the method getEdgeWeights()

{composition-setup}
{composition-setup

Solving and Extracting the Solution

Here we fill in the blank methods solve(), getEdgesInOpt(), and getOptVal(). For performance reasons, it is a good idea to cache the solution as a field of the TspIpSolver and "shut down" CPLEX. Recall the warning that calling getValue(IloIntVar var) from IloCplex repeatedly instead of a single getValues(IloIntVar[] vars) causes performance issues. Although it isn't really good "Java style," as discussed in Java Style for CPLEX, we will keep a copy of the edge variables stored in an array as a field of the class to improve performance.

} _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}}, the static method {{sum(IloCplex cplex, BiMap<T,IloIntVar> variables, Iterable<T> set, Function<? super T,? extends Number> coefficients)}}
* From {{UndirectedGraph<V,E>}}, the method {{getEdges()}}
* From {{TspInstance}}, the method {{getEdgeWeights()}}

{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. Solving and Extracting the Solution

Here we fill in the blank methods {{solve()}}, {{getEdgesInOpt()}}, and {{getOptVal()}}.  For performance reasons, it is a good idea to cache the solution as a field of the TspIpSolver and "shut down" CPLEX.  Recall [the warning|Java and CPLEX#Performance Issues Reading Variable Values from CPLEX] that calling {{getValue(IloIntVar var)}} from {{IloCplex}} repeatedly instead of a single {{getValues(IloIntVar[] vars)}} causes performance issues.  Although it isn't really good "Java style," as discussed in [Java Style for CPLEX], we will keep a copy of the edge variables stored in an array as a field of the class to improve performance. 

To accomplish this, first add the fields
{anchor:edgeVariablesAsArray}
{code}
	private ImmutableSet<E> edgesInOpt;
	private double optVal;
	private IloIntVar[] edgeVariablesAsArray;
{code}

Next, we will set the field {{edgeVariablesAsArray}} by adding the one-liner to the constructor:

{code

}
		...
		this.edgeVariables = Util.makeBinaryVariables(cplex, graph.getEdges());
		edgeVariablesAsArray = edgeVariables.inverse().keySet().toArray(new IloIntVar[]{});//insert this line
		//the degree constraints
		...
{code}

We will fill in the remaining fields during {{solve()}}.  But first, we add an auxiliary method to encapsulate access to {{edgeVariablesAsArray}}, reducing the chance of error down the road.  In designing this method, we must remember our previous discussion of [numerical tolerances

|Java and Cplex#Reading Integer Variable Values from CPLEX].
{code}
	/**
	 * assumes  edgeVarVals[i] in {0,1}, up to some tolerance.  
	 * @param edgeVarVals
	 * @return the edges where the variable takes the value one.
	 */
	private Set<E> edgesUsed(double[] edgeVarVals){
		Set<E> ans = new HashSet<E>();
		for(int e = 0; e < edgeVarVals.length; e++){
	        if(Util.doubleToBoolean(edgeVarVals[e])){
	        	ans.add(edgeVariables.inverse().get(edgeVariablesAsArray[e]));
	        }
	    }
		return ans;
	}

	public void solve() throws IloException{
		if(!cplex.solve()){
			throw new RuntimeException();
		}
		optVal = cplex.getObjValue();
		edgesInOpt = ImmutableSet.copyOf(edgesUsed(cplex.getValues(edgeVariablesAsArray)));
		cplex.end();
	}
	
	public ImmutableSet<E> getEdgesInOpt(){
		return edgesInOpt;
	}
	
	public double getOptVal(){
		return optVal;
	}

{code}
The method {{edgesUsed()}} make look a little odd right now, but its value will become apparent in the next section.

h1. Test Your Code

Now is a good time to test the code you have written thus far.  Keep in mind that we haven't implemented the _cutset_ constraints yet.  A unit test {{testDegreeConstraints()}} was made exactly for this purpose, in _tspSolver/test/solver/TspSolverTest.java_.  Run the class as a JUnit test (right click on the class in the _Project Explorer_ and select _Run As → JUnit Test_.  If you are not on Windows, again you likely will need to set a VM argument [as previously discussed|Test Your Java, Eclipse and Cplex Installations].  The test {{testDegreeConstraints()}} should now pass.

If you need to debug, the unit test is on the following graph:

{gliffy:name=tspDegreeConstraints|align=left|size=L|version=1}

{column} 
{section}