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:56:54 -0400Answer 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/14215Answer 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/14210