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: user@commons.apache.org
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, <reginald.johnson@gmail.com> 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 <
> 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
> >
> >
> |