Computers Room Humans

rooming.mod

# Rooming people into double rooms and single rooms while considering both
# (lack of) roommate preference and room choice preference.

# Written in GNU MathProg by Andres Erbsen <andreser@mit.edu> in Nov 2015.
# Released to public domain (or licensed under CC0 by user's choice).

# USAGE: glpsol --math singledouble.mod | tr ';' '\n'

set people;
set rooms;

# each person gains some utility out of getting placed in a room. The exact
# definition of how utility is computed is given in the constraints section.
var utility{i in people}; 

# the utility is made up as a sum of two values: the prefernce towards the
# roommate and the prefernce towards the room. The ways how these two
# preferences can depend on each other are limited: it is possible to give
# different preferences to rooms depending on whether the room is used as a
# single or a double, but it is not possible to change *room* preference
# depending on who the roommate is. In equations, living in a single gets
# represented as doubling with oneself (and mate_pref is ignored).
param pref_single{i in people, k in rooms}, >= 0, default 0;
param pref_double{i in people, k in rooms}, >= 0, default 0;
param mate_pref {i in people, j in people} >= 0, default 0;

# our solution will tell us who is living with whom, and what room they are in.
var room_with{i in people, j in people}, binary; # i and j in same (unspecified) room
var room_in{i in people, j in people, k in rooms}, binary; # i and j are in room k

maximize total : sum{i in people} utility[i];

s.t. utility_eq{i in people}: utility[i] =
	# look at all the reooms that person is in and all people they are rooming
	# with. While we know that there will be one room and one roommate, the
	# program doesn't, so we will represent this using a sum and a
	# multiplication.
	(sum{j in people, k in rooms} (room_in[i,j,k] *
		# pick the appropriate utility value depending in whether the roommate
		# is actually a different person.
		(if i == j then pref_single[i,k] else mate_pref[i,j] + pref_double[i,k])))
	# normalize each person's utility: people can use any range they want; only
	# the relative magnitudes of their chosen weights should matter. The utility
	# value for i will represent how large fraction of their maximum possible
	# utility was achieved (compared to their first choice).
	/max(1e-200, # avoid division-by-0 in case somebody enters all 0
	max{j in people, k in rooms}
		(if i == j then pref_single[i,k] else mate_pref[i,j] + pref_double[i,k]));

# each person is assigned to room with somebody (maybe themselves)
s.t. everybody_assigned{i in people}:
	sum{j in people} room_with[i,j] = 1;
# every assigned pair is given a room
s.t. assigned_has_room{i in people, j in people}:
	room_with[i,j] = sum{k in rooms} room_in[i,j,k];
# each room has no more than 1 pair in it
s.t. room_cap{k in rooms}:
	sum{i in people, j in people : i<=j} room_in[i,j,k] <= 1;

s.t. room_with_sym{i in people, j in people : i < j}:
	room_with[i,j] = room_with[j,i];
s.t. room_in_sym{i in people, j in people, k in rooms : i < j}:
	room_in[i,j,k] = room_in[j,i,k];

solve;

printf "\nutilities:\n\n";
for {i in people}
	printf "%s: %f\n", i, utility[i];
printf "\n";

for {k in rooms}
	for {i in people}
		for {j in people : i<=j}
			printf "%s",
				if room_in[i,j,k] then
					k & ": " & i & ", " & j & ";"
				else "";
printf "\n";

data;


set people := andreser other1 other2; 
set rooms := room171 theend drug sink toastie rainbow knot coke wood flower rush closet pirateship darkness loeb compass skylight dragon maze;

param pref_single
	andreser loeb 1,
	andreser knot .5,
;

param pref_double
	andreser loeb .5,
	other1 loeb 1,
	other2 loeb 1,
;

param mate_pref
	other1 other2 1,
	other2 other1 1,
;

This could probably read data from a CSV file or similar, but I haven't gotten to that yet.