Problem Formulation

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

private EnumSet<Option> options;
private IloCplex cplex;
private TspInstance<V,E> tspInstance;
private 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		
	}

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)

Solution

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()

Solution

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.

To accomplish this, first add the fields

	private ImmutableSet<E> edgesInOpt;
	private double optVal;
	private IloIntVar[] edgeVariablesAsArray;

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

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

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.

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

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

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. The test testDegreeConstraints() should now pass.

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

Child pages

Adding Variables Objectives and Constraints

Problem Formulation

Solving and Extracting the Solution

Test Your Code