{

Wiki Markup
Composition Setup

Section

Column

width	300px

Page Tree

root	Tutorial

} {composition-setup} {section} {column:width=300px} {pagetree:root=Tutorial} {column} {column} 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}

Column

A Road to Trouble

When programming in Java, you generally have collections of objects, as previously discussed here. Often, you want to create a variable (or constraint) for element of a collection. A bad approach is illustrated below:

Code Block


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 Block

}


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}

For
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}

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

by replacing our two arrays by two HashMaps, e.g.

Code Block


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

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 Block

}


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 Block

}


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|| |{anchor:integerSum}integerSum|IloLinearIntExpr|IloCplex cplex,

Description

Anchor

	integerSum
	integerSum

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}| |{anchor:calcSum}calcSum|double|Set<E> terms, Map<E,Double> coefficients|If for every {mathinline}e \in \text{terms}{mathinline}, we let {mathinline}c_e{mathinline} be zero if coefficients does not contain the key {mathinline}e{mathinline} and the value of {mathinline}e{mathinline} coefficientsComputes otherwise, returns {mathinline} \sum_{e \in \text{terms}} c_e{mathinline}.| While the final function actually has nothing to do with CPLEX, it will often be useful when using CPLEX. h1. Simple Example Revisited Recall the IP we modeled with CPLEX in the previous section: {mathdisplay}

Mathinline

finds the variable

Mathinline

in variables and returns

Mathinline

integerSum

IloLinearIntExpr

IloCplex cplex, BiMap<T,IloIntVar> variables, Iterable<T> set,Function<? super T,Integer> coefficients

For each

Mathinline

finds the variable

Mathinline

in variables and

Mathinline

by applying coefficients to

Mathinline

and returns

Mathinline

Anchor

	calcSum
	calcSum

calcSum

double

Set<E> terms, Map<E,Double> coefficients

If for every

Mathinline

, we let

Mathinline

be zero if coefficients does not contain the key

Mathinline

and the value of

Mathinline

coefficientsComputes otherwise, returns

Mathinline

.

While the final function actually has nothing to do with CPLEX, it will often be useful when using CPLEX.

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.

Finish

the

method

{{

exercise2()

}}

from

_

WarmUps.java

_

,

which

currently

reads

{

Code Block

}


public static void exerciseTwo() throws IloException{
	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);
	IloCplex cplex = new IloCplex();
	//write code here!
}

{code}

The

functionality

should

be

the

same

as

{{

exercise1()

}}

.

Modify

the

{{

main

}}

method

to

test

your

code.

{

Toggle Cloak

:

id

=

	GoodStyleSolution

} _Solution_ {cloak:id=GoodStyleSolution|visible=false} {code} public static void exerciseTwo() throws IloException{ 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); IloCplex cplex = new IloCplex(); //write code here! ImmutableBiMap<String,IloIntVar> varMap = Util.makeBinaryVariables(cplex,varNames); cplex.addGe(Util.integerSum(cplex,varMap,varNames),2); cplex.addMinimize(Util.integerSum(cplex,varMap,varNames,weights)); cplex.solve(); for(String varName: varNames){ System.out.println(varName +": " + cplex.getValue(varMap.get(varName))); } System.out.println("obj: " + cplex.getObjValue()); } {code} {cloak} {column} {section}

Solution

Cloak

visible	false
id	GoodStyleSolution

Child pages

Versions Compared

Old Version 12

New Version 13

Key

A Road to Trouble

Good Style

Simple Example Revisited

Child pages

Page History

Versions Compared

Old Version 12

New Version 13

Key

A Road to Trouble

Good Style

Simple Example Revisited