Skip to content

Instantly share code, notes, and snippets.

@seanstickle

seanstickle/gist:a2678348fd1ada34eb00

Created June 27, 2015 13:16
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save seanstickle/a2678348fd1ada34eb00 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save seanstickle/a2678348fd1ada34eb00 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. seanstickle created this gist Jun 27, 2015.
    83 changes: 83 additions & 0 deletions gistfile1.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,83 @@
    #
    # CONFERENCE SCHEDULING
    #
    # Finds a solution to scheduling all the education
    # sessions at the annual conference
    #

    /* Rooms, Days, Times */
    set ROOMS;
    set DAYS;
    set TIMES;

    /* Presenters, Topics */
    set PRESENTERS;
    set TOPICS;

    /* Sessions: index, ID, topic, rank, presenter */
    set SESSIONS, dimen 5;
    set S := setof{(a,b,c,d,e) in SESSIONS} a;

    /* Assignment */
    var x{d in DAYS, t in TIMES, r in ROOMS, s in S}, binary;

    /* Objective Function */
    minimize obj:
    sum{d in DAYS, t in TIMES, r in ROOMS, s in S} x[d,t,r,s];

    /* Constraint 1: each session is scheduled exactly once */
    s.t. c1 {s in S} :
    sum{d in DAYS, t in TIMES, r in ROOMS} x[d,t,r,s] = 1;

    /* Constraint 2: each day-time-room doesn't have more than
    * one session scheduled
    */
    s.t. c2 {d in DAYS, t in TIMES, r in ROOMS} :
    sum{s in S} x[d,t,r,s] <= 1;

    /* Constraint 3: each day-time doesn't have a presenter
    * in more than one scheduled session
    */
    s.t. c3 {d in DAYS, t in TIMES, p in PRESENTERS} :
    sum{r in ROOMS, s in S} x[d,t,r,s] <= 1;


    /* SOLVE! */
    solve;

    /* Output */

    printf "\n";
    printf "=============================================\n";

    for {d in DAYS} {
    for {t in TIMES} {
    for {r in ROOMS} {
    for {s in S} {
    for {{0}: x[d,t,r,s] == 1} {
    printf "%s\t%s\t%s\t%s\n", d, t, r, s;
    }
    }
    }
    }
    }


    /* DATA */
    data;

    set ROOMS := A B;
    set DAYS := Thu;
    set TIMES := 900 1000;
    set TOPICS := Bio Tech Math;
    set PRESENTERS := Tom Jerry Nancy;

    set SESSIONS :=
    1 20A Bio 9 Tom
    2 3B1 Tech 8 Jerry
    3 7KC Math 7 Tom
    4 L9U Bio 6 Nancy;

    /* EOF */

    end;