I am attempting to set up a min cost network flow linear programming problem
using the org.apache.commons.math3.optimization.linear package. I am having
problems setting up the constraints that dictate that any flow that goes into a
network node must also leave that node.
I’m looking for examples of how to build such a problem using this library.
The constraint takes the form of:
Sum(Xij) = Sum(Xji) for all i
Where the left hand side, Xij is the amount of flow (X) going into from node i
to all nodes j a nd the right hand side is the Sum of all the flow from nodes j
going into node i.
I currently have the constraint set up as shown below:
constraints.add(new LinearConstraint(dArrGoesInna[i], Relationship.EQ,
GetSumDoubleArray(dArrGoesOutta[i])));
However, I am not sure if this will work.
The code for building the model is below:
protected void Solve() throws Exception {
vars = new int[iNumDestinations];
//ConvertListTo2DArray(); //turn the list of path data into a 2D
array
//fill in an array of coefficients related to each node
double[] dArrObjFunc = new double[listNodePathData.size()];
for(int i=0; i< listNodePathData.size(); i++){
dArrObjFunc[i]=listNodePathData.get(i).GetWeight();
}
//collection to hold the constraints
Collection<LinearConstraint> constraints = new ArrayList();
//constrain the X values in the objective functions to be
// greater than 0 and less than one
// hopefully, this creates a binary constraint
double[] dArrayPathUsed = new double[listNodePathData.size()];
for(int i=0; i<listNodePathData.size(); i++){
dArrayPathUsed[i]=0;
constraints.add(new LinearConstraint(dArrayPathUsed,
Relationship.GEQ, 0));
//constraints.add(new LinearConstraint(dArrayPathUsed,
Relationship.LEQ, 1));
}
//constrating that every node must be visited at least once
// the values calcuated will be the same as to goes-inna values that
// will be used later
double[][] dArrGoesInna = new
double[iNumDestinations][listNodePathData.size()];
//initialize all cells in the matrix to 0
for(int i=0; i < iNumDestinations; i++){ //need a constraint for
each node
for(int j=0; j < listNodePathData.size(); j++){ //the coefficient
string will be equal to the number of paths
dArrGoesInna[i][j]=0;
}
}
//now switch the matrix cell to one so that the LHS of the constraint
looks like:
// 1X+0+0+0+0+1x+0+0+0+0+1x+0.....
for(int i=0; i < listNodePathData.size(); i++){ //need a constraint
for each node
for(int j=0; j < iNumDestinations; j++){ //the coefficient string
will be equal to the number of paths
if(j==i%iNumDestinations){
dArrGoesInna[j][i]=1;
}
}
}
//add the new constraint for each node that the information gathered
above is >= 1
for(int i=0; i<iNumDestinations; i++) {
constraints.add(new LinearConstraint(dArrGoesInna[i],
Relationship.GEQ, 1));
}
//build the goes-outa constraint so that we can create the goes-inn
goes outta
//the first iNumDestinations coefficients is the goes-outta portion
// the goes-inna is the same as what we calculated in the previous set
of constraints
//constrating that every node must be visited at least once
double[][] dArrGoesOutta = new
double[iNumDestinations][listNodePathData.size()];
//initialize all cells in the matrix to 0
for(int i=0; i < iNumDestinations; i++){ //need a constraint for
each node
for(int j=0; j < listNodePathData.size(); j++){ //the coefficient
string will be equal to the number of paths
dArrGoesOutta[i][j]=1;
}
}
//now switch the matrix cell to one so that the LHS of the constraint
looks like:
// 1X+1X+1X+1X+0+0+ ... where all the 0's are thing leaving other nodes
int iStartPoint = 0;
int iEndPoint = iStartPoint + iNumDestinations;
for(int i=0; i < iNumDestinations; i++){ //need a constraint for
each node
for(int j=0; j < listNodePathData.size(); j++){ //the coefficient
string will be equal to the number of paths
if((j<iStartPoint)||(j>=iEndPoint)) {
dArrGoesOutta[i][j] = 0;
}
}
iStartPoint = iEndPoint;
iEndPoint = iStartPoint + iNumDestinations;
}
//add the new constraint for each node what goes in must come out
for(int i=0; i<iNumDestinations; i++) {
constraints.add(new LinearConstraint(dArrGoesInna[i],
Relationship.EQ, GetSumDoubleArray(dArrGoesOutta[i])));
}
LinearObjectiveFunction f = new LinearObjectiveFunction(dArrObjFunc, 0);
SimplexSolver solver = new SimplexSolver();
PointValuePair solution = solver.optimize(f, constraints,
GoalType.MINIMIZE, true);
//L.td(context, sol.toString());
}
Sent from Windows Mail
