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

linear programmingnonlinear optimizationoptimization

A binary array $x = [x_1, x_2, x_3, x_4, x_5]$ with each element a binary integer variable taking values 0 or 1. One constraint:
$$x_1 + x_2 + x_3 + x_4 + x_5 == 1$$
Basically one of the variables must be 1. I am trying to maximize the number of consecutive zeros in this array. The optimal result would be
$x_1 = 1$ or $x_5 = 1$. In either case, it yields a result with 4 consecutive zeros.

In practice, I want to allocate some slots but leave some long-range of empty slots for future allocation. Another example is: If I have to allocate one slot with length 1 and another slot with length 2. I will allocate $x_1, x_2, x_3$ so that the remaining empty slot is $x_4, x_5$ (Or allocate $x_3,x_4,x_5$ and leave $x_1,x_2$).

Any suggestion to formulate in a way an optimization solver can solve? Or any suboptimal formulation? Thanks!

Best Answer

Suppose you have the binary vector $x = (x_1,\cdots,x_n) \in \{0,1\}^{n}$, where $x_i = 1$ if the $i^{\text{th}}$ slot is filled and zero otherwise. I can think of the following naive and nasty formulation for the objective (maximum number of consecutive zeros):

$$ \underset{J \subset \{1,\cdots,n\}}{\max}\left\lbrace \lvert J \rvert \prod_{j \in J} (1-x_j) \right\rbrace.$$

Note:

  1. The variable is the subset $J$ of $\{1,\cdots,n\}$
  2. The number of possible choices of $J$ is $2^n - 1$ (excluding the empty set)
  3. The product term inside the $\max$ can be linearized by adding exponentially many auxiliary variables

There may be a better modeling trick - you can try asking at OR Stackexchange.

Related Question