Vincolo di divisibilità nella programmazione Integer
Ho una semplice domanda riguardante la divisibilità nella programmazione intera
supponiamo che la funzione obiettivo sia
$\text{max}\quad x_1 + x_2$
dove il vincolo è che la somma di $x_1$ e $x_2$ sono divisibili per 5, 7 o 9
Mi chiedo come posso modellare il vincolo di divisibilità?
L'unica soluzione a cui riesco a pensare è come
max
x1+x2+ 0*x3
subject to
y1+y2+y3 >= 0
y1*(x1+x2) = 5*x3*y1
y2*(x1+x2) = 7*x3*y2
y3(x1+x2) = 9*x3*y3
x1>=0,x2>=0,x3>=0
È corretto risolvere vincoli di divisibilità come questo?
Grazie!
Risposte
Supponiamo $x_1+x_2$ è delimitata sopra da alcuni $M$; altrimenti il problema è illimitato. Permettere$D=\{5,7,9\}$, e per $d\in D$, introdurre la variabile binaria $z_d$ e variabile intera non negativa $w_d$. Puoi applicare il comportamento desiderato imponendo i seguenti vincoli lineari: \ begin {align} x_1 + x_2 & = \ sum_ {d \ in D} d \ cdot w_d \\ d \ cdot w_d & \ le M \ cdot z_d && \ testo {per$d\in D$} \\ \ sum_ {d \ in D} z_d & = 1 \ end {align}