Is there a way to implement a subtour constraint without a run file?

[vinh k]

I am trying to implement a subtour constraint using Miller-tucker-Zemlin(MTZ) constraint but it seems this reference https://groups.google.com/forum/#!searchin/ampl/subtour%7Csort:date/ampl/FVQ-iZIhUHg/ZT2rPNP4BAAJ which I went to this https://groups.google.com/forum/#!msg/ampl/mVsFg4mAI1c/ZdfRHHRijfUJ . Is there a way to implement a constraint without the run file? Can it be implemented using just a constraint in model file? I am using MATLAB API for AMPL.

Thanks

[AMPL Google Group]

The subtour elimination constraints in that link are stronger subtour elimination cuts that can only be generated iteratively for each subtour found. However, these are not Miller-tucker-Zemlin(MTZ) cuts, which can be introduced in your model as follows:

param n := card(NODES);
param start symbolic := first(NODES);
var u{i in NODES}, >= 0;

# Miller, Tucker and Zemlin (MTZ) (1960)
subject to MTZ{(i,j) in PAIRS: i != start}:
u[i]-u[j]+(n-1)*X[i,j] <= n-2;

You may also be interested in the stronger Desrochers and Laporte (1991) cuts, which are very similar but slightly stronger:

# Desrochers and Laporte (1991)
subject to DL{(i,j) in PAIRS: i != start}:
u[i]-u[j]+(n-1)*X[i,j]+(n-3)*X[j,i] <= n-2;

I have attached a model and a data file with these cuts. Please note that for large scale problems these cuts will not be enough and you will need to use stronger cuts such as the ones in that link.

Best regards,
Filipe

--
Filipe Brandão
am...@googlegroups.com

