10

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.

MIMIGA
  • 201
  • 1
  • 3
  • 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 03:53

2 Answers2

7

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

prubin
  • 39,078
  • 3
  • 37
  • 104
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.

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
jalopez910
  • 21
  • 2
  • 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