If you work at Microsoft for any significant period of time you will change offices. I’ve been around for about 10 years and I think I have had 11 different offices (though my memory is growing increasingly hazy…). So I should not have been surprised when one of my colleagues asked if Solver Foundation has ever been used to figure out plans for office moves. Solver Foundation has been used for scheduling large conferences, but never for office moves. And with that, a small crusade was born, resulting in what I hope will be a few nice blog posts as well as a sample in the next version of Solver Foundation. In this post I will focus on the problem description and some recent research. In future posts I will provide code that formulates and solves office space allocation problems.
Very loosely speaking, the problem is given a) a bunch of people, b) a bunch of rooms, and c) rules for who can go in what office, what’s the best way to allocate people to rooms? In order to build any sort of meaningful mathematical model for this problem, you’ve got to get specific about the relevant attributes of people, rooms, the restrictions, and what “best” means.
One small diversion before we get into the details. When I say “model”, I’m talking about the mathematical expressions and equations that describe the problem to solve. In order to build a model you’re going to need to make some assumptions, for example an assumption might be that “best” means “the office assignment that wastes the least square footage”. The assumptions you make will go a long way in determining the structure of the model. Furthermore, the structure of the model goes a long way in determining the right solution approach, and the solution approach determines whether you will be happy with the accuracy and performance of the solution itself. An advantage of Solver Foundation is that you do not have to worry so much about determining the right solution approach for a model, because Solver Foundation takes care of problem analysis and solver selection. However this does not take care of everything. For one thing, there is the question of what assumptions to make, and how to build the model. That ain’t easy. In many cases there are lots of different reasonable assumptions you could make, and it isn’t always clear which ones are appropriate and which are not. For example, why shouldn’t “best” mean “the office assignment that makes the most people happy”? And even if you build a nice model based on a certain set of assumptions, and then you change your assumptions slightly, the right model and solution approach may be very different. For this problem I’m going to lay out a certain set of very reasonable assumptions and build a model. But keep in mind that if I started with different assumptions then my model and solution approach would be quite different.
I did a bit of searching on the web and found that Dario Landa-Silva has several nice papers on the office allocation problem [link]. A recent paper with Özgür Ülker [link] explores a mixed integer (MIP) model for office space allocation. The objects of interest are entities (i.e. people) and rooms. Entities are characterized primarily by a “usage requirement”: the square footage they require. Rooms have a square footage attribute, as well as lists of adjacent and “nearby” rooms. The concept of usage requirements is not what we usually want at Microsoft: we usually think in terms of one or two people being allocated to an office. For certain groups with more flexible workspace this makes more sense though. The concepts of “adjacent” and “nearby” seem sensible: they remove potentially unnecessary complexity due to trying to incorporate distance information into the model.
The MIP model considers several types of constraints:
- All allocated: all entities must be assigned a room.
- Allocation: an entity must be assigned to a particular room.
- Same room: two entities must share an office.
- No sharing: an entity cannot share a room.
- Adjacency: two entities should be adjacent.
- Group by: entities in a group should be near each other.
- Away from: two entities should not be near each other.
These constraints can be either “hard” (strictly enforced) or “soft” (discouraged by means of penalty terms in the goal). Meeting rooms fit naturally into this framework too. Results are presented on some real test problems involving ~100-200 rooms and entities. They are able to solve many of the test models to optimality using CPLEX 11.
The next few posts will lay out Solver Foundation code that builds and solves office allocation models of this type. If you read the Landa-Silva and Ulker’s paper you will see exactly how we will proceed, but before doing so you may want to try formulating this problem as a Solver Foundation model by yourself.