Skip to main content

Examination Timetabling Problem - First steps with Gurobi

Answered
Carlo Eggenschwiler
Edited
  • Gurobi-versary
  • First Question
  • First Comment

Hi all

I'm new to Gurobi. I have to solve an Examination Timetabling Problem. This is the usecase: Students have presentations (ca. 200). Each presentation has to be assigned to one room and one timeslot. All timeslots are of the same length.

I started creating an 3-dimensional array of the size of presentations * rooms * timeslots. Each position of the array is initialized with a binary var and named with the id of the presentation, room and timeslot.

The first constraint that I have to solve is, that every presentation has to be assigned in one room and one timeslot.

// Setup assignment variables
GRBVar[][][] assignVars = new GRBVar[presentations.size()][rooms.size()][timeslots.size()];

for (Presentation presentation : presentations) {
    for (Room room : rooms) {
        for (Timeslot slot : timeslots) {
            assignVars[presentation.getId()][room.getId()][slot.getId()] = grbModel.addVar(0.0, 1.0, 0.0, GRB.BINARY, "presRoomTime" + "_p" + presentation.getId() + "_r" + room.getId() + "_s" + slot.getId());
        }
    }
}

// START CONSTRAINT:  Each presentation must be in a room at a time
for (Presentation p : presentations) {
    GRBLinExpr lhs = new GRBLinExpr();
    for (Timeslot t : timeslots) {
        for (Room r : rooms) {
            lhs.addTerm(1.0, assignVars[p.getId()][r.getId()][t.getId()]);
        }
    }
    grbModel.addConstr(lhs, GRB.EQUAL, 1.0, "ALL_SCHEDULED");
}
// END CONSTRAINT

Gurobi says there is a optimal solution. But my observer says that all rooms are used. What is wrong?

How can I tell Gurobi to print the vars that are "true"/1?

     ROOM|312|105|106|107|108|109|203|205|206|207|209|210|211|213|217|218|305|306|307|308|310|311|303|320|304|E11|E12|
Fr 08:00 |186|003|161|079|105|099|068|184|062|180|184|186|060|098|180|047|180|002|010|021|000|097|172|076|168|050|006|
Fr 08:45 |104|139|187|067|043|075|127|170|044|045|173|013|107|058|065|127|165|117|156|015|074|176|150|171|176|158|132|
Fr 09:30 |092|096|069|145|076|018|134|013|184|020|164|159|161|037|135|100|070|162|040|095|122|090|065|121|116|024|131|
Fr 10:15 |069|029|085|058|178|100|069|067|006|033|159|130|081|105|089|176|052|041|043|017|135|087|123|052|033|184|066|
Fr 11:00 |045|060|075|145|172|160|112|105|077|007|052|173|130|086|031|165|122|126|121|098|066|147|045|120|064|072|172|
Fr 11:45 |168|160|088|037|148|004|157|049|065|048|179|116|064|083|045|100|054|008|165|118|065|051|062|071|106|115|186|
Fr 12:30 |027|015|186|139|020|084|015|058|075|132|001|017|112|098|176|018|116|102|118|024|063|070|126|026|049|068|178|
Fr 13:30 |003|157|163|031|100|084|096|076|142|035|106|039|153|096|115|063|108|072|033|162|081|084|172|006|112|018|040|
Fr 14:15 |133|091|024|149|067|021|016|152|134|056|168|099|184|124|107|154|012|039|049|064|097|091|083|161|096|006|020|
Fr 15:00 |126|081|118|112|111|159|145|152|087|077|046|185|124|049|096|062|135|073|083|029|148|029|012|169|062|024|124|
Fr 15:45 |034|178|135|155|043|156|138|010|059|095|055|127|120|009|144|148|109|007|072|107|010|039|088|089|029|074|122|
Fr 16:30 |068|128|007|186|070|052|024|129|098|075|052|010|034|066|123|168|079|080|086|059|085|186|184|055|080|121|124|
Fr 17:15 |098|107|104|059|082|162|105|090|052|180|061|104|022|029|162|061|153|025|040|070|023|133|007|029|032|006|068|
Sa 08:00 |140|068|015|024|021|188|147|179|002|095|084|094|174|149|117|011|024|044|073|157|137|178|077|073|001|156|109|
Sa 08:45 |170|108|100|014|138|074|003|032|078|131|124|159|163|169|079|098|084|107|140|067|015|002|177|102|018|134|027|
Sa 09:30 |009|089|042|076|122|000|117|045|156|124|052|059|126|029|017|009|042|092|087|034|097|042|015|075|140|186|109|
Sa 10:15 |027|114|000|139|019|141|114|156|005|052|148|188|141|073|133|061|009|051|145|072|123|145|138|161|019|132|074|
Sa 11:00 |138|152|085|006|028|181|099|065|106|022|037|031|012|126|012|150|099|051|046|153|020|083|107|110|112|066|081|
@Override
public void callback() {
    Planning planning = new Planning();
    planning.setTimeslots(timeslots);
    planning.setRooms(rooms);
    for (Timeslot t : timeslots) {
        for (Room r : rooms) {
            for (Presentation p : presentations) {
                if (assignVars[p.getId()][r.getId()][t.getId()] == null) continue;
                planning.getSolutions().add(new Solution(r, t, p, p.getExpert(), p.getCoach()));
            }
        }
    }
    System.out.println(planning.toString());
}

