and

initialize

them,

as

below.

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)

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

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:

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: