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 <[email protected] > 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: [email protected] > For additional commands, e-mail: [email protected] > >
