Planning office moves with Solver Foundation: Part III

(Previous posts in this series introduced the office space allocation problem and built data structures to represent and evaluate a problem instance.)

Let’s build a simple (but complete) model for the office allocation problem. I will encapsulate the Solver Foundation code for the model in a class called OfficeSpaceModel. Our program can then use this class without knowing anything about the model formulation (or that Solver Foundation is even being used at all). I will work through the components of OfficeSpaceModel bit by bit.

From the previous post you know that we’re trying to find an assignment of entities to rooms. When soft constraints are violated, or when the amount of space allocated to a room does not match capacity, we add a penalty to our goal. From this information alone we can deduce most of the data members for the class, including:

  • Sets that represent entities and rooms.
  • A decision that indicates whether an entity is assigned to a room,
  • A decision that indicates whether the entity space usage matches room capacity.

Here goes. (You’ll need the code from the previous posts.)

using System;
using System.Collections.Generic;
using System.Data;
using System.Linq;
using System.Text;
using Microsoft.SolverFoundation.Common;
using Microsoft.SolverFoundation.Services;
// be sure to add a reference to the GurobiPlugin.dll included in Program Files\Solver Foundation\Plugins.
using SolverFoundation.Plugin.Gurobi;
namespace Samples.OfficeSpace {

  // The model.
  class OfficeSpaceModel {
    private SolverContext context; // the context.
    private Model model; // the model we're building.
    private Dictionary<ConstraintType, int> constraintCount; // number of constraints of each type.
    private IDictionary<ConstraintType, double> penaltyWeight; // the penalty weights (from last post).
    private Set entitiesSet, roomsSet; // Sets.
    private Parameter size, space; // room size, entity space.
    private Decision allocate; // allocate[e, r] == 1 means r -> e.
    private Decision usage; // usage penalty for each room.
    private Domain ZeroOne = Domain.IntegerRange(Rational.Zero, Rational.One); // for convenience.

    public TimeSpan SolveTimeLimit { get; set; } // how long to keep going.

    public IDictionary<ConstraintType, double> PenaltyWeight {
      get { return penaltyWeight; }
    }


    public OfficeSpaceModel(IDictionary<ConstraintType, double> weights) {
      SolveTimeLimit = TimeSpan.FromSeconds(10);
      var allValues = (ConstraintType[])Enum.GetValues(typeof(ConstraintType));
      constraintCount = allValues.ToDictionary(t => t, t => 0);
      penaltyWeight = weights;
    }
}

(If you’re following along with the Landa-Silva/Ulker paper, “allocate” corresponds to the “delta” variable.) The constructor sets an initial time limit, initializes all constraint counts to zero, and initializes the penalty weights. Now let’s write a method that initializes the parts of the model that are invariant with respect to the input data. In particular: the SolverContext, the Model, and the decisions. Also one very important (but easy to overlook) constraint: each entity must be assigned to a room. This means that the row sums in “allocate” must equal one:

    public void InitializeModel(string name) {
      context = SolverContext.GetContext();
      context.ClearModel();
      model = context.CreateModel();
      model.Name = name;

      entitiesSet = new Set(Domain.Any, "entities");
      roomsSet = new Set(Domain.Any, "rooms");

      allocate = new Decision(ZeroOne, "allocate", entitiesSet, roomsSet);
      usage = new Decision(Domain.RealNonnegative, "usage", roomsSet);
      model.AddDecisions(allocate, usage);

      // Allocation
      model.AddConstraint("allocation",
        Model.ForEach(entitiesSet, e => Model.Sum(Model.ForEach(roomsSet, r => allocate[e, r])) == 1));
    }

We have two parameters in our model: one for the room size and another for entity space requirements. Let’s add methods that allow the user to establish the data binding. Notice that the method is not limited to the OfficeSpaceData class we defined last time – the caller can use any IEnumerable they want.

    public void SetSizeBinding<T>(IEnumerable<T> roomData, string valueField, string indexField) {
      size = new Parameter(Domain.Real, "size", roomsSet);
      size.SetBinding(roomData, valueField, indexField);
      model.AddParameters(size);
    }

    public void SetSpaceBinding<T>(IEnumerable<T> entityData, string valueField, string indexField) {
      space = new Parameter(Domain.Real, "spaceReq", entitiesSet);
      space.SetBinding(entityData, valueField, indexField);
      model.AddParameters(space);
    }

Now we’re into the heart of the model: specifying goals and constraints. Let’s focus on the goal first. The goal has three parts: space overuse cost, space wastage cost, and penalties for violating soft constraints. For now, let’s forget about soft constraints and assume that all constraints must be strictly adhered to (“hard”). We will revisit soft constraints in a future post.

Wastage and Overuse: The paper (equation 20) says to look at each room and take the maximum of (wastage, 2 * overuse). We cannot use “Max” directly in our SFS model, so we will instead use the trick from this blog post: introduce one auxiliary variable for each room (“usage”) and add constraints involving these variables, our parameters, and the wastage/overuse penalites:

