[math] Min Cost Flow Linear Programming Problem Using Optimization Package

classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

[math] Min Cost Flow Linear Programming Problem Using Optimization Package

reginald.johnson




  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
Reply | Threaded
Open this post in threaded view
|

Re: [math] Min Cost Flow Linear Programming Problem Using Optimization Package

Ted Dunning
In electrical and fluid flow problems, it is customary to encode flow to a node as positive and flow from as negative.  This reduces your constraints to a much simpler form

Sum_j A_ij = 0
A_ij = A_ji

Sent from my iPhone

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [math] Min Cost Flow Linear Programming Problem Using Optimization Package

reginald.johnson
I agree, and in fact my original formulation used that same format
(A_ij=A_ji) for the constraint.  However, I didn't (and still don't) see a
way to create a constraint in the optimization class that will let me use
anything other than a number for the right hand side.

  Do you know if this library has this ability?
On May 22, 2014 8:33 AM, "Ted Dunning" <[hidden email]> wrote:

> In electrical and fluid flow problems, it is customary to encode flow to a
> node as positive and flow from as negative.  This reduces your constraints
> to a much simpler form
>
> Sum_j A_ij = 0
> A_ij = A_ji
>
> Sent from my iPhone
>
Reply | Threaded
Open this post in threaded view
|

Re: [math] Min Cost Flow Linear Programming Problem Using Optimization Package

Ted Dunning
Is it possible that you encode the symmetry constraint into the function
itself by only allowing adaptation of the upper triangle?




On Thu, May 22, 2014 at 8:36 PM, Reginald Johnson <
[hidden email]> wrote:

> I agree, and in fact my original formulation used that same format
> (A_ij=A_ji) for the constraint.  However, I didn't (and still don't) see a
> way to create a constraint in the optimization class that will let me use
> anything other than a number for the right hand side.
>
>   Do you know if this library has this ability?
> On May 22, 2014 8:33 AM, "Ted Dunning" <[hidden email]> wrote:
>
>> In electrical and fluid flow problems, it is customary to encode flow to
>> a node as positive and flow from as negative.  This reduces your
>> constraints to a much simpler form
>>
>> Sum_j A_ij = 0
>> A_ij = A_ji
>>
>> Sent from my iPhone
>>
>
Reply | Threaded
Open this post in threaded view
|

Re: [math] Min Cost Flow Linear Programming Problem Using Optimization Package

Thomas Neidhart
In reply to this post by reginald.johnson
On 05/23/2014 05:36 AM, Reginald Johnson wrote:
> I agree, and in fact my original formulation used that same format
> (A_ij=A_ji) for the constraint.  However, I didn't (and still don't) see a
> way to create a constraint in the optimization class that will let me use
> anything other than a number for the right hand side.

The simplex solver in math does only support constants on the right
side, and I am not aware of another solver that would support it.

A possible way to express this constraint could be:

 A_ij - A_ji = 0

btw. you should not use the org.apache.commons.math3.optimization
package anymore. The contents are deprecated and have been refactored
into package org.apache.commons.math3.optim.

The SimplexSolver found there is more robust and faster.

Thomas

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [math] Min Cost Flow Linear Programming Problem Using Optimization Package

Ted Dunning
With no inequality constraints, the flow continuity constraint should not
require a simplex solver.

If there are limitations on maximum flow on some or all links then simplex
does come into play.  Without such limits, not.  IF there are non-linear
flow relations such as come into play in hydraulic systems, then simplex is
not practical.



On Thu, May 22, 2014 at 11:22 PM, Thomas Neidhart <[hidden email]
> wrote:

> On 05/23/2014 05:36 AM, Reginald Johnson wrote:
> > I agree, and in fact my original formulation used that same format
> > (A_ij=A_ji) for the constraint.  However, I didn't (and still don't) see
> a
> > way to create a constraint in the optimization class that will let me use
> > anything other than a number for the right hand side.
>
> The simplex solver in math does only support constants on the right
> side, and I am not aware of another solver that would support it.
>
> A possible way to express this constraint could be:
>
>  A_ij - A_ji = 0
>
> btw. you should not use the org.apache.commons.math3.optimization
> package anymore. The contents are deprecated and have been refactored
> into package org.apache.commons.math3.optim.
>
> The SimplexSolver found there is more robust and faster.
>
> Thomas
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [hidden email]
> For additional commands, e-mail: [hidden email]
>
>
Reply | Threaded
Open this post in threaded view
|

Re: [math] Min Cost Flow Linear Programming Problem Using Optimization Package

reginald.johnson
In the problem, the inequality constraints are the following

Each node must be visited at least once:  Xij>=1  

