Wiki Markup |
---|
{composition-setup}
{composition-setup |
Section |
---|
Column |
---|
| Page Tree |
---|
root | 15DOTs60ia13:Tutorial |
---|
|
|
Column |
---|
First, we will add the following fields to the class so we can easily reference our problem data from any method. Add Code Block |
---|
}
{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}
private EnumSet<Option> options;
private IloCplex cplex;
private TspInstance<V,E> tspInstance;
private ImmutableBiMap<E,IloIntVar> edgeVariables;
{code}
and initialize them, as below. Code Block |
---|
{code}
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}
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
* From {{Util}}, the static method {{integerSum(IloCplex cplex, BiMap<T,IloIntVar> variables, Iterable<T> set) From IloCplex , the method }}
* From {{IloCplex}}, the method {{addEq(IloNumExpr e, double v) From }}
* From {{UndirectedGraph<V,E>}}, the method {{getIncidentEdges(V vertex) }}
{toggle-cloak :id =ConstraintsSolution 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 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
Anchor |
---|
edgeVariablesAsArray | edgeVariablesAsArray | Code Block |
---|
} _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}
private ImmutableSet<E> edgesInOpt;
private double optVal;
private IloIntVar[] edgeVariablesAsArray;
{code}
Next, we will set the field {{edgeVariablesAsArray}} by adding the one-liner to the constructor:
{code
}
...
this.edgeVariables = Util.makeBinaryVariables(cplex, graph.getEdges());
edgeVariablesAsArray = edgeVariables.inverse().keySet().toArray(new IloIntVar[]{});//insert this line
//the degree constraints
...
{code}
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
. Code Block |
---|
|Java and Cplex#Reading Integer Variable Values from CPLEX].
{code}
/**
* 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}
The method {{edgesUsed()}} make look a little odd right now, but its value will become apparent in the next section.
h1. 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|Test Your Java, Eclipse and Cplex Installations]. The test {{testDegreeConstraints()}} should now pass.
If you need to debug, the unit test is on the following graph:
Gliffy Diagram |
---|
size | L |
---|
name | tspDegreeConstraints |
---|
align | left |
---|
version | 1
{gliffy:name=tspDegreeConstraints|align=left|size=L|version=1}
{column}
{section}