Thanks a lot for your help.

Kind regards

Carlo

0

Comments

5 comments

Date Votes
  • Official comment
    Simranjit Kaur
    • Gurobi Staff
    Edited
    This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
  • Eli Towle
    • Gurobi Staff

    Hi Carlo,

    You can retrieve the solution value of a variable by using GRBVar.get() to query the GRB.DoubleAttr.X attribute. With binary variables, it's good practice to check if the value is actually within a small tolerance of 0 or 1, in case the value found by the solver is very slightly different (e.g., \( 10^{-8} \)).

    Does this answer your question? Thanks!

    Eli 

    0
  • Carlo Eggenschwiler
    • Gurobi-versary
    • First Question
    • First Comment

    Hi Eli

    Thanks, that helped.

    I simplified the input data and can now log the solution.

    But what I still dont understand is why all presentations are assigned to the same room.

    GRBVar[][][] x = new GRBVar[nPresentations][nTimeslots][nRooms];
    for (int p = 0; p < nPresentations; ++p) {
        for (int t = 0; t < nTimeslots; ++t) {
            for (int r = 0; r < nRooms; ++r) {
                x[p][t][r] = model.addVar(0, 1, 1.0, GRB.BINARY, presentations[p] + "." + timeslots[t] + "." + rooms[r]);
            }
        }
    }

    // CONSTRAINT: presentation in one room and one timeslot
    for (int p = 0; p < nPresentations; ++p) {
        GRBLinExpr lhs = new GRBLinExpr();
        for (int t = 0; t < nTimeslots; ++t) {
            for (int r = 0; r < nRooms; ++r) {
                lhs.addTerm(1.0, x[p][t][r]);
            }
        }
        model.addConstr(lhs, GRB.EQUAL, 1.0, presentations[p]);
    }
    // END

     

    Optimization complete
    Solution found, objective = 7.0
    P1.T1.R1 1.0
    P2.T1.R1 1.0
    P3.T1.R1 1.0
    P4.T5.R4 1.0
    P5.T1.R1 1.0
    P6.T1.R1 1.0
    P7.T1.R1 1.0

    Is there someting wrong with my constraint modellation?

    Thanks!

     

    0
  • Thomas Opfer
    • Gurobi-versary
    • Thought Leader

    I think you need constraints that state that not more than one presentation may be in the same room at the same time. Otherwise, that would be perfectly ok.

    0
  • Carlo Eggenschwiler
    • Gurobi-versary
    • First Question
    • First Comment

    Hi Thomas

    Thanks for the reply. You were right. I implemented this constraint and now the assignment is correct. Thanks a lot.

    Cheers.

    0

Post is closed for comments.

Didn't find what you were looking for?

New post