Questo problema è simile alla programmazione lineare interi anche un problema di completamento NP?

Question

Ho riscontrato questo problema mentre provo a elaborare un algoritmo di formattazione da tavolo.

È molto simile alla programmazione lineare standard (anche se usa $>$ invece di $<$; Non ho molto familiarità con la programmazione lineare, ma credo che questo non abbia molto).

Permettere $ vec v = (v_1, dots, v_n) $ Sii un vettore di variabili positive-integer.

Il problema è trovare se c'è un incarico $ vec v $ tale che

$$ v_1 + dots + v_n = c $$

e

$$ A vec v geq vec w $$

dove $ c $ è una costante nota, $ vec w $ è una costante conosciuta e $ A $ è una matrice con la proprietà speciale di ogni riga di $ A $ è della forma $ (0, dots, 0, 1, dots, 1, 0, dots, 0) $.

Cioè, ogni vincolo di disuguaglianza utilizza solo coefficienti 1 e 0 e solo variabili "consecutive" compaiono in ciascun vincolo lineare.

---

Penso che questo problema sia completo NP, ma non sono stato in grado di dimostrarlo.

Penso che sia più probabile che una riduzione a esattamente 1 in 3-sat o cover set sia possibile avere successo (le variabili sarebbero rispettivamente letterali/valori e le file nella matrice corrisponderebbero a clausole/set), ma la restrizione che solo vincola Fare riferimento a variabili consecutive non sembra abbastanza forte da descrivere clausole/set arbitrari.

In alternativa, potrei sbagliarmi e questo problema ha in realtà un algoritmo che mi è mancato. (Il problema che sono effettivamente interessato a risolvere è trovare il più piccolo $ c $ in modo tale che i vincoli rimangano soddisfacenti, ma ho formulato il problema in questo modo in modo che rimanga un semplice problema di decisione)

---

Ad esempio, ecco una piccola istanza di questo problema:

$$ inizio {array} {} v_1 + v_2 + v_3 + v_4 & = & 10 v_1 & geq & 1 v_2 & geq & 1 v_2 + v_3 & geq & 3 v_3 + v_4 & geq & 4 v_3 & geq & 1 v_4 & geq & 1 end {array} $$

che ha un possibile incarico $ vec v = (1, 1, 6, 2) $.