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
This topic has been locked.
4 replies
Latest Post
 20130212T08:15:34Z by SystemAdmin
ACCEPTED ANSWER
Pinned topic Decision variable in range of summation
20130209T14:02:39Z

Answered question
This question has been answered.
Unanswered question
This question has not been answered yet.
Updated on 20130212T08:15:34Z at 20130212T08:15:34Z by SystemAdmin

ACCEPTED ANSWER
Re: Decision variable in range of summation
20130211T13:57:29Z in response to SystemAdminThe 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
ACCEPTED ANSWER
Re: Decision variable in range of summation
20130211T18:35:13Z in response to SystemAdminI 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".
ACCEPTED ANSWER
Re: Decision variable in range of summation
20130211T21:53:24Z in response to SystemAdminAlso, 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?
ACCEPTED ANSWER
Re: Decision variable in range of summation
20130212T08:15:34Z in response to SystemAdminRegarding the error you have, there is another nonlinear 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
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


