h1. A Road to Trouble
When programming in Java, you generally have [collections|http://docs.oracle.com/javase/tutorial/collections/] of objects, as previously discussed [here|Do you know Java]. Often, you want to create a variable (or constraint) for element of a collection. A *bad* approach is illustrated below:
{code}
Set<String> stringCollection = makeSomeStrings();//assume this is defined elsewhere
IloCplex cplex = new IloCplex();
String[] stringToIndex = new String[stringCollection.size()];
IloIntVar[] variablesToIndex = cplex.boolVarArray(stringCollection.size());
int i = 0;
for(String s: stringCollection){
stringToIndex[i++] = s;
}
{code}
Then given a String from the collection, we could access the corresponding IloIntVar, and with an IloIntVar, we would access the corresponding String, with the following snippets
{code}
public IloIntVar getVariableForString(String s, String[] stringToIndex, IloIntVar[] variablesToIndex){
for(int i = 0; i < stringToIndex.length; i++){
if(stringToIndex[i].equals(s)){
return variablesToIndex[i];
}
}
return null;
}
public String getStringForVariable(IloIntVar v, String[] stringToIndex, IloIntVar[] variablesToIndex){
for(int i = 0; i < variablesToIndex.length; i++){
if(variablesToIndex[i] == v){
return stringToIndex[i];
}
}
return null;
}
{code}
There are several reasons to be concerned with this.
* For {mathinline}n{mathinline} variables, access time takes {mathinline}O(n){mathinline}.
* We are maintaining two data structures and an index by hand, which leave a lot of room for programmer error
* We cannot add new variables at a later date
We can eliminate any chance of an indexing error and improve our access time to {mathinline}O(1){mathinline} by replacing our two arrays by two [HashMaps|http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html], e.g.
{code}
Set<String> stringCollection = makeSomeStrings();//assume this is defined elsewhere
IloCplex cplex = new IloCplex();
Map<String,IloIntVar> stringToVariable = new HashMap<String,IloIntVar>();
Map<IloIntVar,String> variableToString = new HashMap<IloIntVar,String>();
for(String s: stringCollection){
IloIntVar v = cplex.boolVar();
stringToVariable.put(s,v);
variableToString.put(v,s);
}
{code}
However, we are still maintaining two separate data structures which we need to keep synchronized, which is asking for trouble.
h1. Good Style
Instead, we use [Guava's|http://code.google.com/p/guava-libraries/wiki/GuavaExplained?tm=6] special data structure, the [ImmutableBiMap|http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/ImmutableBiMap.html], which will maintain two HashMaps for us (and as a bonus, prevent any accidental modifications once we _build_ the map). The following methods can be found in Util.java in your project:
{code}
public static <T> ImmutableBiMap<T,IloIntVar> makeBinaryVariables(IloCplex cplex, Iterable<T> set) throws IloException{
Builder<T,IloIntVar> ans = ImmutableBiMap.builder();
for(T t: set){
ans.put(t, cplex.boolVar());
}
return ans.build();
}
{code}
Now the unfortunate code from before can be replaced by
{code}
Set<String> stringCollection = makeSomeStrings();//assume this is defined elsewhere
IloCplex cplex = new IloCplex();
ImmutableBiMap<String,IloIntVar> stringVarBiMap = Util.makeBinaryVariables(cplex,stringCollection);
for(String s: stringCollection){
stringVarMap.put(s,cplex.boolVar());
}
public IloIntVar getVariableForString(String s, ImmutableBiMap<String,IloIntVar> stringVarBiMap){
return stringVarBiMap.get(s);
}
public String getStringForVariable(IloIntVar v, ImmutableBiMap<String,IloIntVar> stringVarBiMap){
return stringVarBiMap.inverse().get(v);
}
{code}
There are a few additional methods in the class Util for creating IloLinearIntExpr objects and IloLinearNumExpr objects designed to keep your code organized and error free. They use another Guava class, [Function|http://code.google.com/p/guava-libraries/wiki/FunctionalExplained], (see [here|http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/base/Function.html] for Javadoc). The idea of a Function<F,T> is simple, they take in any object of type F and produce some object of type T. Functions are a little clunky to make (a weakness of Java), but fortunately you won't have to make many. The follwing static functions are also found in Util
||Method Name||Return Type||Arguments||Description||
|integerSum|IloLinearIntExpr|IloCplex cplex, BiMap<T,IloIntVar> variables, Iterable<T> set|For each {mathinline} e \in \text{set}{mathinline} finds the variable {mathinline} x_e {mathinline} in variables and returns {mathinline} \sum_{e \in \text{set}} x_e{mathinline}|
|integerSum|IloLinearIntExpr|IloCplex cplex, BiMap<T,IloIntVar> variables, Iterable<T> set,Function<? super T,Integer> coefficients|For each {mathinline} e \in \text{set}{mathinline} finds the variable {mathinline} x_e {mathinline} in variables and {mathinline}c_e{mathinline} by applying coefficients to {mathinline}e{mathinline} and returns {mathinline} \sum_{e \in \text{set}} c_e x_e{mathinline}|
{code}
public static <T> IloLinearIntExpr integerSum(IloCplex cplex,
BiMap<T,IloIntVar> variables, Iterable<T> set,
Function<? super T,Integer> coefficients) throws IloException{
IloLinearIntExpr sum = cplex.linearIntExpr();
for(T t: set){
sum.addTerm(variables.get(t), coefficients.apply(t));
}
return sum;
}
public static <T> IloLinearIntExpr integerSum(IloCplex cplex,
BiMap<T,IloIntVar> variables, Iterable<T> set) throws IloException{
return integerSum(cplex,variables,set,unity);
}
private static Function<Object,Integer> unity = new Function<Object,Integer>(){
@Override
public Integer apply(Object arg0) {
return 1;
}};
{code}
h1. Simple Example Revisited
Recall the IP we modeled with CPLEX in the previous section:
{mathdisplay}
\begin{aligned}
&\min & x + 2y + 3z\\
&\text{subject to}& x + y + z &\geq 2\\
&& x,y,z &\in\{0,1\}
\end{aligned}
{mathdisplay}
Lets design a more scalable implementation using our new methods. Try and finish the following stub.
{code}
List<String> varNames = Arrays.asList("x","y","z");
Map<String,Integer> weightsMap = new HashMap<String,Integer>();
weightsMap.put("x",1);
weightsMap.put("y",2);
weightsMap.put("z",3);
Function<String,Integer> weights = Functions.forMap(weightsMap);
{code}
{toggle-cloak:id=GoodStyleSolution} _Solution_
{cloak:id=GoodStyleSolution|visible=false}
{code}
ImmutableBiMap<String,IloIntVar> varMap = Util.makeBinaryVariables(cplex,varNames);
cplex.addGe(Util.integerSum(cplex,varMap,varNames),2);
cplex.addMinimize(Util.integerSum(cplex.varMap,varNames,weights));
{code}
{cloak}
|