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

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.

• Do you specifically want to maximize the number of consecutive zeros at the end of the sequence (meaning a long string of zeros in the middle of the sequence would not fulfill your goal)? – prubin Feb 20 '20 at 21:10
• Either way works. Any of [1,1,1,0,0], [1,0,0,1,1], [0,0,1,1,1] is the optimal solution. – MIMIGA Feb 21 '20 at 17:12
• Any other objective that can achieve a similar goal is also helpful. – MIMIGA Feb 21 '20 at 18:39
• Hi MIMIGA, Is the length of array t a constant in your problem? How about number of appointment and their duration? – Oguz Toragay Feb 21 '20 at 22:01
• @OguzToragay Length of array, number of appointments, and their duration are all fixed. They are not constraints. I assume if the example I gave can be formulated, I can extend to a more general formulation. – MIMIGA Feb 22 '20 at 3:53

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$$.

• it's an interesting answer but, would you please, what does this "$\sum\limits_{n=1}^N z_n = 1$" mean? – A.Omidi Feb 23 '20 at 5:30
• @A.Omidi it's for linearization of $y = \max w_n$. You can check the answer here – EhsanK Feb 23 '20 at 20:05
• Paul, I think the first paragraph should be modified since $w_n$ (as also obvious in your example) is an integer and $w_n \notin [0,1]$ – EhsanK Feb 23 '20 at 20:06
• @EhsanK, that's right. many thanks for your hint. – A.Omidi Feb 24 '20 at 5:13
• @EhsanK: Thanks, you're right that $w_n$ is an integer, not binary (except for $n=1$). I've fixed it. – prubin Feb 24 '20 at 15:53

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.

• But this only drives to allocate to early slots, right? – MIMIGA Mar 11 '20 at 20:24
• Yes, this would try to group them all in the early slots. If instead minimize we maximize, then it will group them on the late slots. Indeed, this is just a simple objective function that does not consider all possible solutions of your problem. – jalopez910 Mar 26 '20 at 18:00