Topic
• 4 replies
• Latest Post - ‏2013-02-12T08:15:34Z by SystemAdmin
1883 Posts

# Pinned topic Decision variable in range of summation

‏2013-02-09T14:02:39Z |
Hello, I am new to to Cplex optimization Studio. I have to solve a mathematical programming problem to determine shift start times for a rostering problem.
The model is similar to the first model in the following paper: http://eprints.qut.edu.au/29823/1/c29823.pdf
With the exception that I only work with 24 periods (one day) instead of 168 periods, also I leave out constraint 6.

I already have the following code:

int N = ...;
int M = ...;

range periods=1..N;

int Dperiods = ...;

dvar int+ Speriods; //Number of crews on duty in period p
dvar int+ Hperiods; //Number of working periods of the shift that starts at the beginning of period p
dvar int Xperiods in 0..1;
dvar int Yperiods in 0..1;
dvar int Zperiods in 0..1;

minimize sum(p in periods)(abs(S[p]-D[p]));

subject to {
forall(p in periods)
forall(q in periods:q<=p)
D[p]-sum(t in periods:q<=t<=p) S[t]*Y[t] <= M*Z[p];

forall(p in periods)
forall(q in periods:q<=p)
Y[q] <= M*(1-Z[p]);

forall(p in periods)
1-sum(t in periods:(p+1)<=t<=(p+H[p]))Y[t] <= M*X[p];

forall(p in periods)
Y[p] <= M*(1-X[p]);

sum(t in periods) Y[t]==6;
};

The problem I have is that in one constraint a decision variable (H[p]) is included in the range of the summation.
Any idea how I can solve this?

Thanks,

Steven
Updated on 2013-02-12T08:15:34Z at 2013-02-12T08:15:34Z by SystemAdmin
1883 Posts

#### Re: Decision variable in range of summation

‏2013-02-11T13:57:29Z
The authors of the article couldn't care less about their model MIP formulation :)

For your specific problem, I recommend to introduce a new set of decision variables, which indicate if the shift is active at each period.

dvar boolean isOnperiodsperiods; // whether shift p (first) is active at period p (second)

the necessary constraints

forall(p1 in periods, p2 in periods) {
if (p1 > p2)
isOnp1p2 == 0;

if (p1 < p2)
N * isOnp1p2 <= N + p1 + H[p] - p2;

isOnp1p2 <= Yp1;
}

forall(p in periods)
1-sum(t in periods)isOn[t][p] <= M*X[p];
Regards,
Zahar
1883 Posts

#### Re: Decision variable in range of summation

‏2013-02-11T18:35:13Z
The authors of the article couldn't care less about their model MIP formulation :)

For your specific problem, I recommend to introduce a new set of decision variables, which indicate if the shift is active at each period.

dvar boolean isOnperiodsperiods; // whether shift p (first) is active at period p (second)

the necessary constraints

forall(p1 in periods, p2 in periods) {
if (p1 > p2)
isOnp1p2 == 0;

if (p1 < p2)
N * isOnp1p2 <= N + p1 + H[p] - p2;

isOnp1p2 <= Yp1;
}

forall(p in periods)
1-sum(t in periods)isOn[t][p] <= M*X[p];
Regards,
Zahar
I guess the H[p] in your new constraints must be Hp1?

When I do this, I get the following error "CPLEX Error 5002: Q in 'id1040' is not positive semi-definite".
1883 Posts

#### Re: Decision variable in range of summation

‏2013-02-11T21:53:24Z
I guess the H[p] in your new constraints must be Hp1?

When I do this, I get the following error "CPLEX Error 5002: Q in 'id1040' is not positive semi-definite".
Also, I thought of something that is impossible with the current formulation.

Suppose that there are 4 hour shifts and I want that it is possible for the model to find a schedule with a shift starting at the beginning of period 24 and ending at the end of period 3.

Any tips on how to implement this?
1883 Posts

#### Re: Decision variable in range of summation

‏2013-02-12T08:15:34Z
Also, I thought of something that is impossible with the current formulation.

Suppose that there are 4 hour shifts and I want that it is possible for the model to find a schedule with a shift starting at the beginning of period 24 and ending at the end of period 3.

Any tips on how to implement this?
Regarding the error you have, there is another non-linear constraint

forall(p in periods)
forall(q in periods:q<=p)
D[p]-sum(t in periods:q<=t<=p) S[t]*Y[t] <= M*Z[p];

If you picked that paper just because you needed an example scheduling problem MIP formulation then it was an unfortunate pick. You may consider using IBM iLog CP optimizer, which is designed for scheduling problems. Take a look at the following link