writing a constraint for a maximisation problem

Question

There are $n$ seats in a row. $p$ people (where $p<n$) can seat anywhere as long as long as they sit at least one seat apart due to personal relationships.

This statement is part of a larger problem related to optimisation. Can you give insights how to write this statement as a constraint? I am struggling to find a way to write it nicely in a constraint form, so I am ready for optimisation.

Insights appreciated

Answer 1

Let $x_i$ for i=1,..,n be a binary variable, which is 1 if seat i is occupied, and 0 if it is not.

$x_i + x_{i+1} \le 1$, for i=1,..,n-1 precludes 2 people sitting next to each other.

$\Sigma_{i=1}^n x_i = p$ if you want to make sure everyone is seated somewhere.

If it is impossible to satisfy both these constraints, the problem will be infeasible. This would happen if $p > \lfloor (n+1)/2 \rfloor$.

Answer 2

Hi: If $a_i$ = 1 when you sit there and zero when you don't. Then the constraint is $abs((a_{i+1} - a_{i})) > 0$. Not sure if that helps because it involves integer programming but maybe you can modify as necessary. Note that this type of constraint won't allow for two empty seats in a row.