A Model with Semi-Integer variables

Not many times I encounter a model where I can use semi-integer variables. These are integer variables that are either zero or some value between LO and UP. I.e. x ∈ 0 ⋃ {LO,..,UP}.

The problem is as follows. We have N groups of people (the size of a group varies but is at least two) that we want to seat at M tables. Each table has a given capacity r. Finally we want no lonely people at a table: if a person sits at a table, there is at least one other member of his/her group at the table. Find the minimum number of tables needed.

One way of doing this:



Notes:

• The assignment variables x are semi-integer. It is forbidden to have a single member of a group at a table.
• The capacity constraint reduces the capacity of a table when it is not used.
• The order equation makes sure we start using lower numbered tables. Also it reduces symmetry and may speed things up.