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*(1Z[p]);
forall(p in periods)
1sum(t in periods:(p+1)<=t<=(p+H[p]))Y[t] <= M*X[p];
forall(p in periods)
Y[p] <= M*(1X[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
Topic

Re: Decision variable in range of summation
20130211T13:57:29ZThis is the accepted answer. This is the accepted answer.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;
}
and your problematic constraint reads
forall(p in periods)
1sum(t in periods)isOn[t][p] <= M*X[p];
Regards,
Zahar 
Re: Decision variable in range of summation
20130211T18:35:13ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20130211T13: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;
}
and your problematic constraint reads
forall(p in periods)
1sum(t in periods)isOn[t][p] <= M*X[p];
Regards,
Zahar
When I do this, I get the following error "CPLEX Error 5002: Q in 'id1040' is not positive semidefinite". 
Re: Decision variable in range of summation
20130211T21:53:24ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20130211T18:35:13Z
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 semidefinite".
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? 
Re: Decision variable in range of summation
20130212T08:15:34ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20130211T21:53:24Z
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?
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
http://www.google.co.il/url?sa=t&rct=j&q=OPL+CP&source=web&cd=11&cad=rja&ved=0CDIQFjAAOAo&url=http%3A%2F%2Fchawalit.siit.tu.ac.th%2Flib%2Fexe%2Ffetch.php%3Fmedia%3Dmeeting%3Amodeling_with_ibm_ilog_cp_optimizer.pdf&ei=uPMZUfjWJsf5sgbmpoHADQ&usg=AFQjCNE8qbgfj6cHNPq1Vv9TrrNEEtchQ
http://www.ibm.com/developerworks/forums/forum.jspa?forumID=2067&start=15
But it is possible to solve the problem through Cplex optimizer as well, just need to redesign the formulation.
Regarding your question on circular intervals, one approach is to extend you overall time period to the previous day and to add a constraint that all shifts starting yesterday have a shift starting today at the same time. With CP it will be easy.
Regards,
Zahar