Re: [Help-glpk] mathprog assistance

[Eric Winter]

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.:

https://lists.gnu.org/archive/html/help-glpk/2016-03/msg00050.html

/***

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 IMRT

    LINAC2 VMAT

    LINAC2 MRI

;

/* linac availability. 600=10am, 480=8am */

param : lStart lFinish :=

    LINAC1   600   1200

    LINAC2   480   1200;

/* number of minutes required to administer treatment */

param : P : dur :=

     1   10

     2   15

     3   10

     4   15

     5   15

     6   10

     7   15

     8   10

     9   15

    10   15

    11   10

    12   15

    13   10

    14   15

    15   15

;

param reqCapability : IMRT VMAT MRI :=

     1   0   1    0

     2   0   1    0

     3   0   1    0

     4   0   1    0

     5   1   0    0

     6   1   0    0

     7   1   0    0

     8   0   1    0

     9   0   1    0

    10   0   1    0

    11   1   0    0

    12   1   0    0

    13   1   0    0

    14   1   0    0

    15   1   0    0

;

/* ie: patient 1 should AVOID between midnight and 3pm */

param : TIMES : patient wStart wFinish :=

    1   1   800    900  

    2   4     0    604

    3   4   610   1500

;

end;

Eric Winter

On 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,

Nick

On 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. 

Jeff

On 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 since

the 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. 

Jeff

On 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?

Jeff

On 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

Python: https://drive.google.com/file/d/0B8FyZKjT_SdKcmttMzZfdW91emhIcjRaWFFQWTZQMnhzR0dB/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