Answers to: Constraint formulationhttp://www.or-exchange.com/questions/14207/constraint-formulation<p>Hello,</p>
<p>My problem consists to determine the exact period of patient treatment.
The duration of period is 30 minutes.</p>
<pre><code>Indices:
P patients
T periods
M doctor
Parameter:
dur[p] : the treatment duration of patient p
Decision Variables
Occup[m][t] {1: if a doctor is available at period t, 0:else}
Trait[p][t]:{1: If patient p is treated at period t, 0:else}
</code></pre>
<p>=> A patient is treated once on T periods.</p>
<p>I have this constraint:</p>
<p>At period t, if the sum of patient "p" treatment time with patients' treatment time to come before him does not exceed 30 minutes then
Trait[p][t]=1 else
Trait[p][t]=0</p>
<p>The formulation of constraint on CPLEX opl is</p>
<pre><code> forall(m in doctors, t in periods)
sum(p in 1..P)(dur[p]*Trait[p][t])<=30*Occup[m][t];
</code></pre>
<p>My problem when i add another constraint some patients will not treated at the exact period.</p>
<p>My question is: how can I force this constraint to determine the exact treatment period.</p>
<p>Best regards</p>enWed, 21 Sep 2016 06:58:02 -0400Comment by lolla on Walter's answerhttp://www.or-exchange.com/questions/14207/constraint-formulation#14216<p>I explain my problem in answers</p>lollaWed, 21 Sep 2016 06:58:02 -0400http://www.or-exchange.com/questions/14207/constraint-formulation#14216Answer by lollahttp://www.or-exchange.com/questions/14207/constraint-formulation/14215<p>Constraints :</p>
<pre><code> constraint 1: calculate variable doctor_move
forall (m in doctors,t in 2..T)
(Occup[m][t] - Occup[m][t-1])/2 <=doctor_move[m][t];
forall (m in doctors,t in 2..T)
1+(Occup[m][t] - Occup[m][t-1])/2>=doctor_move[m][t];
Constraint 2 :patients are treated according to order (FCFS)
forall(m in doctors, p in patients)
sum(t in periods)t*treat[p][t]<=sum(t in periods)t* treat[p+1][t];
Constraint 3 :patient p is treated at most once
forall(m in doctors, p in patients)
sum(t in periods)treat[p][t]==1;
Constraint 4 :identifying a patient treatment period
forall(m in doctors, t in 1..T)
sum(p in patients)(dur[p]*Treat[p][t])<=30*Occup[m][t];
constraint 5: Calculate the remaining number of patients in each period:
forall(m in doctors, t in periods)
nb_rest[m][t]==sum(p in patients,t1 in 1..t)appearance[p][t1]-sum(p in patients, t1 in 1..t)treat[p][t1];
Constraint 6: Doctor moves to service only if patients are available
forall (m in doctors, t in 1..T)
doctor_move[m][t]<=nb_rest[m][t];
</code></pre>
<p>For example:</p>
<p>i have 4 patients: theirs treatment period should be:</p>
<pre><code> patient 1 -> treatment period =2
patient 2 -> treatment period =4
patient 3 -> treatment period =5
patient 4 -> treatment period =8
</code></pre>
<p>I obtain these treatment periods when i use only constraint 1 to 5. But when i add constraint 6, i will have :</p>
<pre><code> patient 1 -> treatment period =2
patient 2 -> treatment period =4
patient 3 -> treatment period =8
patient 4 -> treatment period =14
</code></pre>
<p>(patient3 and 4 will be treated in others periods => and that is not true) </p>lollaWed, 21 Sep 2016 06:56:54 -0400http://www.or-exchange.com/questions/14207/constraint-formulation/14215Comment by Walter on Walter's answerhttp://www.or-exchange.com/questions/14207/constraint-formulation#14213<p>What do you mean by "some patients will be treated in their exact period and others will not"? I think I am missing some important information here.</p>WalterTue, 20 Sep 2016 11:40:56 -0400http://www.or-exchange.com/questions/14207/constraint-formulation#14213Comment by lolla on Walter's answerhttp://www.or-exchange.com/questions/14207/constraint-formulation#14212<p>Hi,</p>
<p>Thanks for the proposition. </p>
<p>My problem when i add another constraint the period of treatment will change and is not exact (e.g: some patients will be treated in their exact period and others will not)</p>lollaTue, 20 Sep 2016 07:29:36 -0400http://www.or-exchange.com/questions/14207/constraint-formulation#14212Answer by Walterhttp://www.or-exchange.com/questions/14207/constraint-formulation/14210<p>If I understand your problem correctly I would suggest to modify the formulation as follows:</p>
<pre><code>Treat[p][t]: {1: if patient p is treated during period t}
//Introduce one more variable type:
StartTreat[p][t]: {1: if the treatment of a patient starts in period t}
//For simplicity, instead of using a parameter dur[p] lets use a parameter periods[p] which tells us for how many periods a patient needs to be treated
periods[p]: {would correspond to ceil(dur[p]/30)}
//A patient is treated exactly once
forall(p in 1..P)
sum(t in 1..T)(StartTreat[p][t]) == 1;
//If the treatment is started it cannot be interrupted
forall(p in 1..P, t in 1..T)
StartTreat[p][t]*periods[p] <= sum(d in 1..periods[p])(Treat[p][t+d-1])
//Make sure that a sufficient number of doctors is available
forall(t in 1..T)
sum(p in 1..P)(Treat[p][t]) <= sum(m in 1..M)(Occup[m][t])
</code></pre>
<p>Your problem has some characteristics of a flexible job shop scheduling problem with one operation per job. It might worthwhile to have a look at some papers which discuss MILP formulations for this type of problems.</p>WalterTue, 20 Sep 2016 03:55:37 -0400http://www.or-exchange.com/questions/14207/constraint-formulation/14210Comment by Paul Rubin on lolla's questionhttp://www.or-exchange.com/questions/14207/constraint-formulation#14208<p>Is there a requirement/assumption that patients will be treated in the order of their indices (p=1 before p=2 before ...)? Otherwise (and I suspect the answer is no), the verbal constraint(specifically the "before him") is ambiguous. In period 1, for example, if there are six patients each with duration 10 minutes, after picking two arbitrarily (10 minutes left), wouldn't all four of the others qualify as "p" in the verbal constraint?</p>Paul RubinMon, 19 Sep 2016 15:49:26 -0400http://www.or-exchange.com/questions/14207/constraint-formulation#14208