First, we will add the following fields to the class so we can easily reference our problem data from any method. Add Code Block |
---|
private EnumSet<Option> options;
| Wiki Markup |
---|
h1. The Java Interface to CPLEX
The use of CPLEX in Java is based around the class IloCplex (documented [here|http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r5/index.jsp?topic=%2Filog.odms.cplex.help%2Frefjavacplex%2Fhtml%2Filog%2Fcplex%2FIloCplex.html]). The basic idea is that you create an IloCplex object for your optimization problem, then add variables, the objective, and constraints using methods in the class IloCplex. The IloCplex object can produce [IloNumVar|http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r5/index.jsp?topic=%2Filog.odms.cplex.help%2Frefjavacplex%2Fhtml%2Filog%2Fconcert%2FIloNumVar.html] objects and their subclass [IloIntVar|http://pic.dhe.ibm.com/infocenter/cosinfoc/v12r5/index.jsp?topic=%2Filog.odms.cplex.help%2Frefjavacplex%2Fhtml%2Filog%2Fconcert%2FIloIntVar.html] objects, when are then used as arguments to further methods from IloCplex to make the objective and constraints. The IloCplex interface is somewhat confusing. It is very large, has lots of redundant methods, and lots of methods that appear to be the same but produce very different results. We now summarize the methods of IloCplex which will be of use to us:
||Name||Return Type||Arguments||Description||
|boolVar|IloIntVar| |Creates and returns a new Boolean variable (domain 0,1).|
|boolVarArray|IloIntVar[]|int n |Creates and returns an array of n new Boolean variables (domain 0,1)|
|linearIntExpr|IloLinearIntExpr| |Creates and returns an integer linear expression initialized as 0 (zero).|
|addGe|IloRange|IloNumExpr e, double v|Creates and returns a range representing the constraint {mathinline} e \geq v{mathinline}|
|addEq|IloRange|IloNumExpr e, double v|Creates and returns a range representing the constraint {mathinline} e = v{mathinline}|
|addMinimize|IloObjective|IloNumExpr e|Creates and returns an objective to minimize the expression and adds it to the invoking model.|
{warning:Warning}
For a IloNumExpr e and a double v, calling cplex.addGe(e,v) and cplex.addGe(v,e) are both allowed but do not produce the same result! The first gives the constraint {mathinline} e \geq v{mathinline} while the second gives the constraint {mathinline}v \geq e{mathinline}.
{warning}
{warning:Warning}
For a IloNumExpr e and a double v, calling cplex.ge(e,v) and cplex.addGe(e,v) are both allowed but do not produce the same result! While both return an object for the constraint {mathinline} e \geq v{mathinline}, only the latter adds the constraint to the model! We will actually have use cplex.ge(e,v) later when we add constraints through callbacks instead of adding them directly to the model.
{warning}
h1. Using CPLEX in TspIpSolver
First, we need to set up the objective and the degree constraints. First, add the following fields to the class
{code}
private IloCplex cplex;
private TspInstance<V,E> tspInstance;
private final ImmutableBiMap<E,IloIntVar> edgeVariables;
{code}
|
and initialize them, as below.
{ 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}
The constraints and objective still need to be added to the {{cplex}} object. Try adding them yourself! The following methods should be useful for making the constraints:
* From {{Util}}, {{public static <T> IloLinearIntExpr integerSum(IloCplex cplex, BiMap<T,IloIntVar> variables, Iterable<T> set)}}
** For each element {mathinline}e{mathinline} of {{set}}, finds the corresponding variable {mathinline}x_e{mathinline} and returns {mathinline}\sum_{e \in \text{set}} x_e {mathinline}
* From {{IloCplex}}, {{public IloRange addEq(IloNumExpr e, double v)}}
** Adds the equality constraint e = v
* From {{UndirectedGraph<V,E>}}, {{public Collection<E> getIncidentEdges(V vertex)}}
** returns the edges of the graph that are incident to vertex
If you are unfamiliar with Java, consider viewing the solution for the constraint, then trying the objective yourself.
{toggle-cloak:id=ConstraintsSolution} _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}}, {{public static <T> IloLinearNumExpr sum(IloCplex cplex, BiMap<T,IloIntVar> variables, Iterable<T> set, Function<? super T,? extends Number> coefficients)}}
** For every element {mathinline}e{mathinline} of {{set}}, gets the corresponding variable {mathinline}x_e{mathinline} from {{variables}} and the number {mathinline}d_e{mathinline} from {{coefficients}} and returns an expression for {mathinline}\sum_{e \in \text{set}} d_e x_e {mathinline}.
{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}
| 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 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;
|
Next, we will set the field edgeVariablesAsArray by adding the one-liner to the constructor: Code Block |
---|
...
this.edgeVariables = Util.makeBinaryVariables(cplex, graph.getEdges());
edgeVariablesAsArray = 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. In designing this method, we must remember our previous discussion of numerical tolerances. 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;
}
|
The method edgesUsed() make look a little odd right now, but its value will become apparent in the next section. Test Your CodeNow 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: Gliffy Diagram |
---|
size | L |
---|
name | tspDegreeConstraints |
---|
|
|