10
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 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)? $\endgroup$ – prubin Feb 20 '20 at 21:10
  • $\begingroup$ Either way works. Any of [1,1,1,0,0], [1,0,0,1,1], [0,0,1,1,1] is the optimal solution. $\endgroup$ – MIMIGA Feb 21 '20 at 17:12
  • $\begingroup$ Any other objective that can achieve a similar goal is also helpful. $\endgroup$ – MIMIGA Feb 21 '20 at 18:39
  • $\begingroup$ Hi MIMIGA, Is the length of array t a constant in your problem? How about number of appointment and their duration? $\endgroup$ – Oguz Toragay Feb 21 '20 at 22:01
  • $\begingroup$ @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. $\endgroup$ – MIMIGA Feb 22 '20 at 3:53
7
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\begingroup$ it's an interesting answer but, would you please, what does this "$\sum\limits_{n=1}^N z_n = 1$" mean? $\endgroup$ – A.Omidi Feb 23 '20 at 5:30
  • $\begingroup$ @A.Omidi it's for linearization of $y = \max w_n$. You can check the answer here $\endgroup$ – EhsanK♦ Feb 23 '20 at 20:05
  • 1
    $\begingroup$ 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]$ $\endgroup$ – EhsanK♦ Feb 23 '20 at 20:06
  • $\begingroup$ @EhsanK, that's right. many thanks for your hint. $\endgroup$ – A.Omidi Feb 24 '20 at 5:13
  • $\begingroup$ @EhsanK: Thanks, you're right that $w_n$ is an integer, not binary (except for $n=1$). I've fixed it. $\endgroup$ – prubin Feb 24 '20 at 15:53
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ But this only drives to allocate to early slots, right? $\endgroup$ – MIMIGA Mar 11 '20 at 20:24
  • $\begingroup$ 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. $\endgroup$ – jalopez910 Mar 26 '20 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.