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 |
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] |
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 > |
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 >> > |
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] |
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] > > |
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] > > |
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 |
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] > > > > > |
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] > > > > > |
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] |
Free forum by Nabble | Edit this page |