Planning office moves with Solver Foundation: Part II

This is the second part in a multi-part series on planning office moves using Solver Foundation. Part I introduced the problem and provided a pointer to a solution approach. In this post we will write code to read problem instances and evaluate their quality. Using this code you’ll be able try out your own heuristics for solving office allocation problems. In future posts we’ll consider how to build a Solver Foundation model capable of finding optimal allocations.

From the last post you know that our task is to assign entities (usually people) to offices so that the amount of space is used as effectively as possible, and so that constraints such as “same room”, “group by”, “next to”, and “away from” are satisfied. Let’s formalize the specification of a problem so we can get into the details. To specify a problem instance we need to identify:

  • Entities: how much space does an entity require? Also to model “group by” constraints we’ll need to know which group an entity belongs to. A group could correspond to a department in an organization.
  • Rooms: what is the size of each room? Which rooms are adjacent? Which rooms are considered to be “nearby”?
  • Constraints: what is the constraint “type” (that is, in the bulleted list from the last post, which one are we talking about?) What are the relevant entities and rooms for the constraint?

Let’s take a simple example. Suppose we’re planning a move involving ten employees and (sadly) only nine offices. The ten employees are divided among two groups: the Form team and the Function team. (In case you were wondering, these are the names of the members of the Solver Foundation team. Here is a link to a team photo.)

Name Group Space
Alexander Form 15
Banksy Form 10
Christo Form 15
David Function 9
Einstein Function 15
Fabio Form 6
Galileo Function 6
Holmes Function 4
Icarus Form 4
Jian Function 6

The offices are on two floors of the building. Let’s say that offices are adjacent if they are either next to or across from each other (“kitty corner” does not count: we’re using the L1 norm…) and offices are “nearby” if they are on the same floor. Here is the floor plan. The area of an office is the number of cells inside.

Floor 1:         Floor 2:
+—-+—+—+    +—+—+—+
|101 |103|105|    |201|  203  |
|    |   |   |    |   |       |
+—-+—+—+    +—+—+—+

+—+—+—+    +—+—+—+
|102|104|106|    |    202    |
|   |   |   |    |           |
+—+—+—+    +—+—+—+

A constraint is described by a tuple (type, subject, target, hard). The type is one of { allocate, same room, no sharing, adjacency, group by, away from}. The subject and target are either rooms or entities depending on the type of constraint. “Hard” is a boolean value that indicates whether the constraint is to be strictly enforced or not. If a constraint is not strictly enforced then violating it will incur a penalty. Following the paper, let’s use these penalties:

  • Adjacent = 10
  • Allocate = 20
  • Away from = 10
  • No sharing = 50
  • Same room = 10
  • Group by = 11.18

The soft constraint violation penalties form one part of the objective. The other part of the objective relates to how effectively the space was allocated. For each room, compare the amount of space used (by adding the space required by each entity) to the room’s size. If there is wasted space, add it to the objective. If there is a shortage of space, double this amount and add it to the objective. So the goal is wastage cost + overuse cost + penalty cost.

On Landa-Silva’s site you can find sample problems in Access (MDB) format. Each MDB file contains tables with the entities, rooms, and constraints. We will follow the same basic schema, but we will instead use XML because it will be easier to load into our C# program. (You can convert the files yourself using my advice in this post.) You can download the XML for my sample problem (with a few constraints) here: [link]. (Download BOTH “sample.xml” and “sample.schema.xml”.)

Now that we have a sample problem, let’s write some code that:

  • Reads the XML into a data structure that represents the problem.
  • Initializes the penalty weights as specified above.
  • Assigns entities to rooms using a dumb heuristic.
  • Evaluates the quality of the solution.

Let’s start with the data. I will read the XML into a DataSet and then convert the rows into data structures. (A side note: I wrote this code really fast, so to start with I worked directly with the DataTable/DataRow objects. That works okay, but I found that the code is cleaner if you define “real” Constraint, Entity, and Room classes.) Here goes:

using System;
using System.Collections.Generic;
using System.Data;
using System.IO;
using System.Linq;
using System.Text;

