Examination Timetabling Problem - First steps with Gurobi

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

正式なコメント

Simranjit Kaur

Gurobi Staff

2025年06月23日 03:14 編集済み

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

2020年04月22日 02:13

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

Carlo Eggenschwiler

2020年04月22日 07:38

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!

Thomas Opfer

2020年04月22日 20:49

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.

2020年04月26日 07:33

Hi Thomas

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

Cheers.

Examination Timetabling Problem - First steps with Gurobi

コメント

お探しのものを見つけられませんでしたか？