[math] Min Cost Flow Linear Programming Problem Using Optimization Package Classic List Threaded 11 messages Open this post in threaded view
|

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

 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 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= 1         for(int i=0; i=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
Open this post in threaded view
|

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 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] > > > > >