Planning office moves with Solver Foundation: Part IV

The previous three posts in this series introduced all the components necessary to describe and model office space allocation problems. Here’s the payoff: a C# program that uses the components to solve problems. The important classes are:

  • OfficeSpaceData. This class stores information about the entities, rooms, and constraints (e.g. “two entities should share a room”) that make up a problem instance.
  • OfficeSpaceModelSimple. This class encapsulates a Solver Foundation model for the office space allocation problem. Callers invoke methods to describe constraints, and then an Allocate() method to solve the model.
  • Solution. This class represents a solution for a problem instance, in particular the room assignment for each entity in the model. A Solution instance is returned by the OfficeSpaceModelSimple.Allocate() method.

Let’s modify the test program from this post to use all three components. The complete test code is below. Note the following:

  • The Main method passes the XML filename, schema filename, and time limit to Run(). (Here is a link to some sample problems.)
  • Run() does the following:
    • Creates a new OfficeSpaceData which reads the data,
    • Establishes the penalties for constraint violation,
    • Creates a new OfficeSpaceModelSimple, passing in the penalty weights,
    • Calls the Fill() method (see below),
    • Solves the model,
    • Reports the results (see below).
  • Fill() scans through the constraints in the OfficeSpaceData object and calls the right methods on OfficeSpaceModelSimple. Remember that constraints have an “IsHard” property that specifies whether a constraint is strictly enforced, but that OfficeSpaceModelSimple currently ignores this setting and treats all constraints as “hard”.
  • The Report() method prints out the results in an easy-to-understand format. The assignment is read from the Solution object. We also manually calculate the wastage and overuse penalties from the assignment. Finally, we call an Evaluate() method that loops over all the constraints and uses the SolutionEvaluator class to calculate the cost of the solution. This calculation is redundant it is supposed to be exactly the same as the goal in our model! I have included this redundant calculation on purpose to check that the model is indeed solving the right problem.
using System;  
using System.Collections.Generic;
using System.IO;
using System.Linq;  
using System.Text;  

namespace Samples.OfficeSpace {
  public class Program {

    private bool printAssignment = true;
    private bool includeDefaultConstraints = true;

    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");

      int seconds = args.Length > 1 ? Int32.Parse(args[1]) : 10;
      Program p = new Program();
      p.Run(fileName, schemaFileName, TimeSpan.FromSeconds(seconds));
    }

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

      OfficeSpaceData data = new OfficeSpaceData();
      data.ReadFromFile(fileName, schemaFilename);

      Dictionary<ConstraintType, double> penalties = GetPenaltyWeights();
      OfficeSpaceModelSimple model = new OfficeSpaceModelSimple(penalties);
      model.SolveTimeLimit = limit;
      string modelName = fileName.Substring(0, fileName.IndexOf('.'));
      Fill(modelName, data, model);
      Solution solution = model.Allocate();
      Report(data, penalties, solution);
    }
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 void Fill(string modelName, OfficeSpaceData data, OfficeSpaceModelSimple model) { model.InitializeModel(modelName); model.SetSizeBinding(data.Rooms, "Size", "ID"); model.SetSpaceBinding(data.Entities, "Space", "Name"); if (includeDefaultConstraints) { model.Wastage(); model.Overuse(); } Console.WriteLine("PROCESSING {0} CONSTRAINTS", data.Constraints.Count()); string e1, e2, room; foreach (var constraint in data.Constraints) { switch (constraint.Type) { case ConstraintType.NoSharing: if (TryGetSubjectEntity(data, constraint, out e1)) { model.NoSharing(constraint.IsHard, e1, data.EntityCount); } break; case ConstraintType.AllocateTo: if (TryGetSubjectEntity(data, constraint, out e1) && TryGetTargetRoom(data, constraint, out room)) { model.AllocateTo(constraint.IsHard, e1, room); } break; case ConstraintType.GroupBy: if (TryGetSubjectEntity(data, constraint, out e1) && TryGetTargetEntity(data, constraint, out e2)) { model.GroupBy(constraint.IsHard, data.Rooms, e1, e2); } break; case ConstraintType.SameRoom: if (TryGetSubjectEntity(data, constraint, out e1) && TryGetTargetEntity(data, constraint, out e2)) { model.SameRoom(constraint.IsHard, e1, e2); } break; case ConstraintType.Adjacent: if (TryGetSubjectEntity(data, constraint, out e1) && TryGetTargetEntity(data, constraint, out e2)) { model.Adjacent(constraint.IsHard, data.Rooms, e1, e2); } break; case ConstraintType.AwayFrom: if (TryGetSubjectEntity(data, constraint, out e1) && TryGetTargetEntity(data, constraint, out e2)) { model.AwayFrom(constraint.IsHard, data.Rooms, e1, e2); } break; default: throw new InvalidOperationException("Invalid constraint."); } } } private void Report(OfficeSpaceData data, Dictionary<ConstraintType, double> penalties, Solution solution) { ReportSection("WEIGHTS:"); foreach (var pair in penalties) { Console.WriteLine("{0}\t{1}", pair.Key, pair.Value); } if (solution.Quality.StartsWith("infeasible", StringComparison.OrdinalIgnoreCase)) { Console.WriteLine("*** MODEL IS INFEASIBLE ***"); return; } if (printAssignment) { ReportSection("ASSIGNMENT:"); Console.WriteLine("ENTITY ROOM"); foreach (var assignment in solution.EntityToRoom.OrderBy(p => p.Key)) { Console.WriteLine("{0} {1}", assignment.Key, assignment.Value); } } ReportSection("USAGE TERMS:"); foreach (var entry in solution.Usage) { string r = entry.Item1; Console.WriteLine("{0} = {1:f4}\tRoom = {2}\tEntity = {3} (count = {4})", r, entry.Item2, data.RoomsByID[r].Size, solution.EntityToRoom.Where(t => t.Value == r).Sum(t => data.EntitiesByName[t.Key].Space), solution.EntityCount(r) ); } Console.WriteLine("TOTAL USAGE = " + solution.Usage.Sum(u => u.Item2)); ReportSection("SUMMARY:"); Console.WriteLine("OBJECTIVE = " + solution.Objective); Console.WriteLine("COST = " + Evaluate(data, penalties, solution.EntityToRoom)); } private static void ReportSection(string label) { Console.WriteLine(Environment.NewLine + label); Console.WriteLine(new string('-', label.Length)); } 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."); } } 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; } } }

