}
{composition-setup}
{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} Column |
---|
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;
|
| {code}
{code} Code Block |
---|
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}
{{}} [ ] [ ]
* From {{Util}}, the static method {{- From
Util , the static method integerSum(IloCplex
| }}
* From {{IloCplex}}, the method {{- From
IloCplex , the method addEq(IloNumExpr
| }}
* From {{- From
UndirectedGraph<V,E>
| }} {{ }}
{:=} _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} Solution Cloak |
---|
visible | false |
---|
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() Solution Cloak |
---|
visible | false |
---|
id | ObjectiveSolution |
---|
| |
Solving and Extracting the SolutionHere 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
Anchor |
---|
| edgeVariablesAsArray |
---|
| edgeVariablesAsArray |
---|
|
Code Block |
---|
private ImmutableSet<E> edgesInOpt;
private double optVal;
private IloIntVar[] edgeVariablesAsArray;
|
| {code}
{{}}
{} |
---|
...
this.edgeVariables = Util.makeBinaryVariables(cplex, graph.getEdges());
edgeVariablesAsArray = edgeVariables.inverse().keySet().toArray(new IloIntVar[]{});//insert this line
//the degree constraints
...
|
| {code}
{{}} {{}} [ |Java and Cplex#Reading Integer Variable Values from CPLEX].
{code}. Code Block |
---|
/**
* 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}
{{}}
h1.
__ {{}} _tspSolver/test/solver/TspSolverTest.java | _ _ _ _ _ [ |Test Your Java, Eclipse and Cplex Installations] {{}}
{gliffy:name=tspDegreeConstraints|align=left|size=L|version=1}
{column}
{section} Gliffy Diagram |
---|
size | L |
---|
name | tspDegreeConstraints |
---|
|
|
|