Dynamic generation of subtour elimination constraints in AMPL

[Atri Mahapatra]

Dear Bob,

I have read your explanation about sub tour elimination constraints in the AMPL discussion forum. I have a question regarding generating sub tour elimination constraints. For smaller  cases, I understand that one can create a set called POW[k] for each element k in  S and then use a binary representation to indicate which vertices are in POW[k].

From the explanation, it is evident that the number of constraints increases exponentially in n. My question is - is there any dynamic way of generating subtour elimination constraints in AMPL?, i,e,  AMPL will identify when subtour elimination constraints is needed and those constraints  will be generated by AMPL dynamically when needed  so that  we do not have to write those constraints manually .


I look forward to hearing from you.

Thanks,
Atri

[Robert Fourer]

The attached file tsp.mod shows an example of a formulation (for the traveling salesman problem in this case) where a collection of subtours to be eliminated is given as data, rather than all subtour elimination constraints being generated in advance.  Also tsp.dat gives an example of corresponding data for a small instance.

 

Of course this leaves it to you to choose which subtour elimination constraints to include in the data.  AMPL cannot automatically decide which subtour elimination constraints need to be included.  You may be able to write an AMPL script that looks at a solution, finds one or more subtours (if any exist), and changes nSubtours and SUB appropriately so as to add those subtours (thus making specification of the subtours in the dat file unnecessary).  However I do not have an example of such a script.

 

Bob Fourer

am...@googlegroups.com

 

 

From: am...@googlegroups.com [mailto:am...@googlegroups.com]

On Behalf Of Atri Mahapatra
Sent: Saturday, July 27, 2013 5:42 PM
To: Robert Fourer; am...@googlegroups.com
Subject: [AMPL 7299] Dynamic generation of subtour elimination constraints in AMPL

[Atri Mahapatra]

Dear Bob,

Thanks for the suggestion. It helps me in understanding how to approach the problem. However, I am stuck in writing such a script that will look at the solution and add sub tours accordingly. Can you direct me to a source that guides in general  how to write a script that looks a solution and generates appropriate constraints? This general idea can help me in writing this specific script.

I look forward to hearing from you.

Thanks,
Atri

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.
To post to this group, send email to am...@googlegroups.com.
Visit this group at http://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[arun lila]

Hi Arti, 

I believe three ways to do it

1. Create a script which will check if the solution contains any sub tour, if yes add the constraint to eliminate the sub tour. repeat the process untill  your solution doesnot contain any subtour.

2. If you are using Cplex than you can also use cplexlazyconstraintcallback facility to dynamically add the cuts.

3. You can use the bender decomposition for the sub tour elimination constraint , where cut will be added automatically to model.

I hope the information helps you.

Thanks

Arun Lila 

[Robert Fourer]

The attached script file tsp.run gives a simple example of a loop that solves an incomplete traveling salesman problem formulation and then generates a random subtour elimination constraint based on the solution.  After a finite number of passes through the loop, there will be no more subtours in the solution, and an optimal tour will be displayed.  With more work, constraints could be generated for all subtours in the solution at each pass, instead of just one.

 

This script provides an illustration of the concept of subtour elimination.  However it should not be considered as providing a realistic approach to solving hard TSPs; a specialized large-scale TSP solver like Concorde (www.math.uwaterloo.ca/tsp/concorde/) is much too complex to code in AMPL scripts.

 

Bob Fourer

am...@googlegroups.com

 

 

From: am...@googlegroups.com [mailto:am...@googlegroups.com]

On Behalf Of Atri Mahapatra
Sent: Monday, July 29, 2013 11:10 PM
To: am...@googlegroups.com; Robert Fourer
Subject: Re: [AMPL 7308] Dynamic generation of subtour elimination constraints in AMPL