commons-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From <reginald.john...@gmail.com>
Subject Re: [math] Min Cost Flow Linear Programming Problem Using Optimization Package
Date Fri, 23 May 2014 13:27:00 GMT
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 <thomas.neidhart@gmail.com
> 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: user-unsubscribe@commons.apache.org
> For additional commands, e-mail: user-help@commons.apache.org
>
>
Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message