Program Integer Linear mana yang mudah?

Ketika mencoba memecahkan masalah, saya akhirnya menyatakan bagian dari itu sebagai program linear integer berikut. Di sini adalah bilangan bulat positif yang diberikan sebagai bagian dari input. Subset tertentu dari variabel diatur ke nol, dan sisanya dapat mengambil nilai integral positif: $\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w$ $x_{ij}$

Memperkecil

$\sum_{j=1}^{m}c_{j}\sum_{i=1}^{\ell}x_{ij}$

Tunduk pada:

$\sum_{j=1}^{m}x_{ij}=n_{i}\,\,\forall i$

$\sum_{i=1}^{\ell}x_{ij}\ge w\,\,\forall j$

Saya ingin tahu apakah program integer ini dapat dipecahkan dalam waktu polinomial; masalah asli saya terpecahkan jika itu, dan saya harus mencoba cara lain jika tidak. Jadi pertanyaan saya adalah:

Bagaimana saya mengetahui jika program linear integer tertentu dapat diselesaikan dalam waktu polinomial? Program linear integer mana yang dikenal mudah? Secara khusus, dapatkah program di atas diselesaikan dalam waktu polinomial? Bisakah Anda mengarahkan saya ke beberapa referensi tentang ini?

reference-request linear-programming polynomial-time integer-programming integrality-gap gphilip
sumber

Jawaban:

Ini adalah kasus khusus masalah transportasi (atau masalah aliran biaya minimum), dan dapat diselesaikan dalam waktu polinomial. Matriks koefisien benar-benar unimodular karena merupakan matriks kejadian dari grafik bipartit.

Artikel Wikipedia berikut bisa bermanfaat.

Yoshio Okamoto
sumber

@Yoshio: Terima kasih, itu menjawab contoh masalah khusus saya (setelah saya memverifikasi sendiri). Apakah Anda tahu kondisi selain unimodularity total yang menjamin solusi waktu polinomial?

gphilip

@ gphilip: Saya akan meringkas pertanyaan-pertanyaan tesis dengan istilah "integralitas polyhedra" dan literatur tentang hal ini sangat besar. Buku "Optimalisasi Kombinatorial: Pengepakan dan Penutup" oleh Gerard Cornuejols (diterbitkan pada tahun 2001) menjelaskan beberapa hasil di sepanjang baris ini.

Yoshio Okamoto

@Yoshio: Bisakah Anda memberi tahu saya mengapa Anda berpikir bahwa matriks koefisien adalah matriks kejadian dari grafik bipartit? Maafkan ketidaktahuan saya, tetapi untuk berbicara tentang matriks koefisien, kita tidak harus terlebih dahulu mengkonversi semua kendala ke bentuk standar (

A x \leq b

$Ax\le b$ )? Setelah kami melakukannya, matriks akan memiliki -1 entri, dan kemudian tidak cocok dengan definisi matriks kejadian (AFAIK). Atau apakah kita dapat berbicara tentang matriks koefisien tanpa terlebih dahulu mengubah kendala ke bentuk standar?

gphilip

@ gphilip: Maaf. Saya membuat jalan pintas implisit, dan saya berbicara tentang matriks koefisien tanpa mengkonversi ke bentuk standar. Saya menggunakan jalan pintas berikut. (1) Jika

A

$A$ benar-benar unimodular (TU, singkatnya), kalau begitu

- A

$-A$ juga TU, yang berarti bahwa kita tidak perlu peduli dengan arah ketidaksetaraan. (2) Jika

A

$A$ adalah TU, kalau begitu

[A ∣ - A]

$[A \mid -A]$ juga TU, yang berarti bahwa kita tidak perlu peduli dengan kendala kesetaraan. (3) Setiap submatrix dari matriks TU adalah TU. Menerapkan aturan-aturan ini ke matriks kejadian dari grafik bipartit harus membuktikan properti untuk bentuk standar.

Yoshio Okamoto

Biarkan saya mengubah aturan jalan pintas saya sebagai berikut. (1) Duplikasi baris mempertahankan unimodularity total. (2) Pembalikan tanda baris mempertahankan unimodularity total. Mereka harus melakukan pekerjaan itu.

Yoshio Okamoto

Secara umum, sulit dikatakan. Tetapi syarat yang cukup adalah matriks kendala Anda benar-benar unimodular dan sisi kanan selalu bilangan bulat (dalam hal ini sisi kanan adalah bilangan bulat, tetapi Anda masih harus memeriksa tentang unimodularity)

Anda harus melihat ini: http://en.wikipedia.org/wiki/Linear_program#Integer_unknowns

Vinicius dos Santos
sumber

Saya sedang berpikir tentang matriks Anda dan itu terlihat sama sekali tidak simultan.

Vinicius dos Santos

@Vinicius: Bisakah Anda memberi tahu saya mengapa matriks terlihat sama sekali tidak mirip dengan Anda? Aku tidak bisa memikirkan ini, terlepas dari komentar Yoshio (tolong lihat tanggapan saya di sana).

gphilip

@ gphilip: Di en.wikipedia.org/wiki/Unimodular_matrix di bagian "Matriks yang sama sekali tidak sama sekali umum", item pertama mencantumkan 4 kondisi yang cukup untuk sebuah matriks menjadi unimodular. Saya pikir kondisi ini, bersama dengan pintasan yang dikomentari Yoshio, cukup untuk menunjukkan bahwa masalahnya dapat diselesaikan dalam waktu polinomial.

Vinicius dos Santos

@ gphilip: Apa motivasi untuk Program Linear ini?

Vinicius dos Santos

@Vinicius: Kami mencoba memecahkan masalah yang dirumuskan dalam istilah memodifikasi matriks input dengan cara tertentu untuk mendapatkan matriks lain dengan beberapa sifat yang baik. LP ini keluar dari satu sub-masalah selama proses.

gphilip

Program integer dengan hanya persamaan dapat diselesaikan dengan program linier.

T ....
sumber

ini tampaknya penting untuk kepentingannya sendiri.

T ....

Saya tidak akan menyebutnya program integer. Ini adalah sistem persamaan linear atas bilangan bulat, dipecahkan secara efisien dengan menghitung bentuk normal Hermite.

Sasho Nikolov

@SashoNikolov kasus yang merosot tapi pasti yang valid sekalipun.

T ....

mengapa memilih negatif?

T ....