RE: [AMPL 8070] Break sub-cycle not connected in a path
Robert Fourer
I think that you should start from the traveling salesman example that I am attaching. Although there exist an "exponential" number of subtour (sub-cycle) elimination constraints, tsp.run file only generates subtour elimination constraints that are actually violated by a solution. In general solution is found long before all such constraints are generated.
It seems to me that you want to do something similar, but for your model, which is somewhat different from mine. In particular, where I have an inner "repeat" loop that searches for any subtour, you need to write a loop that searches for a subtour that isn't linked to an s-t path. I can't tell you how to write that loop, but in general the idea is to start with one node (my statement "let EXTEND := ..." picks a random one) and follow the path through the node until you have a subcycle; then test that subcycle to see if it is one that you need to break.
Bob Fourer
From: am...@googlegroups.com [mailto:am...@googlegroups.com]
On Behalf Of fbi.g...@gmail.com
Sent: Monday, February 24, 2014 6:40 AM
To: am...@googlegroups.com
Subject: [AMPL 8070] Break sub-cycle not connected in a path
Hi all, I want to create a path from a source ( s ) to a target ( t ) while maximize a value ( v ) related to every no_arcs ( NOToriented_arcs ), and remain in a budget B and a time of path T ; In this path can exists sub-cycle , therefore every no_arcs can be cross max 2 times.
Now the question is: how can I broke the sub-cycle that aren't linked to the path s-t with an algorithm in the .run file? ( I do a similar thing in the TSP problem, but in that case I break all the sub-cycle because all of them aren't allowed; In this variant sub-cycle are allowed if they're linked to paths s-t )
I don't want to modelize it with costraint in the .mod because in that case I would have an exponential number of it...
