Originally posted by: Mohamed Awad

Dears,

I would like to ask on how to model campaigns using CPLEX. In the attached case, I have two managers (John & Mark) who act as managers for building different categories of houses. In the attached code*, the transition time is zero if the same manager supervises the same category of houses. I would like to send each manager who finishes 2 houses of the same category to vacation (let's say 20 time units). Shall I use typeOfNext?. If so, how can I include it in the model.

Best regards,

Mohamed 

Originally posted by: PhilippeLaborie

Here is for instance an idea using state functions. I give a simplified example with a single manager (so all intervals are present and require the manager). The idea is to associate with each operation for house building (denoted operation[h]) an additional interval variable (denoted campaign[h]) that will start at the same date as operation[h] but will last until the end of the campaign for building a series of houses of the same type as the one of operation[h]. Intervals campaign[h] of a given campaign will all end at the same time (that is why they are end aligned in the  alwaysEqual constraint. One can count the number of houses in the campaign thanks to a cumul function, with a contribution pulse(campaign[h],1), and for instance it is easy to say : no more than 2 houses per campaign (cumul <= 2) and that there is a certain setup time between 2 campaigns of the same type that corresponds to the manager vacations (with a transition matrix on the state function). Here is the corresponding simplified example in OPL:

using CP;

int n  = 200; // Number of houses
int m  = 5;   // Number of types of houses
int D  = 25;  // Duration of house
int DS = 20;  // Setup time between 2 houses of different type
int DV = 10;  // Duration of vacations after k houses of the same type
int k  = 2;   // Maximal number of houses of the same type without vacation

int T[h in 1..n] = ...; // Type of house 

tuple triple { int t1; int t2; int d; }
{triple} M = { <t1,t2,DS> | t1,t2 in 0..m-1 : t1!=t2 };
{triple} MV = M union { <t1,t1,DV> | t1 in 0..m-1 };

dvar interval operation[h in 1..n] size D;
dvar sequence manager in all(h in 1..n) operation[h] types all(h in 1..n) T[h];

dvar interval campaign[h in 1..n] size D..10000;
stateFunction type with MV;
cumulFunction campsize = sum(h in 1..n) pulse(campaign[h],1);

minimize max(h in 1..n) endOf(operation[h]);
subject to {
  noOverlap(manager, M);
  forall(h in 1..n) {
    startAtStart(operation[h], campaign[h]);
    alwaysEqual(type, campaign[h], T[h], 0, 1); // Not start aligned, end aligned
  }
  campsize <= k;
}

Originally posted by: Mohamed Awad

Dear Phillipe,

Thank you for your kind reply and sorry for my late response as I was trying to adjust your model on a different case. In my case, I have two managers and there is a transition time based on the house category and who is the manager (i.e. the transition time in the case of the same house category and the same manager is zero). In addition, if any manager finishes 4 houses, he takes 20 days of vacation. I am attaching the code i am working on for which, I have the following questions/problems:

- In your solution, the size of every house is the same. In my case, the size is not constant so, I couldn't give a size for dvar interval campaign as you did. How can I solve this problem.

- The no of campaigns is considered for the houses in parallel not to the ones in series. How can I specify it to consider the sum of the houses of the same category that are in series.

- When I changed:

{triplet} transitionCategory = {<i,j, ((item(manCat,i).cat)==(item(manCat,j).cat)?0:10)> | i in manCatTypes,j in manCatTypes};

to:

{triplet} transitionCategory = {<i,j, ((item(manCat,i).cat)==(item(manCat,j).cat)?0:5)> | i in manCatTypes,j in manCatTypes};

I had the following error:

Exception in presolve: Transition matrix for state function does not satisfy the triangle inequality (path 1->0->1). What does the error mean.

The code is sent below and I attached the .dat file. I really appreciate your kind support.

Best regards,

Mohamed
 

The code:

// --------------------------------------------------------------------------
// Licensed Materials - Property of IBM
//
// 5725-A06 5725-A29 5724-Y48 5724-Y49 5724-Y54 5724-Y55
// Copyright IBM Corporation 1998, 2013. All Rights Reserved.
//
// Note to U.S. Government Users Restricted Rights:
// Use, duplication or disclosure restricted by GSA ADP Schedule
// Contract with IBM Corp.
// --------------------------------------------------------------------------

using CP;

int NbHouses = ...; 
range Houses = 1..NbHouses; 
{string} TaskNames   = ...;
{string} ManNames = ...;  

int    Duration [t in TaskNames] = ...;
string Worker   [t in TaskNames] = ...;

int k=4; // when this number was 2, it doesn't work as it counted the two batches in parallel not the ones in series
// I made K two times of max campaign number and it worked in case of one type "1". 

int n  = 9;
int Dcamp=20;
int T[h in 1..n] = ...; // Type of house 
//--------------------------------------------------------

//--------------------------------------------------------


tuple Precedence {
   string pre;
   string post;
};

{Precedence} Precedences = ...; 

int   ReleaseDate[Houses] = ...; 
int   DueDate    [Houses] = ...; 
float Weight     [Houses] = ...; 

dvar interval houses[h in Houses] in ReleaseDate[h]..(maxint div 2)-1;

dvar interval itvs [h in Houses][t in TaskNames] size Duration[t];

dvar interval campaign [h in Houses] size 31..10000; // it requires a size. I gave it the size of house as it is constact..What will I do if it is variable??!!

dvar interval wtasks [h in Houses][m in ManNames] optional;

dvar sequence Mangs [m in ManNames] in all (h in Houses) wtasks[h][m] types all(h in 1..n) T[h];

cumulFunction campsize = sum(h in 1..n) pulse(campaign[h],1);
        
tuple triplet {int loc1; int loc2; int value; };

tuple ManCategory {string mang; int cat;};
{ManCategory} manCat={<m,c> | m in ManNames, c in 1..n};
{int} manCatTypes = {ord (manCat,mc)| mc in manCat};

{triplet} transitionMang = {<i,j, ((item(manCat,i).mang)==(item(manCat,j).mang)?0:10)> | i in manCatTypes,j in manCatTypes};
{triplet} transitionCategory = {<i,j, ((item(manCat,i).cat)==(item(manCat,j).cat)?0:5)> | i in manCatTypes,j in manCatTypes};
{triplet} transitionTimes = {<i,j, (tm.value + tc.value)> | i in manCatTypes,j in manCatTypes ,tm in transitionMang, 
                                                        tc in transitionCategory : i==tm.loc1 && i==tc.loc1 && j==tm.loc2 && j==tc.loc2 && i!=j};

{triplet} transitionCamp = {<i,j,Dcamp> | i in manCatTypes,j in manCatTypes : i==j} union transitionTimes;


stateFunction type4 with transitionCamp;

execute {
                cp.param.FailLimit = 20000;
}

minimize max(h in Houses,t in TaskNames ) endOf(itvs[h][t]);

subject to {

forall(h in Houses)
    alternative(houses[h], all(m in ManNames) wtasks[h][m]);

forall (h in Houses)
  forall (p in Precedences)
    endBeforeStart(itvs[h][p.pre] , itvs[h][p.post]);

forall (h in Houses)
  span(houses[h], all (t in TaskNames) itvs[h][t]);

        forall (m in ManNames)
                noOverlap (Mangs[m], transitionTimes);
        
        
         forall(h in 1..n) {
    startAtStart(houses[h], campaign[h]);
    alwaysEqual(type4, campaign[h], T[h], 0, 1);
  }
  
  campsize <= k;
}  

Originally posted by: PhilippeLaborie

I have the following questions/problems:

- In your solution, the size of every house is the same. In my case, the size is not constant so, I couldn't give a size for dvar interval campaign as you did. How can I solve this problem.

I think that in this case, the minimal length (duration) of a campaign for a task h should be the duration of the task h itself.

- The no of campaigns is considered for the houses in parallel not to the ones in series. How can I specify it to consider the sum of the houses of the same category that are in series.

I do not understand. Could you give a small example with actual values for start/end times, showing what is and what is not a feasible solution in this case?

- When I changed: I had the following error: Exception in presolve: Transition matrix for state function does not satisfy the triangle inequality (path 1->0->1). What does the error mean

A constraint/limitation on the transition matrix for state functions is that they must satisfy the triangle inequality. The error simply says that your matrix does not satisfy the triangle inequality because the transition time from 1 to 0 plus the transition time from 0 to 1 is smaller than the direct transition time from 1 to 1.

Originally posted by: Mohamed Awad

Dear Philippe,

Thank you for your kind reply. I am attaching a screenshot to illustrate the second question. Also, I would like to understand the relation between the types of the sequence variable (types all..) and the transition matrix in case of using noOverLap constraint. For example, what will happen if I don't specify types for the sequence variable "Mangs" while I still have a constraint on the transition time between the sequence variable. Is there a way to specify types based on string not by using integer values.  I am still referring to the code previously sent.

Thanks a million for your kind support.

Best regards,

Mohamed

Originally posted by: PhilippeLaborie

Ok, I understand your second question now. In the original code I sent, I assumed there was only one "manager" resource, so there was only one set of "campaign" intervals.

But when you have several managers, you of course will need to have one (optional) interval per pair house h / manager m, something like:

dvar interval wcampaign [h in Houses][m in ManNames] optional size ...;

With same presence status as the tasks:

presenceOf(wcampaign[h][m]) == presenceOf(wtasks[h][m]);

And you will need one state function per manager resource.

Concerning the other questions:

> I would like to understand the relation between the types of the sequence variable (types all..) and the transition matrix in case of using noOverLap constraint. For example, what will happen if I don't specify types for the sequence variable "Mangs" while I still have a constraint on the transition time between the sequence variable.

If you do not specify any type array when creating the sequence variable, the types are supposed to be contiguous starting from 0, so [0,1,...,n-1] if you have n intervals in the sequence. In general it is always better not to rely on this default value and explicitly define the types (the code is then less ambiguous)

> Is there a way to specify types based on string not by using integer values

No. Types have to be integers. If you have strings as input, you need to index them as integers.