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 methodintegerSum(IloCplex cplex, BiMap<T,IloIntVar> variables, Iterable<T> set)
- From
IloCplex
, the methodaddEq(IloNumExpr e, double v)
- From
UndirectedGraph<V,E>
, the methodgetIncidentEdges(V vertex)
Solution
For the objective, we need the functions:
- From
Util
, the static methodsum(IloCplex cplex, BiMap<T,IloIntVar> variables, Iterable<T> set, Function<? super T,? extends Number> coefficients)
- From
UndirectedGraph<V,E>
, the methodgetEdges()
- From
TspInstance
, the methodgetEdgeWeights()
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()); 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.
a
for using