Use integer/quadratic programming to maximize consecutive zeros in a binary array

Question

A binary array $t = [t_1, t_2, t_3, t_4, t_5]$ with each element a binary integer variable taking values 0 or 1. You can think this vector as slots with 1 representing the slot being taken and 0 otherwise.

Constraints: Now 2 appointments need to be scheduled with the first one taking 1 slot and the second one taking 2 slots. The second appointment must be scheduled at or after the second slot ($t_2$).

Objective: Maximize the number of consecutive zeros in array $t$.(Intend to leave a long range empty slots for future planning)

Solutions: One of the optimal solutions is to put first appointment into $t_1$ and the second appointment into $t_2$ and $t_3$, $t = [1,1,1,0,0]$, which has a consecutive zero number 2. A feasible but non-optimal solution is to put first appointment into $t_1$ and the second appointment into $t_3$ and $t_4$, $t=[1,0,1,1,0]$, which has a consecutive zero number 1.

Optimal Constraints: How to formulate the question in a linear/integer/mixed-integer way that can be solved by an optimization solver? Constraints can be definitely formulated in a linear integer way but I am having a hard time for the objective.

Answer 1

Let $N$ be the dimension of your binary vector $x$. Introduce new variables $w_n \in [0,n]$ for $n=1,\dots,N$. Each $w_n$ will capture the number of consecutive zeros culminating at position $n$. So, for instance, if $x=[1,0,0,1,1]$, then $w=[0,1,2,0,0]$. Note that $w$ does not need to be declared integer; the constraints will force it to be integer-valued.

Next, add the following constraints for each $n$ (where $w_0 = 0$): \begin{align*} w_{n} & \le N(1-x_{n})\\ w_{n}-w_{n-1} & \le1\\ w_{n}-w_{n-1} & \ge1-Nx_{n}. \end{align*} If $x_n=1$, the first constraint forces $w_n=0$ and the second and third constraints have no effect. If $x_n=0$, the first constraint has no effect, while the second and third constraints combine to force $w_n=w_{n-1}+1$.

As I understand you, you now want to maximize $$\max_{n=1}^N w_n.$$ To do this, you can introduce binary variables $z_1,\dots,z_N$ along with the constraint $$\sum_{n=1}^N z_n = 1,$$ plus a continuous variable $y$ to represent the objective value. You will maximize $y$ subject the constraints $$y\le w_{n}+N(1-z_{n})\quad \forall n.$$ This last constraint is nonbinding when $z_n=0$. For exactly one $n$, $z_n$ will be 1 and $y$ will be less than or equal to $w_n$. The solver will choose the $n$ corresponding to the largest $w_n$ and set $y=w_n$.

Answer 2

I would say that this objective function would do a decent job:

$$\min \sum_{i = 0}^{n} i^2 t_i$$

where $n$ is the total number of available slots.