namespace Samples.OfficeSpace {

  class Entity {
    public string Name { get; set; }
    public double Space { get; set; }
    public Entity(DataRow row) {
      Name = row["Name"].ToString();
      Space = Convert.ToDouble(row["Space"]);
    }
    public override string ToString() {
      return Name;
    }
  }

  class Room {
    private readonly OfficeSpaceData parent;
    private string adjacentText;

    public string ID { get; set; }
    public double Size { get; set; }
    public string Floor { get; set; }
    public IEnumerable<Room> Adjacent {
      get { return parent.AdjacentRooms(adjacentText); }
    }
    public IEnumerable<Room> Nearby {
      get { return parent.NearbyRooms(this); }
    }
    public Room(OfficeSpaceData data, DataRow row) {
      parent = data;
      ID = row["ID"].ToString();
      Floor = row["Floor"].ToString();
      adjacentText = row["Adjacent"].ToString() + "," + ID; // adding self
      Size = Convert.ToDouble(row["Size"]);
    }
    public override string ToString() {
      return ID;
    }
  }
  enum ConstraintType { AllocateTo = 0, SameRoom = 4, NoSharing = 6, Adjacent = 7, GroupBy = 8, AwayFrom = 9, Overuse = -1, Wastage = -2 }

  class Constraint {
    public ConstraintType Type { get; set; }
    public bool IsHard { get; set; }
    public string Subject { get; set; }
    public string Target { get; set; }
    public Constraint(DataRow row) {
      IsHard = Convert.ToInt32(row["Type"]) > 0;
      Type = (ConstraintType)Convert.ToInt32(row["Constraint"]);
      Subject = row["Subject"].ToString();
      Target = row["Target"].ToString();
    }
    public override string ToString() {
      return String.Format("[{0}: {1} - {2}]", Type, Subject, Target);
    }
  }

(I have omitted comments for brevity. In a future post I will post all my code in a ZIP file.) The Entity type is straightforward: it has properties for Name and Space. The constructor takes a DataRow as input. If you have looked at the sample XML then you’ll see I am just reading and converting the columns. The Room type has two quirks: the lists of Adjacent and Nearby rooms. The XML stores the adjacent rooms as a comma-separated list of IDs. When a caller asks for the list of adjacent rooms, we will ask a “parent” class OfficeSpaceData to do the parsing for us. Similarly, we will ask OfficeSpaceData to give us the list of nearby rooms, which will be defined as the set of rooms on the same floor. It seemed better to serve up this data “on demand” since we will not need these lists for all rooms. The Constraint class has one hitch: the “subject” and “target” properties are defined as strings. This is because we don’t know whether the subject/target refer to rooms or entities – it depends on the constraint type. So the properties store the ID or Name. You may also be wondering why I have given specific values to the ConstraintType items. It’s to be consistent with data files that Özgür Ülker was kind enough to share with me.

Now let’s introduce OfficeSpaceData, which is container for the Entities, Rooms, and Constraints. It’s the input data for a problem instance.

  class OfficeSpaceData {
    private Dictionary<string, Room> roomsById;
    private Dictionary<string, Entity> entitiesByName;
    private IEnumerable<Constraint> constraints;
    private Func<Room, Room[]> nearRooms;
    private Func<string, Room[]> adjRooms;
    private int entityCount, roomCount;

    public int EntityCount { get { return entityCount; } }

    public int RoomCount { get { return roomCount; } }

    public IEnumerable<Constraint> Constraints { get { return constraints; } }

    public IEnumerable<Room> RoomRows { get { return roomsById.Values; } }

    public IEnumerable<Entity> EntityRows { get { return entitiesByName.Values; } }

    public IDictionary<string, Room> RoomsByID { get { return roomsById; } }

    public IDictionary<string, Entity> EntitiesByName { get { return entitiesByName; } }

    public IEnumerable<Room> NearbyRooms(Room room) {
      return nearRooms(room);
    }

    public IEnumerable<Room> AdjacentRooms(string adjacentText) {
      return adjRooms(adjacentText);
    }

