In http://www.improbable.com/2012/02/12/finding-an-optimal-seating-chart-for-a-wedding/ an interesting model is proposed about optimal seating arrangements for a wedding. Basically their model looks like (I hope I transcribed the mathematical model correctly):
I would probably formulate this slightly different. A linearization
is often formulated as:
Here the last condition can be dropped as we are maximizing the p’s anyway. In general I use these disaggregated versions directly instead of the aggregated versions used in model above.
So how would I write this down? Here is my attempt:
x.fx('g1','table1') = 1;
I renamed some of the sets and variables.
A further improvement is that we fix guest 1 to table 1. This reduces the symmetry in the model.
So which model performs better? Of course this is only one data set, so we need to be careful not to read to much into this, but here are the results with GAMS and Cplex 12.3:
|solution time||216 seconds |
(reported in paper: 2 seconds)
|iterations/nodes||3502605 iterations, 93385 nodes||6943 iterations, 180 nodes|
It looks like the performance of the original model is much slower than reported in the paper. I don’t know the reason for that, may be the GAMS model contained a few tricks not mentioned in the description of the mathematical model (may be related to symmetry when comparing guest j against guest k). Another reason may be that in the paper it is mentioned that some serious server hardware is used while I am running on one thread on a laptop.
Of course this model can also be formulated as a Constraint Programming model. In http://hakank.org/minizinc/wedding_optimal_chart.mzn a single integer variable Tables[guest] for each guest is used indicating the table number. Furthermore using CP constructs one can reduce the model to basically one block of equations:
forall(i in 1..n) (
In the MIP model we have to do a little bit more work!
Note that the CP formulation is probably incorrect w.r.t. to the minimum number of known people at a table (parameter b).
Update: The CP model is fixed. The advantage of using modeling languages is that other people can read the model. If this would be some C++ code I would not have bothered to try to understand it. Also it is often argued that a modeling language helps in maintaining models as fixes are easier to identify and implement than in a traditional programming language.