Planning office moves with Solver Foundation: Part I

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.

Converting an Access DB to XML using C#

I recently needed to import an Access database into a C# program for a sample that I will be blogging about soon. My objective was to convert the data into a more convenient form for use with my “real” application. Nothing here will be very cutting edge! A quick and dirty way to get the job done seemed to be to read the data into a DataSet and export it to XML. Access MDB files can be read using the Jet OLDB provider with OleDbConnection. Once the connection is established, the GetOleDbSchemaTable method can be used to get the table names. Then each table can be read using a select. Writing the data out to XML is easy using the built-in DataSet.WriteToXml() method. I also write out the schema file so that the columns will have the correct types when I read the data back in.

One last hitch: in .Net 4/VS2010 the OLEDB component works only with a 32-bit build. So change the Platform target in the Project properties as follows:

Here’s the code. I’ve made even less of an effort than usual to make the code “production quality”, but note that a couple of the classes I use are IDisposable so I’m taking care to wrap them in a “using” block.

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

// None of this is foolproof...caveat emptor.
namespace AccessToDataSet {
  class Program {
    static void Main(string[] args) {
      if (args.Length == 0 || !args[0].EndsWith(".mdb", StringComparison.InvariantCultureIgnoreCase)) {
        Console.WriteLine("Please specify the path to an MDB file.");
        return;
      }

      DataSet dataSet = new DataSet();
      using (var conn = new OleDbConnection(@"Provider=Microsoft.JET.OLEDB.4.0;" + @"data source=" + args[0])) {
        conn.Open();
        // Retrieve the schema
        DataTable schemaTable = conn.GetOleDbSchemaTable(OleDbSchemaGuid.Tables, new object[] { null, null, null, "TABLE" });
        // Fill the DataTables.
        foreach (DataRow dataTableRow in schemaTable.Rows) {
          string tableName = dataTableRow["Table_Name"].ToString();
          // I seem to get an extra table starting with ~. I can't seem to screen it out based on information in schemaTable,
          // hence this hacky check.
          if (!tableName.StartsWith("~", StringComparison.InvariantCultureIgnoreCase)) {
            FillTable(dataSet, conn, tableName);
          }
        }
      }

      string name = args[0].ToLowerInvariant();
      dataSet.WriteXmlSchema(name.Replace(".mdb", ".schema.xml"));
      dataSet.WriteXml(name.Replace(".mdb", ".xml"));
    }

    private static void FillTable(DataSet dataSet, OleDbConnection conn, string tableName) {
      DataTable dataTable = dataSet.Tables.Add(tableName);
      using (OleDbCommand readRows = new OleDbCommand("SELECT * from " + tableName, conn)) {
        OleDbDataAdapter adapter = new OleDbDataAdapter(readRows);
        adapter.Fill(dataTable);
      }
    }
  }
}

Microsoft Solver Foundation: blogs and resources

Updated 5/29/2012,7/20/2010, 4/14/2012

On 5/25/2012, the Solver Foundation team announced that there will be no more standalone releases of the product. You may consider looking into other modeling frameworks or solvers to meet your needs.

For posterity, here are some general resources:

• Solver Foundation team blog [link]
• Solver Foundation MSDN forum [link]
• How to download and use Solver Foundation Samples [link]
• OML tutorial by Erwin Kalvalagen [link]
• My Solver Foundation blog posts [link]

Here are some of my favorite Solver Foundation posts:

• Simple C# introduction (production planning) [link]
• Project scheduling [link]
• Two-way data binding (with LINQ) [link]
• Traveling salesman [link]
• Solver Foundation and LINQ to SQL [link]
• Interior point solver [link]
• Unconstrained nonlinear solver [link]
• Using the Term class (with C#) [link]
• Knapsack (with LINQ) [link]
• Set covering (with OML) [link]