Rappresentazione ILP del numero di 1 sequenze massime di riga

Question

Attualmente sto usando un ILP per modellare eventi che si verificano in una sequenza di input da $ 1 ... n $. Questi eventi modificano la sequenza di input per ottenere una sequenza desiderata. Ogni evento può avvenire su un intervallo consecutivo $ (i, j) $ E non esistono due eventi. Pertanto, posso rappresentare eventi di qualche matrice $ a = {0, 1 }^{n Times n} $ dove $ a_ {i, j} = 1 $ se c'è un evento che inizia a $ i $ e termina a $ j $ ($ i <= j $).

Sfortunatamente, questo si traduce $ O (n^2) $ variabili e in alcuni casi $ O (n^3) $ o un numero maggiore di vincoli. Sarebbe l'ideale se invece potessi rappresentare questi eventi come una riga $ a '= {0,1 }^n $, dove $ a'_i = 1 iff esiste a_ {p, q} quad text {st} quad p leq i leq q land a_ {p, q} = 1 $
cioè una posizione $ a'_i = 1 $ se c'è un evento che modifica la posizione $ i $.

Da quando sto ottimizzando il numero di eventi, al momento sto minimizzando $ sum a_ {p, q} $, poiché rappresenta il numero di eventi. Se vago $ a $ e prova a usare solo $ a '$, Sono rimasto con qualche riga, per esempio $ a '= [1,1,0, ..., 1,0,1] $.

Domanda 1: Voglio rappresentare il numero totale di eventi dati $ a '$. Attualmente sto pensando $ sum a_i (1-a_ {i+1}) $ per contare il numero di "estremità" degli eventi. Ovviamente posso gestire anche il caso Edge. Sfortunatamente, questo si traduce in un prodotto di variabili binarie. So che posso rappresentarlo con una variabile di supporto e solo sommare, ma mi chiedevo se ci fossero modi più efficienti.

Domanda 2: Questa domanda è più importante, poiché il mio intero modello ruota attorno a questo. Un evento influenzerà solo gli elementi di input dopo la fine dell'evento. Pensa agli eventi come duplicazioni. Se un po 'di portata $ (i, j) $ è duplicato, tutti gli elementi dopo $ j $ si sposterebbe a destra di $ j-i+1 $ slot. Seguendo questa idea di eventi come duplicazioni, considera l'input di seguito:

$ a, b, c, d, e $ e la sequenza desiderata $ A, B, A, B, C, D, E, D, E $. Possiamo raggiungere questo obiettivo duplicando $ a, b $ e $ d, e $ cioè $ a '= [1,1,0,1,1] $. Notare come le posizioni $0$ e $1$ non si è spostato affatto, posizioni $2,3,4,5,6$ erano originariamente $0,1,2,3,4$, e posizioni $7$ e $8$ erano originariamente $3$ e $4$.

Essenzialmente, per ogni posizione $ i $ Nella sequenza risultante, vorrei poter determinare quale posizione $ j $ Viene dalla sequenza originale. Considera la posizione $6$ Nella sequenza risultante, possiamo vedere chiaramente che veniva dalla posizione $4$. Notiamo che questo spostamento di $2$. Allo stesso modo, posizione $5$ Veniva dalla posizione $3$. Uno schema si sviluppa in modo tale che lo spostamento della posizione $ i $ è sempre uguale a $ sum_ {j dove $ k $ è l'indice più grande tale che $ k leq i land a_k = 0 $. Questo è lo stesso che dire che stiamo prendendo la somma di tutti i valori di $ a '$ fino al più recente $0$ prima o at $ i $ in $ a '$.

Come posso modellare tale spostamento in un ILP? Cioè dato $ a '$, come posso creare una variabile $ H $ nell'ILP tale che $ h_ {r, l} = 1 $ Iff $ sum_ {j dove $ k $ è l'indice più grande tale che $ k leq r land a_k = 0 $.