Batasan pembagian dalam pemrograman Integer

Question

Saya punya pertanyaan sederhana tentang pembagian dalam pemrograman integer

misalkan fungsi tujuannya adalah

$\text{max}\quad x_1 + x_2$

dimana batasannya adalah jumlah dari $x_1$ dan $x_2$ habis dibagi 5, 7 atau 9

Saya bertanya-tanya bagaimana saya bisa memodelkan kendala pembagian?

Satu-satunya solusi yang dapat saya pikirkan adalah seperti

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

Apakah benar untuk mengatasi kendala perpecahan seperti ini?

Terima kasih!

Answer 1

Seharusnya $x_1+x_2$ dibatasi di atas oleh beberapa $M$; jika tidak, masalahnya tidak terbatas. Membiarkan$D=\{5,7,9\}$, dan untuk $d\in D$, perkenalkan variabel biner $z_d$ dan variabel integer nonnegatif $w_d$. Anda dapat menegakkan perilaku yang diinginkan dengan menerapkan batasan linier berikut: \ begin {align} x_1 + x_2 & = \ sum_ {d \ in D} d \ cdot w_d \\ d \ cdot w_d & \ le M \ cdot z_d && \ teks {untuk$d\in D$} \\ \ sum_ {d \ in D} z_d & = 1 \ end {align}