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 - 1 <= allocate[e1, r] - allocate[e2, r] <= 1 - eps + eps * d_r)
);
model.AddConstraint("i_same_" + id, d == Model.Sum(Model.ForEach(roomsSet, r => d_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.