    #region Overuse and Wastage

    public void Wastage() {
      model.AddConstraint("wastage",
        Model.ForEach(roomsSet, r =>
          PenaltyWeight[ConstraintType.Wastage] * (size[r] - Model.Sum(Model.ForEach(entitiesSet, e => space[e] * allocate[e, r]))) <= usage[r]
        ));
    }

    public void Overuse() {
      model.AddConstraint("overuse",
        Model.ForEach(roomsSet, r =>
        penaltyWeight[ConstraintType.Overuse] * (Model.Sum(Model.ForEach(entitiesSet, e => space[e] * allocate[e, r])) - size[r]) <= usage[r]
        ));
    }
    #endregion

In order to add the Wastage and Overuse constraints to the model, the caller simply needs to call these methods. We will now add methods for the other constraints we talked about in the first post.

Allocate To: this is easy – just force allocate[e, r] to be 1. I am including an unnecessary “hard” argument to the method so that in a future post I can introduce soft constraints without messing up the calling code. (See equation (2) in the paper.)

    #region AllocateTo

    public void AllocateTo(bool hard, string e, string r) {
      CheckEntities(e);
      int id = ++constraintCount[ConstraintType.AllocateTo];
      model.AddConstraint("alloc_" + id, allocate[e, r] == 1);
    }
    #endregion

This method relies on a utility routine to make sure that the data is OK.

    #region Utilities
    private void CheckEntities(params string[] names) {
      foreach (string name in names) {
        if (String.IsNullOrEmpty(name)) {
          throw new ArgumentNullException("names");
        }
      }
    }

    private void CheckRooms(params string[] names) {
      foreach (string name in names) {
        if (String.IsNullOrEmpty(name)) {
          throw new ArgumentNullException("names");
        }
      }
    }
    #endregion

Same Room: In order to force two entities to share a room we just need to make sure that the values of the “allocate” rows corresponding to the entities always match. That’s easily done with Model.Foreach: (see equation (3))

    #region SameRoom

    public void SameRoom(bool hard, string e1, string e2) {
      CheckEntities(e1, e2);
      int id = ++constraintCount[ConstraintType.SameRoom];
      model.AddConstraint("same_" + id,
        Model.ForEach(roomsSet, r => allocate[e1, r] == allocate[e2, r])
        );
    }
    #endregion

No Sharing: Here we have a presumably important entity who is not supposed to share rooms with anyone else. Equivalently, if allocate[e, r] == 1, then the column sum is 1. If the entity is not assigned to the room (allocate[e, r] == 0)…who cares.  In a mixed integer model we can’t directly include an implication (an “if”), but we can fake it: (see equation (5))

    #region No Sharing

    public void NoSharing(bool hard, string e, int entityCount) {
      int id = ++constraintCount[ConstraintType.NoSharing];
      model.AddConstraint("no_share_" + id,
        Model.ForEach(roomsSet, r =>
          allocate[e, r]
          <= Model.Sum(Model.ForEach(entitiesSet, e2 => allocate[e2, r]))
          <= entityCount - (entityCount - 1) * allocate[e, r]
        )
      );
    }

    #endregion

In the case where allocate[e, r] is 0, the inequality holds because the middle clause will sum to 1. In the case where allocate[e, r] is 1, the last clause equals 1 which forces the column sum to be 1 as desired. This technique of converting an implication into a linear constraint is a common one and is used in the remaining constraints.

Away From: Here we have two entities e1, e2 who should not be assigned to rooms that are near each other. Equivalently this means if allocate[e1, r] = 1 then allocate[e2, r2] must be 0 for all r2 nearby room r. Again we have an implication which we can fake (like we did with “no sharing”): (see equation (8))

    #region AwayFrom

    public void AwayFrom(bool hard, IEnumerable<Room> rooms, string e1, string e2) {
      CheckEntities(e1, e2);
      foreach (var room in rooms) {
        string r = room.ID;
        Term adjTerm = AwayFromNearTerm(e2, r, room.Nearby);
        int id = ++constraintCount[ConstraintType.AwayFrom];
        model.AddConstraint("away_" + id,
          0 <= adjTerm <= 1 - allocate[e1, r]
          );
      }
    }

