1
$\begingroup$

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!

$\endgroup$
3
  • 1
    $\begingroup$ What's stopping you from simply allocating things from left to right, as needed? Won't that yield a solution with the maximal number of consecutive zeros (towards the right)? $\endgroup$ Commented Feb 14, 2020 at 20:46
  • $\begingroup$ @madnessweasley Constraints. Are the constraints are linear but I am having a hard time for the objective. $\endgroup$ Commented Feb 16, 2020 at 19:18
  • $\begingroup$ Can you list what other kinds of constraints you have in your formulation? $\endgroup$ Commented Feb 17, 2020 at 22:56

1 Answer 1

Reset to default
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.