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
//the degree constraints
for(V vertex: graph.getVertices()){
cplex.addEq(Util.integerSum(cplex, edgeVariables,
graph.getIncidentEdges(vertex)), 2);
}
|
|
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
//the objective
cplex.addMinimize(Util.integerSum(
cplex, edgeVariables, graph.getEdges(),tspInstance.getEdgeWeights()));
|
|
Solving and Extracting the Solution
Recall the warning from Reading Variable Values from CPLEX.
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. To accomplish this, add the fields
private ImmutableSet<E> edgesInOpt;
private double optVal;
|
then fill in the solve() method with
|