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: [email protected] 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, <[email protected]> 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 < > [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] > > > > >
