Given a vector $c\in\Re^n$ and a vector $b\in\Re^n$, I would like to design a binary programming problem, \begin{equation} \max_{x\in\{1,0\}} c^\top x \end{equation} and for constraints, I need all consecutive $1$s in the decision variable $x$ times with corresponding $b$ has the same value.
For example, if $\sum_{k=1}^{4} b_k \approx \sum_{k=8}^{9}b_k \approx \sum_{k=11}^{15} b_k $, then a feasible $x$ would be: \begin{equation} x=\begin{bmatrix}1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1\end{bmatrix} \end{equation} where "$\approx$" means that differences are less than given small tolerance.
Can anyone give a suggestion about how to design such constraints? Thanks!
Here's a network-based mixed integer linear programming formulation. The nodes are $N=\{0,\dots,n+1\}$, where $s=0$ is the source node and $t=n+1$ is the sink node. The arcs are $A=\{i\in N, j\in N: i < j\}$. For $(i,j)\in A$ and $v\in\{0,1\}$, let binary decision variable $y_{i,j,v}$ indicate whether elements $i,\dots,j-1$ form a consecutive run with value $v$. Let decision variable $z\in [L,U]$ be the common sum of $b_k$ values for each run of $1$s, with constant bounds $L=\sum_{k=1}^n \min(b_k,0)$ and $U=\sum_{k=1}^n \max(b_k,0)$. Let constant $\epsilon>0$ be the tolerance for $\approx$. The problem is to maximize $$\sum_{(i,j) \in A: i \not= 0} \left(\sum_{k=i}^{j-1} c_k\right) y_{i,j,1}$$ subject to \begin{align} \sum_{(i,j)\in A} y_{i,j,v} - \sum_{(j,i) \in A} y_{j,i,1-v} &= [i = s \land v = 0] &&\text{for $i \in N \setminus \{t\}$ and $v \in \{0,1\}$} \tag1 \\ -\frac{\epsilon}{2}+M_1 (1-y_{i,j,1}) \le z-\sum_{k=i}^{j-1} b_k &\le \frac{\epsilon}{2}+M_2(1-y_{i,j,1}) &&\text{for $(i,j) \in A$ such that $i \not= s$} \tag2 \end{align} Constraint $(1)$ enforces flow balance, with a dummy run of $0$s starting at the source. The (big-M) constraint $(2)$ enforces the logical implication $$y_{i,j,1} = 1 \implies \left|z-\sum_{k=i}^{j-1} b_k\right| \le \frac{\epsilon}{2}.$$ You can take big-M values \begin{align} M_1 &= L-\sum_{k=i}^{j-1} b_k+\frac{\epsilon}{2} \\ M_2 &= U-\sum_{k=i}^{j-1} b_k-\frac{\epsilon}{2} \end{align}
After solving, you can postprocess to compute $x_k=1$ for $k\in\{i,\dots,j-1\}$ for all $(i,j)\in A$ such that $y_{i,j,1}=1$.
For your example data with $\epsilon=0.001$ and randomly generated $c_k$, here is an optimal solution: \begin{matrix} i &j &v &y_{i,j,v} \\ \hline 0 &1 &0 &1 \\ 1 &10 &1 &1 \\ 10 &13 &0 &1 \\ 13 &18 &1 &1 \\ 18 &39 &0 &1 \\ 39 &41 &1 &1 \end{matrix} \begin{align} z &= 0.03755 \\ \sum_{k=1}^9 b_k &= 0.037050 \\ \sum_{k=13}^{17} b_k &= 0.037948 \\ \sum_{k=39}^{40} b_k &= 0.037259 \end{align} \begin{matrix} k & b_k & c_k & x_k \\ \hline 1 & -0.05118323 & 0.6515976 & 1 \\ 2 & 0.00626961 & 0.9214633 & 1 \\ 3 & 0.03077166 & -0.4772522 & 1 \\ 4 & 0.01603241 & 0.6608215 & 1 \\ 5 & -0.01783201 & 0.0680905 & 1 \\ 6 & 0.05471783 & 0.8297638 & 1 \\ 7 & 0.00210547 & 0.7863591 & 1 \\ 8 & 0.01374827 & -0.5370080 & 1 \\ 9 & -0.01757969 & 0.3396552 & 1 \\ 10 & -0.02625333 & 0.6314154 & 0 \\ 11 & -0.00446315 & -0.2994972 & 0 \\ 12 & -0.02073846 & -0.0031765 & 0 \\ 13 & -0.01252584 & 0.4703300 & 1 \\ 14 & 0.00975359 & 0.7840745 & 1 \\ 15 & -0.01428596 & 0.3702945 & 1 \\ 16 & 0.05906364 & -1.6571357 & 1 \\ 17 & -0.00405783 & 0.6717557 & 1 \\ 18 & -0.02165255 & -0.3653084 & 0 \\ 19 & 0.00831523 & -1.1568648 & 0 \\ 20 & -0.01010610 & 0.7950355 & 0 \\ 21 & 0.00139317 & -0.1578055 & 0 \\ 22 & 0.05249583 & 0.5692947 & 0 \\ 23 & -0.00862360 & -0.1551003 & 0 \\ 24 & -0.05346463 & -0.6032818 & 0 \\ 25 & 0.00999009 & -0.2297138 & 0 \\ 26 & -0.01945239 & 0.3247675 & 0 \\ 27 & -0.00064889 & -0.6720116 & 0 \\ 28 & 0.01407921 & -1.7712827 & 0 \\ 29 & 0.02668193 & 0.7281612 & 0 \\ 30 & -0.02578230 & -0.3458772 & 0 \\ 31 & 0.00414781 & -0.0010739 & 0 \\ 32 & 0.04517223 & -1.2890061 & 0 \\ 33 & 0.01560807 & -1.5741394 & 0 \\ 34 & -0.02464580 & -1.0035068 & 0 \\ 35 & -0.03119161 & -1.0080236 & 0 \\ 36 & 0.03360712 & 0.2631495 & 0 \\ 37 & 0.01904169 & 0.0646314 & 0 \\ 38 & 0.06667319 & -0.1402586 & 0 \\ 39 & 0.04471458 & 0.3587272 & 1 \\ 40 & -0.00745605 & 0.9589894 & 1 \end{matrix}