Représentation ILP du nombre de séquences maximales de 1 rangée

Question

J'utilise actuellement un ILP pour modéliser des événements qui se produisent sur une séquence d'entrée de 1 $ ... n $. Ces événements modifient la séquence d'entrée afin d'obtenir une séquence souhaitée. Chaque événement peut se produire sur une gamme consécutive $ (i, j) $ Et aucun événement ne peut se chevaucher. Par conséquent, je peux représenter des événements par une matrice $ a = {0, 1 } ^ {n Times n} $ où $ a_ {i, j} = 1 $ si il y a un événement qui commence à $ i $ et se termine à $ j $ ($ i <= j $).

Malheureusement, cela se traduit par $ O (n ^ 2) $ variables et dans certains cas $ O (n ^ 3) $ ou un plus grand nombre de contraintes. Ce serait idéal si je pouvais à la place représenter ces événements comme une ligne $ a '= {0,1 } ^ n $, où $ a'_i = 1 iff existant a_ {p, q} quad text {st} quad p leq i leq q land a_ {p, q} = 1 $
c'est-à-dire une position $ a'_i = 1 $ si il y a un événement qui modifie la position $ i $.

Depuis que j'optimise le nombre d'événements, pour le moment, je minimise $ sum a_ {p, q} $, car il représente le nombre d'événements. Si j'abandonne $ a $ et essayez d'utiliser uniquement $ a '$, Je me retrouve avec une ligne, par exemple $ a '= [1,1,0, ..., 1,0,1] $.

Question 1: Je veux représenter le nombre total d'événements donnés $ a '$. Actuellement, je pense $ sum a_i (1-a_ {i + 1}) $ Pour compter le nombre de «fins» des événements. Évidemment, je peux également gérer le cas Edge. Malheureusement, cela se traduit par un produit de variables binaires. Je sais que je peux représenter cela avec une variable d'assistance, et résumer simplement cela, mais je me demandais s'il y avait des moyens plus efficaces.

Question 2: Cette question est plus importante, car tout mon modèle tourne autour de cela. Un événement n'affectera que les éléments d'entrée après la fin de l'événement. Considérez les événements comme des duplications. Si une plage $ (i, j) $ est dupliqué, tous les éléments après $ j $ se déplacerait vers la droite par $ j-i + 1 $ machines à sous. Suivant cette idée des événements étant des duplications, considérez l'entrée ci-dessous:

$ a, b, c, d, e $ Et la séquence souhaitée $ a, b, a, b, c, d, e, d, e $. Nous pouvons y parvenir en duplication $ a, b $ et $ d, e $ c'est à dire $ a '= [1,1,0,1,1] $. Remarquez comment les positions $0$ et $1$ ne changeait pas du tout, les positions $2,3,4,5,6$ étaient à l'origine $0,1,2,3,4$, et positions $7$ et $8$ étaient à l'origine $3$ et $4$.

Essentiellement, pour chaque position $ i $ Dans la séquence résultante, je voudrais pouvoir déterminer quelle position $ j $ Il vient de la séquence originale. Considérer la position $6$ Dans la séquence résultante, nous pouvons clairement voir que cela venait de position $4$. Nous remarquons que ce changement de $2$. De même, positionner $5$ est venu de position $3$. Un modèle se déroule de telle sorte que le décalage de position $ i $ est toujours égal au $ sum_ {j où $ k $ est le plus grand index tel que $ k leq i land a_k = 0 $. C'est la même chose que de dire que nous prenons la somme de toutes les valeurs de $ a '$ au plus récent $0$ avant ou à $ i $ dans $ a '$.

Comment puis-je modéliser un tel changement dans un ILP? C'est-à-dire donné $ a '$, comment puis-je créer une variable $ h $ dans l'ILP tel que $ h_ {r, l} = 1 $ fic $ sum_ {j où $ k $ est le plus grand index tel que $ k leq r land a_k = 0 $.