What goes in to each node must come out of it: Xij=Xji


  Basically, what I’ve been trying to do is to use LP to solve the Traveling Salesman Problem.  The techniques I’m following are discussed in this paper: http://www.economicsnetwork.ac.uk/iree/v10n1/rasmussen.pdf


  I’ve successfully been able to use the formulations listed (including implementation of the subtour elimination constraints) to create a working model in Microsoft Excel using the standard Excel solver. Unfortunately, I haven’t had any success in rebuilding the model in the various LP packages I’ve tried in Java (lp_solve, GLPK, Joptimizer).


  Unfortunately, I think that even if I was able to build the constraint that was the subject of my original question, I don’t think I’d be able to implement the subtour elimination constraints since they involve the use of a dummy variable, and I don’t see a way to implement those using math.commons.






Sent from Windows Mail





From: Ted Dunning
Sent: ‎Friday‎, ‎May‎ ‎23‎, ‎2014 ‎6‎:‎17‎ ‎AM
To: Commons Users List





With no inequality constraints, the flow continuity constraint should not
require a simplex solver.

If there are limitations on maximum flow on some or all links then simplex
does come into play.  Without such limits, not.  IF there are non-linear
flow relations such as come into play in hydraulic systems, then simplex is
not practical.



On Thu, May 22, 2014 at 11:22 PM, Thomas Neidhart <[hidden email]
> wrote:

> On 05/23/2014 05:36 AM, Reginald Johnson wrote:
> > I agree, and in fact my original formulation used that same format
> > (A_ij=A_ji) for the constraint.  However, I didn't (and still don't) see
> a
> > way to create a constraint in the optimization class that will let me use
> > anything other than a number for the right hand side.
>
> The simplex solver in math does only support constants on the right
> side, and I am not aware of another solver that would support it.
>
> A possible way to express this constraint could be:
>
>  A_ij - A_ji = 0
>
> btw. you should not use the org.apache.commons.math3.optimization
> package anymore. The contents are deprecated and have been refactored
> into package org.apache.commons.math3.optim.
>
> The SimplexSolver found there is more robust and faster.
>
> Thomas
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [hidden email]
> For additional commands, e-mail: [hidden email]
>
>
Reply | Threaded
Open this post in threaded view
|

Re: [math] Min Cost Flow Linear Programming Problem Using Optimization Package

reginald.johnson
In reply to this post by Ted Dunning
Unfortunately, I’m not familiar enough with LP to know what you mean by that statement.






Sent from Windows Mail





From: Ted Dunning
Sent: ‎Thursday‎, ‎May‎ ‎22‎, ‎2014 ‎9‎:‎13‎ ‎PM
To: Reginald Johnson
Cc: [hidden email]







Is it possible that you encode the symmetry constraint into the function itself by only allowing adaptation of the upper triangle?










On Thu, May 22, 2014 at 8:36 PM, Reginald Johnson <[hidden email]> wrote:



I agree, and in fact my original formulation used that same format (A_ij=A_ji) for the constraint.  However, I didn't (and still don't) see a way to create a constraint in the optimization class that will let me use anything other than a number for the right hand side.  

  Do you know if this library has this ability?



On May 22, 2014 8:33 AM, "Ted Dunning" <[hidden email]> wrote:

In electrical and fluid flow problems, it is customary to encode flow to a node as positive and flow from as negative.  This reduces your constraints to a much simpler form

Sum_j A_ij = 0
A_ij = A_ji

Sent from my iPhone
Reply | Threaded
Open this post in threaded view
|

Re: [math] Min Cost Flow Linear Programming Problem Using Optimization Package

Thomas Neidhart
In reply to this post by reginald.johnson
The paper here http://arxiv.org/vc/cs/papers/0609/0609005v5.pdf [arxiv.org]
shows how the TSP can be solved by using a linear programming model.

Afaik, the standard approach is to use integer LP which commons math does
not yet support, but the referenced paper also shows a way to do it with
standard LP.

Thomas



On Fri, May 23, 2014 at 3:27 PM, <[hidden email]> wrote:

> In the problem, the inequality constraints are the following
>
> Each node must be visited at least once:  Xij>=1
>
> What goes in to each node must come out of it: Xij=Xji
>
>
>   Basically, what I’ve been trying to do is to use LP to solve the
> Traveling Salesman Problem.  The techniques I’m following are discussed in
> this paper: http://www.economicsnetwork.ac.uk/iree/v10n1/rasmussen.pdf
>
>
>   I’ve successfully been able to use the formulations listed (including
> implementation of the subtour elimination constraints) to create a working
> model in Microsoft Excel using the standard Excel solver. Unfortunately, I
> haven’t had any success in rebuilding the model in the various LP packages
> I’ve tried in Java (lp_solve, GLPK, Joptimizer).
>
>
>   Unfortunately, I think that even if I was able to build the constraint
> that was the subject of my original question, I don’t think I’d be able to
> implement the subtour elimination constraints since they involve the use of
> a dummy variable, and I don’t see a way to implement those using
> math.commons.
>
>
>
>
>
>
> Sent from Windows Mail
>
>
>
>
>
> From: Ted Dunning
> Sent: ‎Friday‎, ‎May‎ ‎23‎, ‎2014 ‎6‎:‎17‎ ‎AM
> To: Commons Users List
>
>
>
>
>
> With no inequality constraints, the flow continuity constraint should not
> require a simplex solver.
>
> If there are limitations on maximum flow on some or all links then simplex
> does come into play.  Without such limits, not.  IF there are non-linear
> flow relations such as come into play in hydraulic systems, then simplex is
> not practical.
>
>
>
> On Thu, May 22, 2014 at 11:22 PM, Thomas Neidhart <
> [hidden email]
> > wrote:
>
> > On 05/23/2014 05:36 AM, Reginald Johnson wrote:
> > > I agree, and in fact my original formulation used that same format
> > > (A_ij=A_ji) for the constraint.  However, I didn't (and still don't)
> see
> > a
> > > way to create a constraint in the optimization class that will let me
> use
> > > anything other than a number for the right hand side.
> >
> > The simplex solver in math does only support constants on the right
> > side, and I am not aware of another solver that would support it.
> >
> > A possible way to express this constraint could be:
> >
> >  A_ij - A_ji = 0
> >
> > btw. you should not use the org.apache.commons.math3.optimization
> > package anymore. The contents are deprecated and have been refactored
> > into package org.apache.commons.math3.optim.
> >
> > The SimplexSolver found there is more robust and faster.
> >
> > Thomas
> >
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: [hidden email]
> > For additional commands, e-mail: [hidden email]
> >
> >
>
Reply | Threaded
Open this post in threaded view
|

