In (1) a problem is discussed where an optimization model can help us.
We want to set up \(N\) business dinners attended by customers and suppliers with the following peculiarities:
- there are \(T\) tables,
- we need to seat \(C\) customers and \(S\) suppliers,
- at most \(Maxc\) customers and at most \(Maxs\) suppliers can sit at a single table,
- a customer \(c\) and supplier \(s\) must sit at the same table exactly once,
- two suppliers can only sit at the same table at most once
We want to minimize the number of dinners \(N\) we need to organize such that all these constraints are met.
Restaurant Flo in Barcelona, Spain [link]
The data
We use the example data from (1):
- 6 customers, 5 suppliers
- \(Maxc=3\), \(Maxs=2\)
- 2 tables
A (non-optimal) solution with 8 dinner rounds is given:
An MINLP model
We start with our central binary variable \(x_{i,t,n}\in\{0,1\}\) indicating if person \(i\) sits at table \(t\) in dinner round \(n\). With this we can develop a Mixed Integer Nonlinear Programming model:
\[\boxed{\begin{align}
\min\>&\sum_n y_n && && \text{minimize number of dinner rounds} \\
&\sum_t x_{i,t,n} \le 1 &&\forall i,n&&\text{sit at one table}\\
&\sum_s x_{s,t,n} \le Maxs &&\forall t,n&&\text{limit suppliers at table}\\
&\sum_c x_{c,t,n} \le Maxc &&\forall t,n&&\text{limit customers at table}\\
* \> &\sum_{t,n} x_{c,t,n}\cdot x_{s,t,n} = 1&&\forall c,s&&\text{customers and suppliers meet exactly once}\\
* \> &\sum_{t,n} x_{s1,t,n} \cdot x_{s2,t,n} \le 1&&\forall s1\ne s2&&\text{suppliers sit at most once at the same table}\\
* \> &y_n = \max_{i,t} \{x_{i,t,n}\} && \forall n &&\text{we need a dinner round}\\
&x_{i,t,n},y_n \in \{0,1\}
\end{align}}\] |
The equations marked with a * are nonlinear. The variable \(y_n\) indicates whether we need a dinner round \(n\).
A non-convex MIQCP model
To implement the above MINLP we can apply a few modifications:
- When we checked if suppliers \(s1,s2\) are at the same table, we can skip checking \(s2,s1\). Hence we only need to check suppliers \(s1,s2\) with \(s1<s2\). This saves us a number of equations.
- The constraint \(y_n = \max_{i,t} \{x_{i,t,n}\}\) can be written as a collection of inequalities \(y_n \ge x_{i,t,n}\) (we use the objective to help us drive down \(y_n\)).
- Optionally we can require that \(y_n \ge y_{n+1}\), This makes the solutions more readable (we have the used dinner rounds first) but also reduces symmetry.
- There are more symmetries in the model we can try to alleviate. E.g. order dinner rounds and order tables by some statistic.
We are now only left with quadratic terms in the constraints. Such a model is called a Mixed Integer Quadratically Constrained Problem (MIQCP). Although solvers like Cplex and Gurobi can solve convex MIQCPs, unfortunately this problem is non-convex. That means we need a global solver. The model below can be solved quickly with the solvers GloMIQO, Antigone and Baron. Interestingly, the global solver Couenne is struggling mightily with this model: it has troubles finding a feasible solution.
A linearized MIP model
The binary multiplication can be linearized using a standard reformulation:
\[\begin{matrix}
\boxed{\begin{align}&z=x\cdot y\\
&x,y,z\in \{0,1\}\end{align}}&\Longleftrightarrow&
\boxed{\begin{align}&z \le x\\&z \le y\\&z\ge x+y-1\\&x,y,z\in \{0,1\}\end{align}}
\end{matrix}\] |
Note that we need to apply this reformulation on the individual product terms in the two quadratic constraints. This means we need to introduce a number of additional variables in the model.
We can simplify the binary multiplication further in the supplier case: we only need to make sure that \(z \ge x+y-1\). That will save us some constraints. The reason hat we can do this is that we have an inequality of the form \(\sum_i x_i \cdot y_i \le 1\) so we are only interested in the product terms that are forced to be one. Hence we have the two different cases:
\[\begin{matrix} \displaystyle\sum_i x_i\cdot y_i = 1 & \Longrightarrow &
\boxed{\begin{align} &z_i \le x_i\\ &z_i \le y_i\\&z_i \ge x_i+y_i-1\\&\sum_i z_i=1\end{align}}\\
\displaystyle\sum_i x_i\cdot y_i \le 1 & \Longrightarrow &
\boxed{\begin{align}&z_i \ge x_i+y_i-1\\&\sum_i z_i\le 1 \end{align}}\end{matrix}\]
|
I should note that I assume \(x_i,y_i,z_i \in \{0,1\}\). It is nice to see both constructs next to each other in one small model. The complete linearized model can look like:
This model can now be solved with any MIP solver, including Cplex and Gurobi which were out of the picture for the MIQCP model formulation.
An optimal solution with 3 dinner rounds is:
References
- Alejandra Estanislao, Frédéric Meunier, “A Business Dinner Problem”, Journal of Combinatorial Mathematics and Combinatorial Computing, 97, 173-188, 2016. [link]
