A Road to Trouble
When programming in Java, you generally have collections
of objects, as discussed here. Often, you want to create a variable (or constraint) for element of a collection. A bad approach is illustrated below:
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;
}
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
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;
}
There are several reasons to be concerned with this.
- For \( n \) variables, access time takes \( O(n) \) .
- 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
\( O(1) \)
by replacing our two arrays by two HashMaps, e.g.
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);
}
However, we are still maintaining two separate data structures which we need to keep synchronized, which is asking for trouble.
Good Style
Instead, we use Guava's special data structure, the ImmutableBiMap, 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:
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();
}
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;
}};