Re: [math] Min Cost Flow Linear Programming Problem Using Optimization Package

reginald.johnson
Do you know of a library that does support ILP?






Sent from Surface





From: Thomas Neidhart
Sent: ‎Friday‎, ‎May‎ ‎23‎, ‎2014 ‎6‎:‎57‎ ‎AM
To: [hidden email]





The paper here http://arxiv.org/vc/cs/papers/0609/0609005v5.pdf [arxiv.org]
shows how the TSP can be solved by using a linear programming model.

Afaik, the standard approach is to use integer LP which commons math does
not yet support, but the referenced paper also shows a way to do it with
standard LP.

Thomas



On Fri, May 23, 2014 at 3:27 PM, <[hidden email]> wrote:

> In the problem, the inequality constraints are the following
>
> Each node must be visited at least once:  Xij>=1
>
> What goes in to each node must come out of it: Xij=Xji
>
>
>   Basically, what I’ve been trying to do is to use LP to solve the
> Traveling Salesman Problem.  The techniques I’m following are discussed in
> this paper: http://www.economicsnetwork.ac.uk/iree/v10n1/rasmussen.pdf
>
>
>   I’ve successfully been able to use the formulations listed (including
> implementation of the subtour elimination constraints) to create a working
> model in Microsoft Excel using the standard Excel solver. Unfortunately, I
> haven’t had any success in rebuilding the model in the various LP packages
> I’ve tried in Java (lp_solve, GLPK, Joptimizer).
>
>
>   Unfortunately, I think that even if I was able to build the constraint
> that was the subject of my original question, I don’t think I’d be able to
> implement the subtour elimination constraints since they involve the use of
> a dummy variable, and I don’t see a way to implement those using
> math.commons.
>
>
>
>
>
>
> Sent from Windows Mail
>
>
>
>
>
> From: Ted Dunning
> Sent: ‎Friday‎, ‎May‎ ‎23‎, ‎2014 ‎6‎:‎17‎ ‎AM
> To: Commons Users List
>
>
>
>
>
> With no inequality constraints, the flow continuity constraint should not
> require a simplex solver.
>
> If there are limitations on maximum flow on some or all links then simplex
> does come into play.  Without such limits, not.  IF there are non-linear
> flow relations such as come into play in hydraulic systems, then simplex is
> not practical.
>
>
>
> On Thu, May 22, 2014 at 11:22 PM, Thomas Neidhart <
> [hidden email]
> > wrote:
>
> > On 05/23/2014 05:36 AM, Reginald Johnson wrote:
> > > I agree, and in fact my original formulation used that same format
> > > (A_ij=A_ji) for the constraint.  However, I didn't (and still don't)
> see
> > a
> > > way to create a constraint in the optimization class that will let me
> use
> > > anything other than a number for the right hand side.
> >
> > The simplex solver in math does only support constants on the right
> > side, and I am not aware of another solver that would support it.
> >
> > A possible way to express this constraint could be:
> >
> >  A_ij - A_ji = 0
> >
> > btw. you should not use the org.apache.commons.math3.optimization
> > package anymore. The contents are deprecated and have been refactored
> > into package org.apache.commons.math3.optim.
> >
> > The SimplexSolver found there is more robust and faster.
> >
> > Thomas
> >
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: [hidden email]
> > For additional commands, e-mail: [hidden email]
> >
> >
>
Reply | Threaded
Open this post in threaded view
|

Re: [math] Min Cost Flow Linear Programming Problem Using Optimization Package

Thomas Neidhart
On 05/24/2014 07:40 AM, [hidden email] wrote:
> Do you know of a library that does support ILP?

glpk supports integer and mixed linear programming problems.

I am not aware of a java based library though.

Thomas

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]