    public void ReadFromFile(string fileName, string schemaFilename) {
      FileInfo f = new FileInfo(fileName);
      DataSet dataSet = ReadDataSet(fileName, schemaFilename);
      DataTable roomData = dataSet.Tables["Rooms"];
      DataTable entityData = dataSet.Tables["Resources"];
      DataTable constraints = dataSet.Tables["Constraints"];
      this.constraints = constraints.AsEnumerable().Select(c => new Constraint(c));
      this.roomCount = roomData.Rows.Count;
      this.entityCount = entityData.Rows.Count;
      // todo: check dupes on both.
      roomsById = roomData.AsEnumerable().Select(r => new Room(this, r)).ToDictionary(r => r.ID);
      entitiesByName = entityData.AsEnumerable().Select(e => new Entity(e)).ToDictionary(e => e.Name);

      var nearMap = roomsById.Values.GroupBy(r => r.Floor)
        .Select(g => new Tuple<string, Room[]>(g.Key, g.ToArray()))
        .ToDictionary(t => t.Item1, t => t.Item2);

      nearRooms = r => nearMap[r.Floor];
      adjRooms = r => r.Split(new char[] { ',' }, StringSplitOptions.RemoveEmptyEntries).Where(rr => roomsById.ContainsKey(rr)).Select(id => roomsById[id]).ToArray();
    }

    private static DataSet ReadDataSet(string fileName, string schemaFilename) {
      DataSet dataSet = new DataSet();
      if (File.Exists(schemaFilename)) {
        dataSet.ReadXmlSchema(schemaFilename);
      }
      dataSet.ReadXml(fileName);
      return dataSet;
    }
  }
}

 

The class reads the DataSet and fills some internal data structures. Many of the data structures are exposed as properties so that we can build models and evaluate solutions. The data structures are:

  • A mapping from entity name to Entity.
  • A mapping from room ID to Room.
  • A list of Constraints.
  • A function that takes a Room and returns nearby rooms.
  • A function that takes a string and returns adjacent rooms.
  • Room, entity counts.

The “read from XML” code is trivial since it just uses built-in libraries. The mappings are easily established using LINQ expressions that query over the DataTables for rooms and entities.  (You’ll note that I have left out a bit of error checking.) Finally, the functions for “nearby” and “adjacent” also rely on LINQ expressions. The adjRooms function assumes the input string is a comma-delimited list of room IDs, e.g. “101, 102, 103”. The query filters out entries that do not actually represent valid rooms, e.g. “303”. I do this on purpose so that the sample instances on Landa-Silva’s site run without changes.

Now let’s write some code against these classes to read a problem, apply a simple heuristic, and evaluate the cost.

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
 
namespace Samples.OfficeSpace {
  public class Program {
 
    static void Main(string[] args) {
      if (args.Length == 0 || !args[0].EndsWith(".xml", StringComparison.InvariantCultureIgnoreCase)) {
        Console.WriteLine("Please specify the path to an XML file.");
        return;
      }

      string fileName = args[0];
      if (!File.Exists(fileName)) {
        Console.WriteLine("Could not find input file '{0}'.", fileName);
        return;
      }

      string schemaFileName = fileName.ToLowerInvariant().Replace(".xml", ".schema.xml");

      Program p = new Program();
      p.Run(fileName, schemaFileName);
    }

    private void Run(string fileName, string schemaFilename) {
      Console.WriteLine("FILE: {0}", fileName);

      OfficeSpaceData data = new OfficeSpaceData();
      data.ReadFromFile(fileName, schemaFilename);
      IDictionary<string, string> entityToRoom = Heuristic(data);

      Dictionary<ConstraintType, double> penalties = GetPenaltyWeights();
      Console.WriteLine("COST = " + Evaluate(data, penalties, entityToRoom));
    }

    private IDictionary<string, string> Heuristic(OfficeSpaceData data) {
      var rooms = data.Rooms.Select(r => r.ID).ToArray();
      Dictionary<string, string> entityToRoom = new Dictionary<string, string>(data.EntityCount);
      int k = 0;
      foreach (var entity in data.Entities) {
        entityToRoom[entity.Name] = rooms[(k++) % data.RoomCount];
      }
      return entityToRoom;
    }

