# commons-user mailing list archives

##### Site index · List index
Message view
Top
From <reginald.john...@gmail.com>
Subject [math] Min Cost Flow Linear Programming Problem Using Optimization Package
Date Thu, 22 May 2014 03:24:44 GMT
```

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:

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;

}

//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++) {
}

//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++) {
}

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```
Mime
• Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message