Here is the output of the program for my sample problem (you should be able to confirm this by downloading the Express edition of Solver Foundation). As you can see, the optimal cost is 62. If you look at the assignment, the “Form” team is allocated to the first floor and the “Function” team is allocated to the second floor. Also notice that some of the rooms on the first floor are unused! This is because the sample model has constraints that specify that teammates should be “nearby” each other, which means allocated to the same floor. Since this constraint is strictly enforced this effectively means that each team must be on a separate floor. If we did not have such a strict interpretation of the “nearby” constraints then perhaps we could find an allocation that had better space usage. In order to support soft constraints we will need to revisit the model class, which we will do in the next post.

c:\temp\OfficeSpace\bin\Release>OfficeSpace.exe \temp\data\nott_data\sample.xml
FILE: \temp\data\nott_data\sample.xml
PROCESSING 11 CONSTRAINTS
Optimize a model with 227 Rows, 326 Columns and 1853 NonZeros
Presolve removed 109 rows and 227 columns
Presolve time: 0.03s
Presolved: 118 Rows, 99 Columns, 845 Nonzeros
Objective GCD is 1
Found heuristic solution: objective 104.0000

Root relaxation: objective 2.401047e+01, 133 iterations, 0.00 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0    24.0105    0   41   104.0000    24.0105  76.9%     -    0s
     0     0    41.7082    0   33   104.0000    41.7082  59.9%     -    0s
     0     0    41.8302    0   40   104.0000    41.8302  59.8%     -    0s
     0     0    41.8302    0   37   104.0000    41.8302  59.8%     -    0s
H    0     0                         62.0000    41.8302  32.5%     -    0s
     0     0    47.5859    0   34    62.0000    47.5859  23.2%     -    0s
     0     0    47.5859    0   37    62.0000    47.5859  23.2%     -    0s
     0     0    47.5859    0   36    62.0000    47.5859  23.2%     -    0s
     0     0    47.5859    0   36    62.0000    47.5859  23.2%     -    0s
     0     2    47.5859    0   34    62.0000    47.5859  23.2%     -    0s

Cutting planes:
  Implied bound: 3
  MIR: 7

Explored 16 nodes (595 simplex iterations) in 0.11 seconds
Thread count was 2 (of 2 available processors)

Optimal solution found (tolerance 1.00e-04)
Best objective 6.2000000000e+01, best bound 6.2000000000e+01, gap 0.0%

WEIGHTS:
--------
Adjacent        10
AllocateTo      20
AwayFrom        10
NoSharing       50
SameRoom        10
GroupBy 11.18
Wastage 1
Overuse 2

ASSIGNMENT:
-----------
ENTITY ROOM
Alexander 102
Banksy 101
Christo 203
David 202
Einstein 201
Fabio 105
Galileo 202
Holmes 202
Icarus 103
Jian 202

USAGE TERMS:
------------
101 = 4.0000    Room = 8        Entity = 10 (count = 1)
102 = 18.0000   Room = 6        Entity = 15 (count = 1)
103 = 2.0000    Room = 6        Entity = 4 (count = 1)
104 = 6.0000    Room = 6        Entity = 0 (count = 0)
106 = 6.0000    Room = 6        Entity = 0 (count = 0)
201 = 18.0000   Room = 6        Entity = 15 (count = 1)
202 = 6.0000    Room = 22       Entity = 25 (count = 4)
203 = 2.0000    Room = 14       Entity = 15 (count = 1)
TOTAL USAGE = 62

SUMMARY:
--------
OBJECTIVE = 62
COST      = 62

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