    private static Dictionary<ConstraintType, double> GetPenaltyWeights() {
      // page 5
      Dictionary<ConstraintType, double> penalties = new Dictionary<ConstraintType, double>();
      penalties[ConstraintType.Adjacent] = 10;
      penalties[ConstraintType.AllocateTo] = 20;
      penalties[ConstraintType.AwayFrom] = 10;
      penalties[ConstraintType.NoSharing] = 50;
      penalties[ConstraintType.SameRoom] = 10;
      penalties[ConstraintType.GroupBy] = 11.18;
      penalties[ConstraintType.Wastage] = 1;
      penalties[ConstraintType.Overuse] = 2;

      return penalties;
    }

    private static double Evaluate(OfficeSpaceData data,
      Dictionary<ConstraintType, double> penalties,
      IDictionary<string, string> entityToRoom) {
      SolutionEvaluator e = new SolutionEvaluator(data, entityToRoom, penalties);
      double cost = 0;
      string e1, e2, room;
      foreach (var constraint in data.Constraints) {
        switch (constraint.Type) {
        case ConstraintType.NoSharing:
          if (TryGetSubjectEntity(data, constraint, out e1)) {
            cost += e.NoSharingCost(e1);
          }
          break;

        case ConstraintType.AllocateTo:
          if (TryGetSubjectEntity(data, constraint, out e1) && TryGetTargetRoom(data, constraint, out room)) {
            cost += e.AllocateToCost(e1, room);
          }
          break;

        case ConstraintType.GroupBy:
          if (TryGetSubjectEntity(data, constraint, out e1) && TryGetTargetEntity(data, constraint, out e2)) {
            cost += e.GroupByCost(e1, e2);
          }
          break;

        case ConstraintType.SameRoom:
          if (TryGetSubjectEntity(data, constraint, out e1) && TryGetTargetEntity(data, constraint, out e2)) {
            cost += e.SameRoomCost(e1, e2);
          }
          break;

        case ConstraintType.Adjacent:
          if (TryGetSubjectEntity(data, constraint, out e1) && TryGetTargetEntity(data, constraint, out e2)) {
            cost += e.AdjacentCost(e1, e2);
          }
          break;

        case ConstraintType.AwayFrom:
          if (TryGetSubjectEntity(data, constraint, out e1) && TryGetTargetEntity(data, constraint, out e2)) {
            cost += e.AwayFromCost(e1, e2);
          }
          break;

        default:
          throw new InvalidOperationException("Invalid constraint.");
        }
        //Console.WriteLine("type = {0}, cost = {1}", constraintType, cost);
      }
      cost += data.Rooms.Sum(r => e.RoomUsageCost(r.ID));

      return cost;
    }

    private static bool TryGetSubjectEntity(OfficeSpaceData data, Constraint constraint, out string entity) {
      entity = constraint.Subject;
      if (!data.EntitiesByName.ContainsKey(constraint.Subject)) {
        Console.WriteLine(String.Format("*** Invalid subject entity [{0}] in row {1}", entity, constraint));
        return false;
      }
      return true;
    }

    private static bool TryGetTargetEntity(OfficeSpaceData data, Constraint constraint, out string entity) {
      entity = constraint.Target;
      if (!data.EntitiesByName.ContainsKey(entity)) {
        Console.WriteLine(String.Format("*** Invalid target entity [{0}] in row {1}", entity, constraint));
        return false;
      }
      return true;
    }

    private static bool TryGetTargetRoom(OfficeSpaceData data, Constraint constraint, out string room) {
      room = constraint.Target;
      if (!data.RoomsByID.ContainsKey(room)) {
        Console.WriteLine(String.Format("*** Invalid target room [{0}] in row {1}", room, constraint));
        return false;
      }
      return true;
    }
  }
}