{#HS:634145233-17576#}

On Fri, Aug 3, 2018 at 3:51 PM UTC, Ampl Modeling Language <am...@googlegroups.com> wrote:

I am trying to implement a subtour constraint using Miller-tucker-Zemlin(MTZ) constraint but it seems this reference https://groups.google.com/forum/#!searchin/ampl/subtour%7Csort:date/ampl/FVQ-iZIhUHg/ZT2rPNP4BAAJ which I went to this https://groups.google.com/forum/#!msg/ampl/mVsFg4mAI1c/ZdfRHHRijfUJ . Is there a way to implement a constraint without the run file? Can it be implemented using just a constraint in model file? I am using MATLAB API for AMPL.

Thanks

--
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 https://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.

[vinhk...@gmail.com]

Thanks you very much for the insight.

[vinh k]

Thanks Filipe Brandão. This is exactly what I needed. Even better, you had the code. Hats off to you.

[vinhk...@gmail.com]

Hi Filipe Brandão,

I have modified the code a bit so that I can integrate 3 vehicles. However, I am not sure if I am doing it correctly.

Here is the data:

set WAYPNTS[1] :=    1   2   3   4   5   6   7   8;

set WAYPNTS[2] :=    1   2   3   4   5   6   7   8;

set WAYPNTS[3] :=    1   2   3   4   5   6   7   8;

param:VEHICLE:sizeWaypnts :=

   1                   8

   2                   8

   3                   8;

Here is the model:

set VEHICLE ordered;

set WAYPNTS {VEHICLE} ordered; 

param sizeWaypnts{VEHICLE};             #number of waypoints for each vehicle 

set PAIRS:={v in VEHICLE,i in WAYPNTS[v], j in WAYPNTS[v]: i!=j};

var E{v in VEHICLE, i in WAYPNTS[v], j in WAYPNTS[v]} binary;            #sweeping variable

var u{v in VEHICLE,i in WAYPNTS[v]}, >= 0;                            #sequence number in a tour 

# subtour elimination Miller, Tucker and Zemlin (MTZ) (1960)

subject to MTZ{v in VEHICLE,(v,i,j) in PAIRS: i != 1}: u[v,i]-u[v,j] + (sizeWaypnts[v]-1)*E[v,i,j] <=sizeWaypnts[v]-1;

My ultimate goal is to have multiple vehicle subtour constraint. For each vehicle initial node is 1 and node 8 should be visited last.

I can not seem to get the proper result for this case as there is still subtour in this implementation. Did I write it wrong?

On Friday, August 3, 2018 at 11:50:56 AM UTC-4, vinh k wrote:

[AMPL Google Group]

The constraints enforcing that each waypoint is visited once are missing, and the right hand side of MTZ constraints should be sizeWaypnts[v]-2 instead of sizeWaypnts[v]-1.

Please try with the following model:

set VEHICLE ordered;
set WAYPNTS {VEHICLE} ordered;

param sizeWaypnts{VEHICLE}; #number of waypoints for each vehicle

set PAIRS {v in VEHICLE} := {i in WAYPNTS[v], j in WAYPNTS[v]: i!=j};

var E{v in VEHICLE, PAIRS[v]} binary; #sweeping variable
var u{v in VEHICLE, WAYPNTS[v]}, >= 0, <= sizeWaypnts[v]-1; #sequence number in a tour

subject to LeaveOnce {v in VEHICLE, i in WAYPNTS[v]}:
sum {(i,j) in PAIRS[v]} E[v,i,j] = 1;

subject to VisitOnce {v in VEHICLE, j in WAYPNTS[v]}:
sum {(i,j) in PAIRS[v]} E[v,i,j] = 1;

# subtour elimination Miller, Tucker and Zemlin (MTZ) (1960)

subject to MTZ{v in VEHICLE,(i,j) in PAIRS[v]: i != 1}: u[v,i]-u[v,j] + (sizeWaypnts[v]-1)*E[v,i,j] <=sizeWaypnts[v]-2;

The output is the following:

E [1,*,*]
: 1 2 3 4 5 6 7 8 :=
1 . 1 0 0 0 0 0 0
2 0 . 0 0 0 1 0 0
3 0 0 . 1 0 0 0 0
4 0 0 0 . 1 0 0 0
5 0 0 0 0 . 0 0 1
6 0 0 0 0 0 . 1 0
7 0 0 1 0 0 0 . 0
8 1 0 0 0 0 0 0 .

[2,*,*]
: 1 2 3 4 5 6 7 8 :=
1 . 0 0 0 0 1 0 0
2 1 . 0 0 0 0 0 0
3 0 0 . 0 0 0 1 0
4 0 1 0 . 0 0 0 0
5 0 0 1 0 . 0 0 0
6 0 0 0 0 0 . 0 1
7 0 0 0 1 0 0 . 0
8 0 0 0 0 1 0 0 .

[3,*,*]
: 1 2 3 4 5 6 7 8 :=
1 . 0 1 0 0 0 0 0
2 1 . 0 0 0 0 0 0
3 0 0 . 0 0 1 0 0
4 0 0 0 . 1 0 0 0
5 0 0 0 0 . 0 1 0
6 0 0 0 0 0 . 0 1
7 0 1 0 0 0 0 . 0
8 0 0 0 1 0 0 0 .
;

u [*,*] (tr)
: 1 2 3 :=
1 7 7 7
2 0 6 6
3 3 3 0
4 4 5 3
5 5 2 4
6 1 0 1
7 2 4 5
8 6 1 2
;

Best regards,
Filipe

--
Filipe Brandão
am...@googlegroups.com

{#HS:634145233-17576#}

On Sun, Aug 5, 2018 at 1:05 PM UTC, Ampl Modeling Language <am...@googlegroups.com> wrote:

Thanks you very much for the insight.

--
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 https://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.

On Sun, Aug 5, 2018 at 1:05 PM UTC, Ampl Modeling Language <am...@googlegroups.com> wrote:

Thanks Filipe Brandão. This is exactly what I needed. Even better, you had
the code. Hats off to you.

On Fri, Aug 3, 2018 at 10:05 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

The subtour elimination constraints in that link are stronger subtour elimination cuts that can only be generated iteratively for each subtour found. However, these are not Miller-tucker-Zemlin(MTZ) cuts, which can be introduced in your model as follows:

param n := card(NODES);
param start symbolic := first(NODES);
var u{i in NODES}, >= 0;

# Miller, Tucker and Zemlin (MTZ) (1960)
subject to MTZ{(i,j) in PAIRS: i != start}:
u[i]-u[j]+(n-1)*X[i,j] <= n-2;

You may also be interested in the stronger Desrochers and Laporte (1991) cuts, which are very similar but slightly stronger:

# Desrochers and Laporte (1991)
subject to DL{(i,j) in PAIRS: i != start}:
u[i]-u[j]+(n-1)*X[i,j]+(n-3)*X[j,i] <= n-2;

I have attached a model and a data file with these cuts. Please note that for large scale problems these cuts will not be enough and you will need to use stronger cuts such as the ones in that link.

Best regards,
Filipe

--
Filipe Brandão
am...@googlegroups.com

On Fri, Aug 3, 2018 at 3:51 PM UTC, Ampl Modeling Language <am...@googlegroups.com> wrote:

I am trying to implement a subtour constraint using Miller-tucker-Zemlin(MTZ) constraint but it seems this reference https://groups.google.com/forum/#!searchin/ampl/subtour%7Csort:date/ampl/FVQ-iZIhUHg/ZT2rPNP4BAAJ which I went to this https://groups.google.com/forum/#!msg/ampl/mVsFg4mAI1c/ZdfRHHRijfUJ . Is there a way to implement a constraint without the run file? Can it be implemented using just a constraint in model file? I am using MATLAB API for AMPL.

Thanks

[Vinh K]

Thank you very much. 

You received this message because you are subscribed to a topic in the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/ampl/sijPeX1_rE0/unsubscribe.
To unsubscribe from this group and all its topics, send an email to ampl+uns...@googlegroups.com.

[vinhk...@gmail.com]

Thank you very much Filipe Brandão

On Friday, August 3, 2018 at 11:50:56 AM UTC-4, vinh k wrote: