commons-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
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:

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