Help with extension on example room_assignment.ipynb

[jpoberhauser]

Apologies if this is not the right forum for this question, will close Issue if so.

I am attempting a small extension on the room_assignment problem where there is also a numeric 'utility' to each request for room assignment. The goal would be to maximize utility while keeping the no-overlap constraints.

For example, input data could be: start | end | utility_room_1 | utility_room_2 | utility_room_3 1 52 6399.9 0.00 0.00
1 23 99.0 799.90 0.00
1 23 0.0 1494.90 0.00
23 24 0.0 0.00 0.00 23 24 0.0 0.00 0.00 24 27 0.0 0.00 199.90 24 27 0.0 100.00 0.00
29 47 0.0 0.00 99.99
29 47 0.0 1599.95 199.88

Where start and end are days of the year for example, utility is calculated with some utility function that helps requests rank room assignment, and the task is to maximize utility on room assignment without allowing for overlaps on start and end days.

Thank you in advance for the guidance

[tias]

No problem.

It is exactly like you say, you can keep the constraints as they are and should add an objective function, e.g. through m.maximize(obj) where obj is an objective function (see knapsack example for the simplest form of objective function).

In your case, you could iterate over the rows of your data, such that you end up with something like obj = sum([(roomvar[0]==0)*6399.9, (roomvar[0]==1)*0.0, ...)

One caveat: ortools does not accept float constaints, so multiply by 100 and round.

If you have more concrete code snippets on which you are stuck we can give more concrete advice too.

[jpoberhauser]

Thanks for the quick reply, I really appreciate it.

The example that works so far is:

from cpmpy import *  # CPMpy constraint solving library
import pandas as pd

d = {'start': [1, 1, 1, 23, 23, 24, 24, 29, 29], 
    'end': [52, 23, 23, 24, 24, 27, 27, 47, 47],
    'utility_room_0': [639990,9900, 0,0,0,0,0,0,0 ],
    'utility_room_1' : [0,79990, 149490, 0,0,0, 10000, 0, 159995],
    'utility_room_2' : [0,0,0,0,0, 19990, 0 , 9999, 19988]}
df_reqs = pd.DataFrame(data=d)
max_rooms = 3

n_requests = len(df_reqs)
print(f"number of requests {n_requests}")
requestvars = intvar(0, max_rooms-1, shape=(n_requests,))# intvar(lower_bound, upper_bound, and shape) # shape can be a tuple to make a matrix-or anyn-dimensional object
print(f"IntVars for request variables: {requestvars}")

m = Model()
# Let's say there is no explicit room preference, just utility function
# for idx, row in df_reqs.iterrows():
#     if not pd.isna(row['overall_room_preference']):
#         m += (requestvars[idx] == int(row['overall_room_preference']))
# A room can only serve one request at a time.
# <=> requests on the same day must be in different rooms
for day in range(min(df_reqs['start']), max(df_reqs['end'])):
    overlapping = df_reqs[(df_reqs['start'] <= day) & (day < df_reqs['end'])]
    if len(overlapping) > 1:
        m += AllDifferent(requestvars[overlapping.index])

sat = m.solve()
print(sat, m.status())

I was able to add the constraints thanks to your suggestions, so I'll post below in case its useful for others:

n_requests = len(df_reqs)
print(f"number of requests {n_requests}")
requestvars = intvar(0, max_rooms-1, shape=(n_requests,))# intvar(lower_bound, upper_bound, and shape) # shape can be a tuple to make a matrix-or anyn-dimensional object
print(f"IntVars for request variables: {requestvars}")
max_rooms = 3

# Let's say there is no explicit room preference, just utiliy function
# for idx, row in df_reqs.iterrows():
#     if not pd.isna(row['overall_room_preference']):
#         m += (requestvars[idx] == int(row['overall_room_preference']))

### Create obj function
obj_list = []
for idx, row in df_reqs.iterrows():
    utils = [row.utility_room_0, row.utility_room_1, row.utility_room_2]
    for j in range(max_rooms):
        obj_list.append((requestvars[idx]==j)* utils[j])
obj = sum(obj_list)
m = Model(maximize=obj)

# A room can only serve one request at a time.
# <=> requests on the same day must be in different rooms
for day in range(min(df_reqs['start']), max(df_reqs['end'])):
    overlapping = df_reqs[(df_reqs['start'] <= day) & (day < df_reqs['end'])]
    if len(overlapping) > 1:
        m += AllDifferent(requestvars[overlapping.index])

sat = m.solve()
print(sat, m.status())

I am using this for a Multiple Object Tracker, and its great how integrated it is to numpy and can be weaved into other deep learning approaches. Thanks again for your help.

[tias]

Hi Juan Pablo,

Yes, exactly.

Slightly more elegantly as

for val, util in enumerate([row.utility_room_0, row.utility_room_1, row.utility_room_2]):
  obj_list.append( (requestvars[idx]==val)* util

I was unsure how fluent you were in NNs. We actually do exactly this in our 'visual sudoku' perception-based solving, if which you find a notebook (the objective is added somewhere in the middle), here: https://github.com/CPMpy/cpmpy/blob/master/examples/advanced/visual_sudoku.ipynb

Happy you appreciate the library, it is exactly made for these kinds of things. I'd be interested to hear more about your research too, feel free to drop me an email (tias.guns@kuleuven.be)