Okay. Main() is expecting a path to an XML file. Assuming we get it, Run() creates a new OfficeSpaceData and fills it in with the data from the XML file. Then we call the Heuristic method, which creates a dictionary that maps entities to rooms: this constitutes a solution to an office allocation problem. My heuristic is stupid: iterate through the rooms and assign them to the rooms sequentially, cycling if we run out of rooms. This heuristic completely ignores the constraints! The last part of the problem is to evaluate the quality of the solution. In order to do this we’ll need to 1) evaluate the amount of wasted and overused space, 2) calculate penalties for constraint violation. We’ll define yet another class (SolutionEvaluator) to help to this. In the code above you see how it’s used: we iterate over each constraint, switching on the ConstraintType. We send in the right arguments to SolutionEvaluator methods depending on the constraint type. The SolutionEvaluator methods return the penalty (if any) for the constraint:

  // Calculates the objective value for a solution, incorporating penalties for soft constraints.
  class SolutionEvaluator {
    private IDictionary<string, string> entityToRoom;
    private IDictionary<ConstraintType, double> penalties;
    private OfficeSpaceData data;

    public SolutionEvaluator(OfficeSpaceData data, IDictionary<string, string> entityToRoom, IDictionary<ConstraintType, double> penalties) {
      this.data = data;
      this.penalties = penalties;
      this.entityToRoom = entityToRoom;
    }

    public double RoomUsageCost(string r) {
      double totalSpaceUsed = entityToRoom.Where(p => p.Value == r).Sum(p => data.EntitiesByName[p.Key].Space);
      double roomSize = data.RoomsByID[r].Size;
      return (roomSize > totalSpaceUsed) ? (roomSize - totalSpaceUsed) : 2 * (totalSpaceUsed - roomSize);
    }

    public double AllocateToCost(string e, string r) {
      return entityToRoom[e] == r ? 0 : penalties[ConstraintType.AllocateTo];
    }

    public double NoSharingCost(string e) {
      string room = entityToRoom[e];
      return entityToRoom.Where(p => p.Value == room).Count() == 1 ? 0 : penalties[ConstraintType.NoSharing];
    }

    public double AwayFromCost(string e1, string e2) {
      var e1Rooms = data.RoomsByID[entityToRoom[e1]].Nearby;
      return EvaluateInList(e1Rooms, e2, penalties[ConstraintType.AwayFrom], true);
    }

    public double AdjacentCost(string e1, string e2) {
      var e1Rooms = data.RoomsByID[entityToRoom[e1]].Adjacent;
      return EvaluateInList(e1Rooms, e2, penalties[ConstraintType.Adjacent], false);
    }

    public double GroupByCost(string e1, string e2) {
      var e1Rooms = data.RoomsByID[entityToRoom[e1]].Nearby;
      return EvaluateInList(e1Rooms, e2, penalties[ConstraintType.GroupBy], false);
    }

    public double SameRoomCost(string e1, string e2) {
      string r1 = entityToRoom[e1];
      string r2 = entityToRoom[e2];
      return r1 == r2 ? 0 : penalties[ConstraintType.SameRoom];
    }

    private double EvaluateInList(IEnumerable<Room> e1Rooms, string e2, double penalty, bool penalizeInList) {
      string r2 = entityToRoom[e2];
      if (e1Rooms.FirstOrDefault(r => r.ID == r2) != null) {
        return penalizeInList ? penalty : 0;
      }
      else {
        return penalizeInList ? 0 : penalty;
      }
    }
  }

The rules are pretty simple, so checking most of them takes only a line or two of code. Nearby, Adjacent, and GroupBy, AwayFrom all deal with checking to see if an assigned room is in (or out of) a list. So I wrote a helper method called EvaluateInList to avoid unnecessary code duplication. Putting it all together, if I run the program against the sample data, I see the cost for my solution:

c:\OfficeSpace\bin\Release>OfficeSpace.exe \temp\OfficeSpace\data\nott_data\sample.xml
FILE: \temp\OfficeSpace\data\nott_data\sample.xml
COST      = 186.36

That was a lot of code without much explanation, but I hope it was worth it. At this point you can write a more sensible Heuristic method and see how you do. Getting all this out of the way will let us focus on building a Solver Foundation model for this problem, which we’ll do in the next post.

Author: natebrix

Follow me on twitter at @natebrix.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s