CODEWITHSUNDEEP
pythonor-toolscp-sat
Leszek Pachura
Leszek Pachura

Reputation: 569

Or-Tools CP-SAT: how to define goal function to minimize number of unique booked rooms?

I'm starting to learn ortools.sat.python / cp_model and I am confused as how to use model.minimize()/maximize().

Let's take an example simple problem of booking meetings to timeslots and rooms:

model = cp_model.CpModel()
bookings = {}
for m in meetings:
    for t in timeslots:
        for r in rooms:
            bookings[(m, t, r)] = model.new_bool_var(f"{m}_{t}_{r}")

# 1. each meeting shall be held once
for m in meetings:
    model.add_exactly_one(bookings[(m, t, r)] for r in rooms for t in timeslots)

# 2. no overbooking: no two meetings can be booked for the same timeslot-room pair
for t in timeslots:
    for r in rooms:
        model.add_at_most_one(bookings[(m, t, r)] for m in meetings)

Now, what I would like to further improve, is to minimize the total number of different booked rooms. In other words, if it is possible to create the whole booking schedule using e.g. 3 rooms only (and not all 5 or 6 that are available), then such solution should be preferred.

How do I do that?

If I wanted to minimize the total number of bookings for room #1, I would simply write:

model.minimize(sum(bookings[(m, t, room_1)] for m in meetings for t in timeslots))

To calculate the total number of different booked rooms AFTER finding the solution, I would write:

total_rooms_used = 0
for r in rooms:
    room_r_bookings = sum(solver.value(bookings[(m, t, r)]) for t in timeslots for m in meetings)
    if room_r_bookings > 0:
        total_rooms_used += 1
print(f"Total rooms used: {total_rooms_used}")

However, my problem is that I want to minimize total_rooms_used, and I don't know how to put it in model.minimize(...)

Upvotes: 0

Views: 99

Answers (1)

Laurent Perron
Laurent Perron

Reputation: 11014

    all_rooms_used = []
    for r in rooms:
      room_used = model.new_bool_var(f"room_used({r})")
      all_rooms_used.append(room_used)
      all_bookings = []
      for m in meetings:
        for t in timeslots:
          model.add_implication(bookings[(m, t, r)], room_used)
          all_bookings.append(bookings[(m, t, r)])
      model.add_bool_or(all_bookings).only_enforce_if(room_used)

    # symmetry breaking
    for i in range(len(all_rooms_used) - 1):
      model.add_implication(~all_rooms_used[i], ~all_rooms_used[i + 1])

    model.minimize(sum(all_rooms_used))

Upvotes: 1

Related Questions