Suggestions on model

New to AMPL
1

hi, i am trying to make an automated class scheduling . Can you suggest how can i constraint the assignment of rooms only to their predefined buildings only. Also how to avoid assigning time in between lunchbreak

update: I already solved the issue with predefined buildings, but I’m stuck on how to assign class codes that are not assigned due to lack of rooms. now I want the unassigned class codes to be assigned from the available rooms remaining, ignoring the building constraint

# Sets
set CODE;
set ROOMS;
set DAYS ordered := {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday"};
set TIME ordered := {"8:00am - 9:00am", "9:00am - 10:00am", "10:00am  11:00am", "11:00am - 12:00nn", "1:00pm - 2:00pm", "2:00pm - 3:00pm", "3:00pm - 4:00pm", "4:00pm - 5:00pm"};

# Paramaters
param program{CODE} symbolic;
param section{CODE} symbolic;
param course_num{CODE} symbolic;
param course_title{CODE} symbolic;
param room{CODE} symbolic;
param lec{CODE} >= 0;
param lab{CODE} >= 0;
param teaching_load{CODE} >= 0;
param building{CODE} symbolic;

param buildings{ROOMS} symbolic;
param floor{ROOMS} symbolic;
param type{ROOMS} symbolic;
param lecture{ROOMS} binary;
param laboratory{ROOMS} binary;

# Read data from Excel
load amplxl.dll;
table overall IN "amplxl" "timetable.xlsx" "overall":
    CODE <- [CODE], program, section, course_num, course_title, room, lec, lab, teaching_load, building;
table rooms IN "amplxl" "timetable.xlsx" "rooms":
    ROOMS <- [ROOMS], buildings, floor, type, lecture, laboratory;
    
read table overall;
read table rooms;

var assignment{CODE, ROOMS, DAYS, TIME} binary;
var room_assigned{CODE, ROOMS} binary;

# Constraints
subject to building_constraint {c in CODE, r in ROOMS}:
    room_assigned[c, r] = if buildings[r] = building[c] then 1 else 0;

subject to required_hours_per_code{c in CODE}:
    sum{r in ROOMS, d in DAYS, t in TIME} assignment[c, r, d, t] = lec[c] + lab[c];
    
subject to no_conflicts {r in ROOMS, d in DAYS, t in TIME}:
    sum {c in CODE} assignment[c, r, d, t] <= 1;

subject to available_slots {c in CODE, r in ROOMS, d in DAYS, t in TIME}:
    assignment[c, r, d, t] <= room_assigned[c, r];
    
#subject to assign_remaining_rooms {c in CODE, r in ROOMS, d in DAYS, t in TIME}:
#	assignment[c, r, d, t] = if room_assigned[c, r]= 0 then 1 else 0;
2

Because required_hours_per_code is an = constraint, it requires every class code to be fully assigned. Thus either all codes will be assigned, or the solver will report “no feasible solution” and probably it will not return any useful solution.

Here’s a sketch of a possible alternative approach, which you can adapt to your specific needs.

To compute an initial solution that makes as many assignments as possible, change required_hours_per_code to a <= constraint, and adding an objective function to maximize the number of successful assignments (the sum of all the assignment variables).

After the solver returns a solution, use AMPL’s fix command to fix all of the assignments that have been made:

fix {c in CODE, r in ROOMS, d in DAYS, t in TIME: 
   assignment[c,r,d,t] = 1} assignment[c,r,d,t];

Then drop the constraints involving room_assigned, change required_hours_per_code to an = constraint, and solve again:

drop building_constraint;
drop available_slots;
redeclare subject to required_hours_per_code{c in CODE}:
    sum{r in ROOMS, d in DAYS, t in TIME} assignment[c, r, d, t] = lec[c] + lab[c];
solve;
3

Thanks for the suggestions! Really appreciate it.

4

Hello again, could you please recommend an open source solver similar to Gurobi that is suited for my model?

5

Try HiGHS. It has a full AMPL interface, and (like Gurobi) it accepts problems (like yours) that have integer (including binary) variables with linear objectives and constraints.

1 Like
7

Is room_assigned[c,r] equal to 1 if and only if code c is assigned to room r? Then your constraints each_code_one_room say that each code is assigned to at most one room.

I am not sure what you mean by the “gap intervals”. Can you give some more detail?

  • Explain what the variable gap[c,r,d,t] represents in the model.
  • Describe in words the meaning of the constraint calculate_gap.

Also, note that, in general, you cannot minimize two objective functions at the same time: solutions that maximizes successful_assignments may not minimize total_gap, and solutions that minimizes total_gap may not maximize successful_assignments.

9

The “presolve” messages are telling you that your problem has no feasible solution: there is no way to assign values to the variables that are within the variables’ bounds and that also satisfy all of the constraints. As an example, consider the first message:

presolve, variable room_assigned['BSMR_ME 4B_ME Elective 2','AB1 - 206 IT Lab 4']:
        impossible deduced bounds: lower = 0, upper = -20

This binary variable must be \geq 0 (hence “lower = 0”). But based on an analysis of the constraints where this variable appears, AMPL has also proved that it must be \leq -20 in any feasible solution (“upper = -20”). Since a variable cannot be \geq 0 and also \leq -20, this proves that no feasible solution is possible.

A possible cause is as follows: By analyzing the other constraints, presolve is determining that a lot of the room_assigned variables have to equal 1; and as a result, sum {r in ROOMS} room_assigned[c, r] <= 1 cannot possibly be satisfied in all cases. You can check by using the command

display room_assigned.lb;

after solve, to display the lower bounds that presolve found for these binary variables. Look to see if there are many that have lower bounds of 1, which imply that they must equal 1.

This proof of infeasibility occurs in AMPL’s “presolve” phase, while the problem is being generated for the solver. Thus the problem is never actually sent to the solver. You will need to fix this problem before you can determine whether the objective function penalties are working.