[gecode-users] graph constraints and hamiltonian path

[Jonathan Skovhus Andersen]

Hi Serge,

I have actually implemented just what you are requesting - the TSP that does
not return to it's starting point. I am a complete beginner
at GeCode so there are most likely a better way to do it, but I did it this
way.

Introduce this relation:
*rel(*this, totalNoEndPoint == total - p.d(p.size()-1,0));*

And then change your cost function to minimize totalNoEndPoint:
*virtual IntVar cost(void) const /// Return solution cost*
* {*
* return totalNoEndPoint;*
* }*
*
*
I hope that this will give you some ideas.

/Jonathan Skovhus.

2011/5/21 serge lemouton <serge.lemouton at ircam.fr>

> Dear Christian,
>
> Thanks for your idea, but I am not sure to understand how to implement it.
> Moreover, i don't know if it will work, because what i want to do is to
> find a path  minimizing the total distance through an ensemble of points,
> and it seems to me that the "circuit" constraint will always take into
> account the distance between the last and the first city in the salesman
> itinerary, isn't it ?
> It does not seem obvious to me that we can obtain the shortest path simply
> by removing the longest distance of the shortest circuit, but I am not an
> expert in hamiltonian graphs !
>
> Serge
>
> On 19 mai 2011, at 23:21, Christian Schulte wrote:
>
> > Hmmm. Just thinking: how about adding an additional node that is assigned
> to
> > lead back to the start node and then find a Hamiltonian circuit for this?
> > That should work, shouldn't it? Or am I missing something.
> >
> > Christian
> >
> > --
> > Christian Schulte, KTH, web.it.kth.se/~cschulte/
> >
> >
> > -----Original Message-----
> > From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On
> Behalf
> > Of serge lemouton
> > Sent: Thursday, May 19, 2011 9:32 PM
> > To: users at gecode.org
> > Subject: [gecode-users] graph constraints and hamiltonian path
> >
> > Hello,
> >
> > Question about graph constraints:
> > I would like to modify the the TSP example in order to find the solutions
> > where the travelling salesman should not return to its starting point.
> > In other terms, is it possible to use the "circuit" constraint to find an
> > hamiltonian path instead of a circuit ?
> > Does it require to modify the code or is it better to create another
> > subclass of the graph class ?
> >
> > Thanks for any advice,
> >
> > Serge Lemouton
> > _______________________________________________
> > Gecode users mailing list
> > users at gecode.org
> > https://www.gecode.org/mailman/listinfo/gecode-users
> >
> >
>
>
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20110522/264e5e6a/attachment.htm>