need some clarification in ampl error

[Atri Mahapatra]

Dear Bob,

I was working on the  dynamic subtour elimination constraint generation.
Previously, in my formulation, I used subtour elimination constraints that were computed. I am trying to solve the problem with dynamic generation of  subtour elimination constraints.I am following your suggestion.  I am getting an error which I am unable to understand:

**************************************************************************************************************************
sw: ampl

ampl: include "C:\files\inti.run";

C:\files\inti.run, line 19 (offset 431):
 left-hand side has dimen 1 but
 right-hand side has dimen 2

context:  ((i,j) in E and (x[i,j,m] + y[i,j,m])   = 1 or (j,i) in E and ( x[j,i,m] + y[j,i,m])  =  >>> 1)}; <<<

****************************************************************************************************************************

I have attached the model files - formulation.mod ( where sub tour constraints are computed) and new.mod, new.run ( where constraints are generated). The data file is 2.dat.

I use the following subtour constraint:

subject to Cutsubtours {m in trip, k in S: card(POW[k]) >= 2 and card(POW[k]) <= N/2}:
    sum {(i,j) in E: (i in POW[k]) and (j not in POW[k])} (x[i,j,m] + y[i,j,m])
    + sum {(j,i) in E: (i not in POW[k]) and (j in POW[k])} (x[i,j,m] + y[i,j,m] )>= 2];

This constraint is giving me the desired result and I would like  to use the same for the  sub tour constraint generation.

It would be of great help if you can  suggest me  where I am doing wrong  in my current formulation ( in script file or mod file) and also explain me the following in the TSP.run file you have send me earlier  ?

**********************************************************************************************************************************

let NEWSUB := {};
   let EXTEND := {member(ceil(Uniform(0,card(NODES))),NODES)};

   repeat {
      let NEWSUB := NEWSUB union EXTEND;
      let EXTEND := {j in NODES diff NEWSUB: exists {i in NEWSUB}
         ((i,j) in PAIRS and X[i,j] = 1 or (j,i) in PAIRS and X[j,i] = 1)};
   } until card(EXTEND) = 0;
************************************************************************************************************************************

I look forward to hearing from you.

Thanks,

Atri

[Robert Fourer]

The problem here is that EXTEND is defined as a one-dimensional set, but you are using the "let" command to assign a two-dimensional set to it.  Specifically if EXTEND is initialized as a set of vertices, then  you can't write

 

   let EXTEND := {m in trip, j in V diff NEWSUB: ...

 

which makes EXTEND into a set of (m,j) pairs where m is a trip and j a vertex.

 

Bob Fourer

am...@googlegroups.com

 

 

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

On Behalf Of Atri Mahapatra
Sent: Thursday, August 1, 2013 6:10 PM
To: Robert Fourer; am...@googlegroups.com
Subject: [AMPL 7315] need some clarification in ampl error

[KristianU]

Dear Bob and others,

I am facing a similar problem, where my binary decision variable is in 4 dimensions, similar to here where X has 3 dimensions. 

How can "let EXTEND" be formulated in this example, so the dimension m (trips) is defined?

Thank you,

/Kristian 

[AMPL Google Group]

You can't define one dimensional set and assign two dimensional values. If each member of your set is 4-dimensional, then you need to declare the set as follows:
set Extend dimen 4;
set A;
set B;
set C;
set D;
data;
set Extend = (1,2,3,4), (4,5,6,7),(8,9,10,11);
set A = 1,2;
set B = 3,4;
set C = 5,6;
set D = 7,8;

then you can have four dimensional member in the set as follows:
data;
set Extend = (1,2,3,4), (4,5,6,7),(8,9,10,11);

Alternatively, if you want to use let statement and create the member of Extend from the one dimensional set A, B, C and D, then you can use following let command

let {i in A, j in B, k in C, l in D} Extend := Extend union {(i,j,k,l)};


--
Dr. Paras Tiwari
am...@googlegroups.com

{#HS:680531781-25283#}

--
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.

[KristianU]

Hi Paras,

Thank you very much for the answer. I may have formulated my question a bit confusing - at least I am not quite sure how to go on with your answer.

I will try to ask in a different way.

I want to use following code in my run file in order to eliminate subtours dynamically.

______________________

repeat {

   solve;

   let NEWSUB := {};

   let EXTEND := {member(ceil(Uniform(0,card(P))),P)};

   repeat {

      let NEWSUB := NEWSUB union EXTEND;

      let EXTEND := {j in P diff NEWSUB: exists {p in NEWSUB}

         ((p,j) in E and H[p,j,v,t] = 1 or (j,p) in E and H[j,p,v,t] = 1)};

   } until card(EXTEND) = 0;

   if card(NEWSUB) < card(P) then {

      let nSubtours := nSubtours + 1;

      let SUB[nSubtours] := NEWSUB;

      display SUB;

   } else break;

};

_____________________________

However, this can not run as my decision variable H has four dimensions [p,j,v,t] and v og t is not defined in the above.

I tried defining them as followed:

  repeat {

      let NEWSUB := NEWSUB union EXTEND;

      let EXTEND := {j in P diff NEWSUB: exists {p in NEWSUB, v in 1..V, t in 1..T}

         ((p,j) in E and H[p,j,v,t] = 1 or (j,p) in E and H[j,p,v,t] = 1)};

   } until card(EXTEND) = 0;

Which made the model run, but I am not sure if it is correct, as it did not eliminate the subtours..

/Kristian

[AMPL Google Group]

Rewrite your statement as follows:

let EXTEND := {j in P diff NEWSUB, v in 1..V, t in 1..T: exists {p in NEWSUB}

((p,j) in E and H[p,j,v,t] = 1 or (j,p) in E and H[j,p,v,t] = 1)};

So, move v and t index before colon. Let me know if this removes subtour.

Your problem seems different than the other problems discussed in subtour elimination. As mentioned at http://www.math.uwaterloo.ca/tsp/methods/opt/subtour.htm, the subtour constraint ... >=2 indicates that for each city i we must select two of the roads that start or end at i (since we need to arrive at city i and then leave again). You have a binary variable 'H' of four dimension, so I don't think you have formulated your problem as a graph problem. If the above change doesn't remove subtour, please let us know. I need to look into how can we extend the subtour elimination of the graph problem to something like your problem.

Thanks,
Paras

--
Dr. Paras Tiwari
am...@googlegroups.com

{#HS:680531781-25283#}

[KristianU]

This: 

let EXTEND := {j in P diff NEWSUB, v in 1..V, t in 1..T: exists {p in NEWSUB}

gives me same error message as Atri in the first post of this thread:

     left-hand side has dimen 1 but

     right-hand side has dimen 3

I can only get it to run with this input:

let EXTEND := {j in P diff NEWSUB: exists {p in NEWSUB, v in 1..V, t in 1..T}

But this still creates subtours.

My binary variable 'H' first two dimensions represents the tour from station p to station j. The last two are which vehicle v in which time period t, as my model is quite similar to a Periodic Vehicle Routing Problem. I see from your explanation, that this constraint formulation might be problematic for my model, as I dont necessarily want my vehicles to visit every station in every time period, which they are forced to do if I understand it correctly. 

I would love to hear your inputs on an alternativ formulation or other thoughts. 

Thanks,

Kristian

[KristianU]

Hi again Paras,

I am thinking that my subtour constraint in the model file should contain something like.

"the subtour constraint ... >=2 * StationVisited[p, v, t];"

In order for the constraint to only bind on the stations used by the vehicles in a given time period. However, I am still unable to get the dynamic subtour elimination to work.

Best,

Kristian

[AMPL Google Group]

It appears that you need to focus first on defining the subtour elimination constraints correctly. In your formulations it appears that you have one subtour elimination constraint for every subset of the stations. But each vehicle may separately have subtours in the solution, so you may need to have subtour elimination constraints for each combination of a vehicle and a subset of stations. The presence of time periods in your application will further complicate the formulation; to get the correct formulation of your subtour elimination constraints, you will need to closely study the particular variant of the vehicle routing problem that you are trying to solve.

After you have what you believe is a correct formulation, you can proceed to write the script to dynamically generate the subtour elimination constraints. Then if the solution found at the end of your script still has subtours, you can study the subtours to understand why they were not eliminated by the constraints that you defined. It may also help to use AMPL's "expand" command to look at the subtour elimination constraints that were actually generated.

--
Robert Fourer
am...@googlegroups.com

{#HS:680531781-25283#}

On Wed, Oct 10, 2018 at 4:54 PM UTC, Ampl Modeling Language <am...@googlegroups.com> wrote:

Hi again Paras,

I am thinking that my subtour constraint in the model file should contain something like.

"the subtour constraint ... >=2 * StationVisited[p, v, t];"

In order for the constraint to only bind on the stations used by the vehicles in a given time period. However, I am still unable to get the dynamic subtour elimination to work.

Best,
Kristian

tirsdag den 9. oktober 2018 kl. 03.50.30 UTC+2 skrev AMPL Google Group:

On Tue, Oct 9, 2018 at 2:47 AM UTC, Ampl Modeling Language <am...@googlegroups.com> wrote:

This:

let EXTEND := {j in P diff NEWSUB, v in 1..V, t in 1..T: exists {p in NEWSUB}

gives me same error message as Atri in the first post of this thread:

left-hand side has dimen 1 but

right-hand side has dimen 3

I can only get it to run with this input:

let EXTEND := {j in P diff NEWSUB: exists {p in NEWSUB, v in 1..V, t in 1..T}

But this still creates subtours.

My binary variable 'H' first two dimensions represents the tour from station p to station j. The last two are which vehicle v in which time period t, as my model is quite similar to a Periodic Vehicle Routing Problem. I see from your explanation, that this constraint formulation might be problematic for my model, as I dont necessarily want my vehicles to visit every station in every time period, which they are forced to do if I understand it correctly.

I would love to hear your inputs on an alternativ formulation or other thoughts.

Thanks,

Kristian


tirsdag den 9. oktober 2018 kl. 03.50.30 UTC+2 skrev AMPL Google Group:

On Tue, Oct 9, 2018 at 1:50 AM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

Rewrite your statement as follows:

let EXTEND := {j in P diff NEWSUB, v in 1..V, t in 1..T: exists {p in NEWSUB}
((p,j) in E and H[p,j,v,t] = 1 or (j,p) in E and H[j,p,v,t] = 1)};

So, move v and t index before colon. Let me know if this removes subtour.

Your problem seems different than the other problems discussed in subtour elimination. As mentioned at http://www.math.uwaterloo.ca/tsp/methods/opt/subtour.htm, the subtour constraint ... >=2 indicates that for each city i we must select two of the roads that start or end at i (since we need to arrive at city i and then leave again). You have a binary variable 'H' of four dimension, so I don't think you have formulated your problem as a graph problem. If the above change doesn't remove subtour, please let us know. I need to look into how can we extend the subtour elimination of the graph problem to something like your problem.

Thanks,
Paras

--
Dr. Paras Tiwari
am...@googlegroups.com

[KristianU]

Hi Bob,

I tried to formulate the subtour constraints like this:

param nSubtours >= 0 integer;

set SUB {1..nSubtours} within P;

subject to Subtour_Elimination {k in 1..nSubtours, m in SUB[k], v in 1..V, t in 1..T, f in 1..F}:

sum {p in SUB[k], j in P diff SUB[k]} 

      if (p,j) in PAIRS then H[p,j,v,t] else H[j,p,v,t]  >=2 * StationUsed[m,f,v,t];  #f is indexing different commodities

This way I think I am formulating the subtour elimination constraint for every vehicle and time-period. Does this make sense to you?

Thanks,

Kristian

[AMPL Google Group]

Hi Kristian,

For each subset SUB[k], the Subtour_Elimination constraint does appear to generate the relevant subtour elimination constraints for all vehicles in all periods. That should eliminate of the subtours that you see, as well as many other possible subtours.

--
Robert Fourer
am...@googlegroups.com

{#HS:680531781-25283#}

On Thu, Oct 11, 2018 at 2:10 PM UTC, Ampl Modeling Language <am...@googlegroups.com> wrote:

Hi Bob,

I tried to formulate the subtour constraints like this:


param nSubtours >= 0 integer;
set SUB {1..nSubtours} within P;

subject to Subtour_Elimination {k in 1..nSubtours, m in SUB[k], v in 1..V, t in 1..T, f in 1..F}:
sum {p in SUB[k], j in P diff SUB[k]}
if (p,j) in PAIRS then H[p,j,v,t] else H[j,p,v,t] >=2 * StationUsed[m,f,v,t]; #f is indexing different commodities

This way I think I am formulating the subtour elimination constraint for every vehicle and time-period. Does this make sense to you?

Thanks,
Kristian

torsdag den 11. oktober 2018 kl. 05.07.01 UTC+2 skrev AMPL Google Group:

On Thu, Oct 11, 2018 at 3:06 AM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

It appears that you need to focus first on defining the subtour elimination constraints correctly. In your formulations it appears that you have one subtour elimination constraint for every subset of the stations. But each vehicle may separately have subtours in the solution, so you may need to have subtour elimination constraints for each combination of a vehicle and a subset of stations. The presence of time periods in your application will further complicate the formulation; to get the correct formulation of your subtour elimination constraints, you will need to closely study the particular variant of the vehicle routing problem that you are trying to solve.

After you have what you believe is a correct formulation, you can proceed to write the script to dynamically generate the subtour elimination constraints. Then if the solution found at the end of your script still has subtours, you can study the subtours to understand why they were not eliminated by the constraints that you defined. It may also help to use AMPL's "expand" command to look at the subtour elimination constraints that were actually generated.

--
Robert Fourer
am...@googlegroups.com

[KristianU]

Hi,

I should think so too, however, I still get routes with subtours. I worry that SUB is not updated correct, but I can not figure out where the mistake is.

Run file:

set NEWSUB;

set EXTEND;

let nSubtours := 0;

option cplex_options ' mipdisplay 2 nodefile 3';

repeat {

   solve;

   let NEWSUB := {};

   let EXTEND := {member(ceil(Uniform(0,card(P))),P)};

   

   repeat {

      let NEWSUB := NEWSUB union EXTEND;

      let EXTEND := {j in P diff NEWSUB: exists {p in NEWSUB, v in V, t in T}

         ((p,j) in PAIRS and H[p,j,v,t] = 1 or (j,p) in PAIRS and H[j,p,v,t] = 1)};

   } until card(EXTEND) = 0;

   if card(NEWSUB) < card(P) then {

      let nSubtours := nSubtours + 1;

      let SUB[nSubtours] := NEWSUB;

      display SUB;

   } else break;

};

Do you see anything in the above, that is incorrect?

Thank you.

/Kristian

[AMPL Google Group]

Since you are the one who best knows the details of the vehicle routing problem that you are trying to solve, you will need to take responsibility for debugging your solution approach. As a start, you could add "display H;" after "solve;" and you could add "display EXTEND, NEWSUB;" after the two "let EXTEND := . . ." statements, so that you can see exactly how your procedure is working. Then look at the output for each pass through the repeat loop, and ask yourself whether NEWSUB correctly represents one of the subtours in the solution given by H. If NEWSUB does not represent one of the subtours in the solution, then you know there has been an error in computing it.

In particular, at the last pass through the loop, if NEWSUB equals P but there are still subtours in the solution, then NEWSUB is not being computed correctly and you can investigate further to determine the error in your logic.

--
Robert Fourer
am...@googlegroups.com

{#HS:680531781-25283#}

[KristianU]

This was good advice. After debugging I became aware, that this approach was not suitable for my problem.

I have a model with multiple vehicles and multiple time periods. A node can only be visited by one vehicle one time within a time period. The nodes does not have to be visited in every time period, which is a major difference from the TSP formulation, where all nodes are in the cycle. All of this made my problem a bit more complex.

I tried with the following approach:

The constraint in the model file is more or less the same as from your TSP example. I just added the binary variable "StationUsed".

set P ordered;  # Number of nodes

set PAIRS := {p in P, j in P: ord(p) != ord(j)};

param nSubtours >= 0 integer;

param iter >= 0 integer;

set SUB {1..nSubtours} within P;

subject to Subtour_Elimination {s in 1..nSubtours, k in SUB[s], f in F, v in V, t in T}:

sum {p in SUB[s], j in P diff SUB[s]} 

      if (p,j) in PAIRS then H[p,j,v,t] else H[j,p,v,t]  >= 2 * StationUsed[k,f,v,t];

My run file looks like this:

let nSubtours := 0;

let iter := 0;

param num_components {V, T};

set P_TEMP;

set PAIRS_SOL {1..iter, V, T} within PAIRS;

param component_id {P_TEMP};

set COMPONENT_IDS;

set COMPONENT {COMPONENT_IDS};

param cp;

param cj;

# loop until each day and each vehicles support graph is connected

repeat {

let iter := iter + 1;

   

solve;

# Find connected components for each day

for {v in V, t in T} {

let P_TEMP := {p in P: exists {f in F} StationUsed[p,f,v,t] > 0.5};

let PAIRS_SOL[iter, v, t] := {(p,j) in PAIRS: H[p, j, v, t] > 0.5};

# Set each node to its own component

let COMPONENT_IDS := P_TEMP;

let num_components[v, t] := card(P_TEMP);

for {p in P_TEMP} {

let component_id[p] := p;

let COMPONENT[p] := {p};

};

# If p and j are in different components, merge the two component

for {(p,j) in PAIRS_SOL[iter, v, t]} {

let cp := component_id[p];

let cj := component_id[j];

if cp != cj then {

# update smaller component

if card(COMPONENT[cp]) < card(COMPONENT[cj]) then {

for {k in COMPONENT[cp]} let component_id[k] := cj;

let COMPONENT[cj] := COMPONENT[cj] union COMPONENT[cp];

let COMPONENT_IDS := COMPONENT_IDS diff {cp};

} else {

for {k in COMPONENT[cj]} let component_id[k] := cp;

let COMPONENT[cp] := COMPONENT[cp] union COMPONENT[cj];

let COMPONENT_IDS := COMPONENT_IDS diff {cj};

};

};

};

let num_components[v, t] := card(COMPONENT_IDS);

display num_components[v, t];

# create subtour from each component not containing depot node

for {k in COMPONENT_IDS: COMPONENT[K] diff {p}} { . #***

let nSubtours := nSubtours + 1;

let SUB[nSubtours] := COMPONENT[k];

display SUB[nSubtours];

};

};

display num_components;

} until ({v in V, t in T} num_components[v,t] := 1); #***

I have debugged this thoroughly and it seems to do the job, however I encountered two syntax errors (marked with ***), which I dont know how to fix. I would be very glad if some of you could help.

1)

syntax error
context:  for {k in COMPONENT_IDS: COMPONENT[k] diff {1}  >>> } <<<  {

I want to create the subtours from each component not containing the depot, which is in node 1. Can I formulate this different?

2)

syntax error
context:  } until ({v in V, t in T}  >>> num_components[ <<< v,t] := 1);

How do I make the repeat loop run until all num_components[v,t] = 1?

Any thoughts on these two errors would be much appreciated. Thank you.

Best regards,

Kristian

[AMPL Google Group]

(1) To skip COMPONENT[k] if it contains 1, you can write:

for {k in COMPONENT_IDS: 1 not in COMPONENT[k]} { . . .

(2) You need to use the "forall" operator:

. . . until (forall {v in V, t in T} num_components[v,t] = 1);

--
Robert Fourer
am...@googlegroups.com

{#HS:680531781-25283#}

[KristianU]

Thank you very much. Just, what I was looking for.

Unfortunately, I have another error. I get a lot of "invalid subscript discarded", when running the model:

Error at _cmdno 43 executing "if" command
(file amplin, line 229, offset 5372):
error processing set COMPONENT:
	invalid subscript COMPONENT[4] discarded.

Error at _cmdno 63 executing "for" command
(file amplin, line 245, offset 5951):
error processing set COMPONENT:
	invalid subscript COMPONENT[3] discarded.

(...)

Bailing out after 10 warnings.

I think the script is doing what I am looking for, but it stops, when it has discarded 10 invalid subscripts. 

When trying to debug I tested the second for loop.

for {p in P_TEMP} {
				
        let component_id[p] := p;
	let COMPONENT[p] := {p};		
	display component_id[p];
	display COMPONENT[p]; 	
};
	

This is displaying correct, but not before a few errors with "invalid subscript discarded". It seems that p runs through some p not in P_TEMP. For example when P_TEMP is a set consisting of nodes  "1 3 4 5", then I get a invalid subscript for component_id[2] and COMPONENT[2]. My guess is that something similar happens again later on in the IF-ELSE statement.

How do I avoid this?

Best,

Kristian

[AMPL Google Group]

This kind of "invalid subscript" error occurs when a set or parameter is indexed over a set, like P_TEMP, that keeps changing, with members being deleted as well as added.

Usually there is a straightforward fix. Try defining component_id and COMPONENT to be indexed over P rather than P_TEMP. But continue to use for {p in P_TEMP} as your looping statement.

--
Robert Fourer
am...@googlegroups.com

{#HS:680531781-25283#}

[KristianU]

Thank you. This worked and I finally made it eliminate the subtours dynamically. However, it didn't quite have the speed improvement as I had hoped for.. :-(

/Kristian