    private Term AwayFromNearTerm(string e2, string r, IEnumerable<Room> nearbyRooms) {
      CheckRooms(r);
      SumTermBuilder b = new SumTermBuilder(10);
      bool any = false; // note: this should always end up true since a room is considered to be near to itself.
      foreach (var nearbyRoom in nearbyRooms) {
        any = true;
        CheckEntities(nearbyRoom.ID);
        b.Add(allocate[e2, nearbyRoom.ID]);
      }
      return any ? b.ToTerm() : (Term)Rational.Zero;
    }
    #endregion

We need to add up an unknown number of terms so I have used the SumTermBuilder class for performance.

Adjacency and Group By: The adjacency constraints specifies that two entities e1, e2 must be located in adjacent rooms. Equivalently: if allocate[e1, r] = 1 then the sum of allocate[e2, r2] for all rooms r2 adjacent to r must be 1. Therefore we need to add constraints that represent this implication for each room. The constraint creation is captured in InSameSet, which has some extra arguments so it can be re-used. (see equation (6))

    #region Adjacent

    public void Adjacent(bool hard, IEnumerable<Room> rooms, string e1, string e2) {
      CheckEntities(e1, e2);
      foreach (var room in rooms) {
        InSameSet(ConstraintType.Adjacent, e1, e2, room.ID, room.Adjacent, "adj");
      }
    }

    private void InSameSet(ConstraintType type, string e1, string e2, string r, IEnumerable<Room> adjRooms, string prefix) {
      CheckRooms(r);
      int id = ++constraintCount[type];
      SumTermBuilder b = new SumTermBuilder(10);
      bool any = false; // should always end up true: rooms are considered to be adjacent to themselves.
      foreach (var adjRoom in adjRooms) {
        any = true;
        CheckEntities(adjRoom.ID);
        b.Add(allocate[e2, adjRoom.ID]);
      }
      if (any) {
        model.AddConstraint(prefix + id, allocate[e1, r] <= b.ToTerm() <= 1);
      }
    }

    #endregion

The “group by” constraint is exactly the same, except we are dealing with the list of nearby rooms, rather than the list of adjacent rooms. (see equation (7))

    #region GroupBy

    public void GroupBy(bool hard, IEnumerable<Room> rooms, string e1, string e2) {
      CheckEntities(e1, e2);
      foreach (var room in rooms) {
        InSameSet(ConstraintType.GroupBy, e1, e2, room.ID, room.Nearby, "grp");
      }
    }

    #endregion

Now a user of the class can express any of the constraints we want, and all that is left is a method to solve the model. This method adds the goal (using the “usage” decision we defined earlier), creates a directive to use the Gurobi solver, and solves the model:

    public Solution Allocate() {
      model.AddGoal("goal", GoalKind.Minimize, Model.Sum(Model.ForEach(roomsSet, r => usage[r])));

      Directive dir = new GurobiDirective { OutputFlag = true, TimeLimit = (int)SolveTimeLimit.TotalMilliseconds };

      var solution = context.Solve(dir);

      var assignment = from t in allocate.GetValues()
                       where Convert.ToDouble(t[0]) > 0.01
                       select new Tuple<string, string>(t[1].ToString(), t[2].ToString());

      var usagePenalty = from values in usage.GetValues()
                         where Math.Abs((double)values[0]) > 0.01
                         select new Tuple<string, double>(values[1].ToString(), (double)values[0]);

      return new Solution(solution.Quality, solution.Goals.First().ToDouble(), assignment, usagePenalty);
    }

Once we solve the model, we save the following information:

  • The solution quality (because the problem might not even be feasible)!
  • The assignment of entities to rooms. This is extracted from the “allocate” decision using a simple LINQ query to pull out the nonzero entries.
  • The penalties for wastage or overuse, again using a LINQ query.

Here is the Solution data structure. We have also added a couple of methods to help users pull out results.

  // Output data.
  class Solution {
    public IDictionary<string, string> EntityToRoom { get; private set; }
    public double Objective { get; private set; }
    public IEnumerable<Tuple<string, double>> Usage { get; private set; }
    public string Quality { get; set; }

    public Solution(
      SolverQuality quality,
      double objective,
      IEnumerable<Tuple<string, string>> assignment,
      IEnumerable<Tuple<string, double>> usage
      ) {
      Quality = quality.ToString();
      Objective = objective;
      Usage = usage;
      EntityToRoom = assignment.ToDictionary(i => i.Item1 /* entity */, i => i.Item2 /* room */);
    }

    public int EntityCount(string room) {
      return EntityToRoom.Where(p => p.Value == room).Count();
    }

    public string GetRoom(string entity) {
      return EntityToRoom[entity];
    }
  }

In order to test out the class we will need to modify our test program from last time to create an OfficeSpaceModel instance and call the right methods using the data in OfficeSpaceData. We’ll take that on 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