|
From: | Jeffrey Kantor |
Subject: | Re: [Help-glpk] mathprog assistance |
Date: | Tue, 29 Mar 2016 14:39:34 +0000 |
Jeffrey,Thanks for the effort. It's very useful seeing some examples solving more complex problems. For posterity I'm pasting you final version as plain text, reason being there are no enclosures if you read this email on the archive site (which I have used in the past).i.e.:/***aim: to allocate patients to linear accelerators for treatment.patients may require linacs with certain capabilities.patients may prefer to avoid certain times of the day.each patient needs to be scheduled on exactly one machine (with sufficient capabilities)a linac can only be used by one person at a time.each linac only operates during a certain window during the day.where not all patients' time preferences can be met, preference should be given to those with more flexibility***//* big number for disjuctive constraints */param K := 24*60;/* set of linac machines and capabilities */set LINACS dimen 2;set L := setof{(l,c) in LINACS} l;set C := setof{(l,c) in LINACS} c;param hasCapability{l in L, c in C} := if (l,c) in LINACS then 1 else 0;/* linac start and finish times, minutes after midnight */param lStart{L} > 0;param lFinish{L} > 0;/* patient properties */set P;param dur{P} > 0; /* in minutes */param reqCapability{P, C} >= 0, binary;/* patient time conflicts */set TIMES;param patient{TIMES};param wStart{TIMES};param wFinish{TIMES};/* assignment of each patient to one linac with needed capabilities */var lp{P, L} >= 0, binary;s.t. assign{p in P}: sum{l in L} lp[p, l] <= 1;s.t. capabilities{p in P, l in L, c in C}:lp[p, l] * hasCapability[l, c] >= lp[p, l] * reqCapability[p, c];/* schedule patient within machine availability */var x{P} >= 0;s.t. startP{p in P, l in L}:x[p] >= lStart[l] * lp[p,l];s.t. endP{p in P, l in L}:x[p] + dur[p] <= K * (1 - lp[p,l]) + lFinish[l] * lp[p,l];/* patient sequencing on each machine */var seq{p in P, q in P, l in L : p < q}, binary; /* 1 is p is before q */s.t. p_after_q{p in P, q in P, l in L: p < q}:x[p] >= (x[q] + dur[q]) - K * seq[p, q, l]- K * (1 - lp[p, l])- K * (1 - lp[q, l]);s.t. p_before_q{p in P, q in P, l in L: p < q}:x[q] >= (x[p] + dur[p]) - K * (1 - seq[p, q, l])- K * (1 - lp[p, l])- K * (1 - lp[q, l]);/* Soft contraints on exculsion windows */var wEarly{i in TIMES} >= 0;var wLate{i in TIMES} >= 0;var ybin{i in TIMES} binary; /* Choose to either shift left or shift right */s.t. shiftEarly{i in TIMES}:wEarly[i] >= x[patient[i]] + dur[patient[i]] - wStart[i] - K * (1 - ybin[i]);s.t. shiftLate{i in TIMES}:wLate[i] >= wFinish[i] - x[patient[i]] - K * ybin[i];/* objective */var z;var penalty{p in P} >= 0;/* penalize any assignment that can't be made today's schedule */s.t. infeasPenalty{p in P}: penalty[p] >= K * (1 - sum{l in L} lp[p,l]);/* the more times they want to avoid, the less we care about them */param pWeight{p in P}, >= 0 := 10000 / (1 + sum{i in TIMES} if p = patient[i] then (wFinish[i] - wStart[i]) else 0);s.t. timePenalty{i in TIMES}: penalty[patient[i]] >= (wEarly[i] + wLate[i]);/* mixed norm objective */s.t. sup{i in TIMES}: z >= penalty[patient[i]]*pWeight[patient[i]];minimize obj: z + sum{p in P} penalty[p];solve;printf("\nResults\n");printf "z: %f\n", z;printf "\nMachine Schedule";for {l in L} {printf "\n%s (%dm utilisation):",l,sum{p in P} dur[p] * lp[p, l];printf {c in C : hasCapability[l, c] == 1}: " %s", c;printf "\n";for {k in 0..2400, p in P : round(x[p]) == k and lp[p,l] == 1} {printf " Patient %2s: %02d:%02d-%02d:%02d, penalty = %5.2fm, weight = %5d, ",p,round(x[p]) div 60,round(x[p]) mod 60,round(x[p] + dur[p]) div 60,round(x[p] + dur[p]) mod 60,penalty[p],pWeight[p];printf "Weighted penalty = %5.2f\n", penalty[p] * pWeight[p];}}printf "\nPatient Schedule Exclusions\n";printf {i in TIMES}:"Patient %2s: Excluded: %4d to %4d Scheduled: %4d to %4d\n",patient[i],wStart[i],wFinish[i],x[patient[i]],x[patient[i]] + dur[patient[i]];printf "\nPatient Schedule\n";for {p in P, l in L : lp[p,l] = 1}{printf "Patient %2s",p;printf " (";printf {c in C : reqCapability[p,c]==1}: "%s", c;printf " %dm", dur[p];printf ") %02d:%02d-%02d:%02d",round(x[p]) div 60,round(x[p]) mod 60,round(x[p] + dur[p]) div 60,round(x[p] + dur[p]) mod 60;printf " (%s:", l;printf {c in C : hasCapability[l,c]==1}: " %s", c;printf ")\n";}data;set LINACS :=LINAC1 IMRTLINAC2 VMATLINAC2 MRI;/* linac availability. 600=10am, 480=8am */param : lStart lFinish :=LINAC1 600 1200LINAC2 480 1200;/* number of minutes required to administer treatment */param : P : dur :=1 102 153 104 155 156 107 158 109 1510 1511 1012 1513 1014 1515 15;param reqCapability : IMRT VMAT MRI :=1 0 1 02 0 1 03 0 1 04 0 1 05 1 0 06 1 0 07 1 0 08 0 1 09 0 1 010 0 1 011 1 0 012 1 0 013 1 0 014 1 0 015 1 0 0;/* ie: patient 1 should AVOID between midnight and 3pm */param : TIMES : patient wStart wFinish :=1 1 800 9002 4 0 6043 4 610 1500;end;Eric WinterOn Mon, Mar 28, 2016 at 6:33 PM, Nick Farrell <address@hidden> wrote:Jeff, thank you very much for all that feedback. It will be a great help for me, both for this specific scenario and to better understand mathprog and GLPK.Hopefully others can benefit from your help too, if they find themselves in a similar situation to me.regards,NickOn 29 March 2016 at 08:29, Jeffrey Kantor <address@hidden> wrote:Nick,I've attached a more refined model for your problem. There are a large number of changes designed to improve efficiency and readability.1. The data section format has revised to better consolidate parametric data, and to provide non redundant entry of linac capabilities. This makes use of the 'setof' glpk statement.2. Syntax has been simplified in various parameter and variable declarations.3. Your model will report an infeasible solution if not all patients can be assigned to machines. This has been changed so that it assigns as many as possible given time and capability constraints. You could create a report of those left assigned.4. The objective function has been simplified with regard to encroachments on excluded time periods.5. Redundant sequencing constraints and variables have been removed.6. Redundant scheduling variables have been removed.7. Additional solution reports have been added for patient and machine schedules.8. The Big M (here K) has been fixed to the number of minutes in a day.All in all, this should provide a smaller, faster, and more robust model. It could still use some additional parameter checks, but thought this might be a good.For what it's worth, it runs quite well inside the MathProg webpage at http://www3.nd.edu/~jeff/mathprog/mathprog.html.JeffOn Sun, Mar 27, 2016 at 11:33 PM Jeffrey Kantor <address@hidden> wrote:OK. Here are some quick thoughts ...1. You can simplify the data section by defining the sets L and P when defining parameters. No efficiency gain here, just cleaner.2. When I run as is, there are 456 binary variables, 1045 constraints. The sequence constraints only need to be defined for p < q sincethe case q > p is redundant.That change alone reduces the problem to 246 binary variables and 625 constraints.3. I haven't tested this, but defining start times as x[p,l] seems redundant. The same information is coded in x[p] and lp[p,l].Points 1 & 2 are illustrated in the attached file.JeffOn Sun, Mar 27, 2016 at 10:41 PM Nick Farrell <address@hidden> wrote:Hi Jeff, thanks for looking.
My contrived example may be setting only one capability, but usually some would have multiple capabilities. For example, an IMRT machine may also have VMAT capabilities.
My intention is that if a patient requires multiple capabilities, they all have to be simultaneously satisfied before a linac is a viable candidate.
Hope that helps.
Nick
On 28 Mar 2016 1:18 PM, "Jeffrey Kantor" <address@hidden> wrote:Hi Nick,In looking through the model, one question concerns the linac capabilities. These are coded as IMRT, VMAT, and MRI. Each machine has one and only one of the of these capabilities. And each patient requires one and only capability. Is that true in general, or is that just true for this example?JeffOn Sun, Mar 27, 2016 at 9:50 PM Nick Farrell <address@hidden> wrote:It appears the list server is scrubbing my text files:
_______________________________________________
schedule.mod:
https://drive.google.com/file/d/0B8FyZKjT_SdKQy1wN3FBRWt6a2c/view?usp=docslist_api
Help-glpk mailing list
address@hidden
https://lists.gnu.org/mailman/listinfo/help-glpk
_______________________________________________
Help-glpk mailing list
address@hidden
https://lists.gnu.org/mailman/listinfo/help-glpk
[Prev in Thread] | Current Thread | [Next in Thread] |