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

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
  • SystemAdmin
    SystemAdmin
    1883 Posts
    ACCEPTED ANSWER

    Re: Decision variable in range of summation

    ‏2013-02-11T13:57:29Z  in response to SystemAdmin
    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)
    1-sum(t in periods)isOn[t][p] <= M*X[p];
    Regards,
    Zahar
    • SystemAdmin
      SystemAdmin
      1883 Posts
      ACCEPTED ANSWER

      Re: Decision variable in range of summation

      ‏2013-02-11T18:35:13Z  in response to SystemAdmin
      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".
      • SystemAdmin
        SystemAdmin
        1883 Posts
        ACCEPTED ANSWER

        Re: Decision variable in range of summation

        ‏2013-02-11T21:53:24Z  in response to SystemAdmin
        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?
        • SystemAdmin
          SystemAdmin
          1883 Posts
          ACCEPTED ANSWER

          Re: Decision variable in range of summation

          ‏2013-02-12T08:15:34Z  in response to SystemAdmin
          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

          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=AFQjCNE8qbgfj6cHN-Pq1Vv9TrrNEEtchQ

          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