Variabel Boolean true iff persamaan puas dalam ILP

8

Dengan asumsi adalah variabel boolean dalam program ILP (yang , st ) dan , dibatasi bilangan bulat variabel antara dan . Saya ingin menyandikan batasan tingkat tinggi berikut: $y$ $y \in Z$ $0 <= y <= 1$ $x_1$ $x_2$ $0$ $M$

y = 1 ⟺ x_{1} \leq x_{2}

$y = 1 \iff x_1 \le x_2$

Sejauh ini saya sudah mendapat ini:

x_{1} \leq x_{2} + (M. + 1) y

$x_1 \le x_2 + (M+1)y$

Ini menegaskan bahwa setiap kali benar, harus atau persamaan tidak akan berlaku. Namun, jika , tidak ada yang membatasi dan karenanya bisa atau . $x_1 > x_2$ $y$ $1$ $x_1 \le x_2$ $y$ $0$ $1$

Apa persamaan lain yang bisa saya tambahkan untuk menyandikan kendala?

integer-programming Setzer22
sumber

cs.stackexchange.com/q/104990/755

DW

5

Anda bisa melakukan ini dengan memperkenalkan dua ketidaksetaraan

x_{1} \leq x_{2} + M. (1 - y)

$x_1 \le x_2 + M (1-y)$

dan

x_{1} > x_{2} - M. y .

$x_1 > x_2 - M y.$

Yang pertama mengkodekan persyaratan $y=1 \implies x_1 \le x_2$ (Anda dapat melihat bahwa jika $y=1$ , lalu $M(1-y)$ istilah menghilang; jika $y=0$ , kemudian $M(1-y)$ menjadi sesuatu yang besar dan ketidaksetaraan secara otomatis terpenuhi). Yang terakhir mengkodekan persyaratan $y=0 \implies x_1 > x_2$ (untuk alasan yang sama).

Semoga ini memberi Anda ide bagaimana menangani implikasi jenis lain juga, jika timbul. Pada dasarnya, kalikan dengan sesuatu yang besar, dan tambahkan / kurangi di suatu tempat.

DW
sumber

5

Anda bisa menambahkan konstanta $0<A<M$ dan kemudian Anda menambahkan batasan ini:

SEBUAH - y (SEBUAH + M.) ⩽ x_{1} - x_{2} ⩽ M. (1 - y) .

$A-y(A+M)\leqslant x_1-x_2\leqslant M(1-y).$

Jika $y=1$ maka Anda yang tersisa

- M. ⩽ x_{1} - x_{2} ⩽ 0,

$-M\leqslant x_1-x_2\leqslant 0,$ yang mengatakan itu

x_{1} ⩽ x_{2}

$x_1\leqslant x_2$ .

Dan jika $y=0$ maka Anda akan ditinggalkan

SEBUAH ⩽ x_{1} - x_{2} ⩽ M.,

$A\leqslant x_1-x_2\leqslant M,$ yang mengatakan itu

x_{1} > x_{2}

$x_1>x_2$ (sejak

0 < A < M

$0<A<M$ ).

Ribz
sumber

3

Lihatlah kendala indikator dan kendala SOS. Meskipun Anda dapat mendefinisikan relasi target secara linear seperti yang dijelaskan oleh jawaban lain, kendala khusus dapat ditangani dengan lebih efisien oleh pemecah IP.

Jika Anda memutuskan untuk mengimplementasikan kendala secara langsung seperti dijelaskan oleh jawaban lain, cobalah untuk menggunakan M sekecil mungkin, dan pertimbangkan untuk menurunkan toleransi integral jika hasil Anda tidak benar. Selain itu, hindari ketimpangan yang ketat, mereka ambigu dalam konteks aritmatika floating point.

Menggunakan batasan indikator:

$x_1\le x_2 \leftarrow y=1$

$x_2\ge x_1 +1\leftarrow y=0$

Batasan kedua setara dengan $x_2>x_1$ untuk bilangan bulat, jika Anda mau $x_2\ge x_1$ cukup jatuhkan 1.

Septimus G
sumber

Terima kasih atas saran yang bermanfaat! Bisakah Anda menguraikan bagaimana kendala SOS bermanfaat / berguna dalam situasi khusus ini?

DW

Saya menambahkan contoh dengan batasan indikator. Untuk SOS lebih rumit dan Anda harus memperkenalkan variabel tambahan, sehingga Anda mungkin tidak mendapatkan banyak dengan menggunakannya. Saya pikir satu-satunya aspek untuk berhati-hati di sini adalah masalah numerik yang dapat timbul dengan menggunakan formulasi yang diusulkan oleh orang lain, dan bagaimana cara mengatasinya. Jika Anda memiliki akses ke solver dengan batasan indikator, maka cobalah dengan cara itu karena solver dapat melakukan percabangan pada mereka secara langsung, atau secara dinamis memodifikasi nilai big-M.

Septimus G

Variabel Boolean true iff persamaan puas dalam ILP

Jawaban: