order of periods

[brigitte...@gmail.com]

Hello,

I am working on an arc routing problem with periods and different lengths for the arcs. The startdepot is 0 and the enddepot is 5. The problem is that the solution always jumps between the periods, so that the periods are not choosen in order:

param n;                                               
set Vert := 0..n;                                       
set Arc := {i in Vert, j in Vert : i <> j};   
param T;
set Period := 1..T;
param l{(i,j) in Arc};  -> length for the arc (i,j)
param c{(i,j) in Arc};
param M;

var x{(i,j) in Arc, t in Period} binary;     -> equal to 1 if arc (i,j) is planned in period to for the tour
var gamma{(i,j) in Arc} binary;     -> equal to 1 if arc (i,j) is planned in the tour, doesn`t matter which period

maximize costs: sum{(i,j) in Arc, t in Period} x[i,j,t] * c[i,j];   

subject to start: sum{(0,j) in Arc} x[0,j,1] = 1;    -> each tour starts in the depot 0
subject to end: sum{(i,5) in Arc, t in 2..T} x[i,5,t] = 1;    -> each tour has to end in the depot 5
subject to period{t in Period}: sum{(i,j) in Arc} x[i,j,t] <= 1;    -> each period can only be choosen one time; so one vehicle can not drive over two arc at the same time
subject to time: sum{(i,j) in Arc, t in Period} x[i,j,t] <= T;    -> the tour shouldn`t be longer than the maximal worktime
subject to Periodenlaenge{(i,j) in Arc}: sum{t in Period} x[i,j,t] <= gamma[i,j] * M;     -> if arc (i,j) is planned in the tour (doesn`t matter which time) then gamma gonna be one
subject to Periodenlaenge2{(i,j) in Arc}: sum{t in Period} x[i,j,t] = l[i,j] * gamma[i,j];   -> the length describeds how many periods need to be planned for this arc; but only if the arc is planned in the tour

This is the solution I get:
x [0,*,*] (tr)
:    1   2   3   4   5    :=
1    0   1   0   0   0
2    0   0   0   0   1
3    0   0   0   0   0
4    1   0   0   0   0
5    0   0   0   0   0
6    0   0   1   0   0
7    0   0   0   1   0
8    0   0   0   0   0
9    0   0   0   0   0
10   0   0   0   0   0

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

I choosed the length for the arc (2,4) two periods. So the program is planning with the correct length but it also should be planning the period after period and not jump between it. I tried to get connected periods with a flow conservation constraint:
subject to Flusserhaltung{(i,j) in Arc, t in 2..T}: sum{u in Vert: u <> j} x[j,u,t] +  x[i,j,t] <= x[i,j,t-1];

But then the whole model isn`t working because of the "end"-constraint.

Could anyone help me with it? I am working with this problem for a long time!

Thank you!

[AMPL Google Group]

I think you are saying that your solution has X[2,4,t] = 1 for t = 3 and t = 5, but you want to force it to = 1 for two consecutive values of t (like 3 and 4). Furthermore you have tried to add a constraint to enforce this condition:

subject to Flusserhaltung {(i,j) in Arc, t in 2..T}: sum {u in Vert: u <> j} x[j,u,t] + x[i,j,t] <= x[i,j,t-1];

But can you explain more specifically why "the whole model isn't working" when you add this constraint? If you are getting an error message, then what is the complete text of the message? If you are getting wrong solutions with this constraint, then can you give an example of what is wrong with them?

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

{#HS:564796378-5646#}

[brigitte...@gmail.com]

Yes that´s correct. I am not getting consecutive values of the periods.

If I am using the constraint "Flusserhaltung" then I am getting follow error message:

presolve, constraint end:
    all variables eliminated, but lower bound = 1 > 0

I don´t know how to change constraint end to solve the problem because the tour needs to end at the depot in any period.

[AMPL Google Group]

AMPL's presolve phase uses an analysis of the constraints to tighten the bounds on some of the variables. Sometimes presolve finds that a variable's lower bound equals its upper bound, in which case the variable can be fixed at that bound. When you see the message

presolve, constraint end:
all variables eliminated, but lower bound = 1 > 0

it means that all of the variables in constraint "end" have been fixed in this way, resulting in a constraint that can't be satisfied. In this case the constraint is

subject to end: sum {(i,5) in Arc, t in 2..T} x[i,5,t] = 1;

and the "lower bound = 1 > 0" suggests that presolve fixed all the variables x[i,5,t] to zero, resulting in an impossible constraint 0 = 1. To investigate the cause of this problem you might set "option presolve 0;" and then use your solver to look for an irreducible infeasible subset, as explained for example in https://groups.google.com/d/msg/ampl/o8aNfwpoBAc/D46d6cfICQAJ and https://groups.google.com/d/msg/ampl/KO8rV88e4Fo/autgtMVxAwAJ.

Also you should consider whether your "end" constraint is correct. It says that exactly one of all the variables x[i,5,t] equals 1, for all arcs (i,5) and all periods 2 through T.

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

{#HS:564796378-5646#}

On Wed, Apr 25, 2018 at 9:26 AM UTC, Ampl Modeling Language <am...@googlegroups.com> wrote:

Yes that´s correct. I am not getting consecutive values of the periods.

If I am using the constraint "Flusserhaltung" then I am getting follow error message:

presolve, constraint end:
all variables eliminated, but lower bound = 1 > 0

I don´t know how to change constraint end to solve the problem because the tour needs to end at the depot in any period.

Am Montag, 23. April 2018 16:01:24 UTC+2 schrieb AMPL Google Group:

On Mon, Apr 23, 2018 at 2:00 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

I think you are saying that your solution has X[2,4,t] = 1 for t = 3 and t = 5, but you want to force it to = 1 for two consecutive values of t (like 3 and 4). Furthermore you have tried to add a constraint to enforce this condition:

subject to Flusserhaltung {(i,j) in Arc, t in 2..T}: sum {u in Vert: u <> j} x[j,u,t] + x[i,j,t] <= x[i,j,t-1];

But can you explain more specifically why "the whole model isn't working" when you add this constraint? If you are getting an error message, then what is the complete text of the message? If you are getting wrong solutions with this constraint, then can you give an example of what is wrong with them?

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