Planning office moves with Solver Foundation: Part V

It’s time to finish our mixed integer programming modeling sample for office space allocation problems. In a previous post in this series I presented a Solver Foundation model that enforces constraints for office space problems, optimizing for space allocation.  I initially assumed that we wanted to strictly enforce all of the constraints in the model, but that’s not always what we want to do. For example, I may have constraints that say “Banksy and Christo need to be located near each other” or “Christo and Fabio need to be located away from each other”. With a number of these constraints we may quickly get into a situation where we cannot find an assignment that satisfies all of them: my model may be infeasible. Moreover, sometimes these constraints actually represent preferences rather than conditions that must hold at all costs. We can instead model these conditions as “soft constraints”, meaning that we allow the constraint to be violated but add a penalty to the goal to compensate.

If you have a model that uses hard constraints it is usually not too hard to change it into a model that uses soft constraints. Usually the trick is to introduce auxiliary boolean (0-1) decision variables and add terms to the hard constraints. When we do this we want to make sure that:

  • The constraint will always hold, but…
  • If the condition represented in the original hard constraint does not hold then the auxiliary decision gets the value 1.

Then we can stick the auxiliary decision in the goal and multiply it by a constant: this represents the penalty for violating the soft constraint. Our model represents six different kinds of constraints. Rather than going through them all, I will go through the “allocate to” and “same room” constraints to give you an idea for how it works.

Allocate To: if we want to make sure that entity e is assigned to room r, the hard constraint is simply allocate[e, r] == 1. To form the soft constraint we add a new decision “d” and add the constraint d == 1 – allocate[e, r].  The decision d goes into the goal as a penalty term: if the hard constraint is violated then allocate[e,r] == 0 and d == 1.  We can modify the OfficeSpaceModel.AllocateTo (from this post) as follows:

    public void AllocateTo(bool hard, string e, string r) {
      CheckEntities(e);
      int id = ++constraintCount[ConstraintType.AllocateTo];
      if (hard) {
        model.AddConstraint("alloc_" + id, allocate[e, r] == 1);
      }
      else {
        Decision d = new Decision(ZeroOne, "d_alloc_" + id);
        model.AddDecision(d);
        model.AddConstraint("i_alloc_" + id, d == 1 - allocate[e, r]);
        penaltyTerms[ConstraintType.AllocateTo].Add(d);
      }
    }

Same Room: the “hard” version of the constraint ensures that the rows of the allocate decision corresponding to two entities e1, e2 are identical. In the “soft” version of the constraint we introduce one auxiliary decision d_r for each room. We want the value of such a decision to be 1 if the values of allocate are different, i.e. the absolute value of the difference is nonzero. We cannot directly model an absolute value so we use a modeling trick instead: we add lower and upper bounds to the constraint involving d_r. These bounds force d_r = 1 if and only if the entries of allocate are different.

    public void SameRoom(bool hard, string e1, string e2) {
      CheckEntities(e1, e2);
      int id = ++constraintCount[ConstraintType.SameRoom];
      if (hard) {
        model.AddConstraint("same_" + id,
          Model.ForEach(roomsSet, r => allocate[e1, r] - allocate[e2, r] == 0)
          );
      }
      else {
        // See equations 10 and 11.
        Decision d = new Decision(ZeroOne, "d_same_" + id); // indicator
        Decision d_r = new Decision(ZeroOne, "d_same_r_" + id, roomsSet); // per-room indicator
        model.AddDecisions(d, d_r);
        model.AddConstraint("same_" + id,
          Model.ForEach(roomsSet, r => 2 * d_r[r] - 1 <= allocate[e1, r] - allocate[e2, r] <= 1 - eps + eps * d_r[r])
          );
        model.AddConstraint("i_same_" + id, d == Model.Sum(Model.ForEach(roomsSet, r => d_r[r])));
        penaltyTerms[ConstraintType.SameRoom].Add(d);
      }
    }

The soft constraint versions of the other constraint types are similar so I will not review them in detail here. Download the complete solution (including the code from all posts in this series here.)

We’ve replicated everything in the Landa-Silva/Ülker paper that was our original inspiration. Let’s see how the code performs. First, let’s re-solve our sample problem with soft constraints. Here is the last part of the output:

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

PENALTY TERMS:
--------------
d_grp_21 = 1
d_grp_31 = 1

USAGE TERMS:
------------
101 = 2.0000    Room = 8        Entity = 9 (count = 1)
103 = 2.0000    Room = 6        Entity = 4 (count = 1)
105 = 2.0000    Room = 6        Entity = 4 (count = 1)
201 = 18.0000   Room = 6        Entity = 15 (count = 1)
202 = 6.0000    Room = 22       Entity = 25 (count = 2)
203 = 2.0000    Room = 14       Entity = 15 (count = 1)
TOTAL USAGE = 31.9999999999983

SUMMARY:
--------
OBJECTIVE = 54.3600000000084
COST      = 54.36
COST      = 186.36

If you compare this to the output from the hard constraint solution, you will notice that the cost is 54.36 compared to 62. This happens because here the “group by” constraints that request the Form and Function teams to be on the same floor were violated (Icarus and Fabio are on Floor 1).

The code seems to do quite well for larger problems too. In particular, the code improves on the best known solution for largest sample problem (“notta”). The previously best-known objective value was 379.88, but in 6 minutes we obtain a solution with objective value 317.06:

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

     0     0   178.0506    0  349  4437.5000   178.0506  96.0%     -  148s
H    0     0                        935.1500   178.0506  81.0%     -  152s
H    0     0                        610.2700   178.0506  70.8%     -  159s
H    0     0                        341.6600   178.0506  47.9%     -  181s
     0     0   217.5068    0  334   341.6600   217.5068  36.3%     -  202s
H    0     0                        320.6600   217.5068  32.2%     -  220s
     0     0   221.5996    0  394   320.6600   221.5996  30.9%     -  234s
     0     0   225.7156    0  389   320.6600   225.7156  29.6%     -  263s
H    0     0                        317.0600   225.7156  28.8%     -  277s
     0     0   229.1693    0  390   317.0600   229.1693  27.7%     -  292s
     0     0   229.8062    0  395   317.0600   229.8062  27.5%     -  306s
     0     0   230.4912    0  406   317.0600   230.4912  27.3%     -  322s
     0     0   231.8208    0  396   317.0600   231.8208  26.9%     -  337s
     0     0   232.7833    0  395   317.0600   232.7833  26.6%     -  345s

Since this is a very large model in order to run this problem you will need the enterprise version of Solver Foundation. If you are a professor, student, or researcher and your academic institution has a Developer AA subscription then you will be able to download the unthrottled Enterprise edition of Solver Foundation (and tons of other stuff) at no cost through the MSDNAA program.

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