Apa yang diketahui tentang solusi untuk masalah pemrograman linear integer yang jarang?

Jika saya memiliki satu set batasan linier di mana setiap kendala memiliki paling banyak (katakanlah) 4 variabel (semua nonnegatif dan dengan koefisien {0,1} kecuali untuk satu variabel yang dapat memiliki koefisien -1), apa yang diketahui tentang solusi ruang? Saya kurang peduli dengan solusi yang efisien (meskipun harap tunjukkan jika ada yang diketahui) daripada dengan mengetahui seberapa kecil minimum fungsi tujuan dapat, sebagai fungsi dari jumlah variabel dan jumlah kendala, dan jumlah variabel per paksaan.

Lebih konkretnya, programnya seperti

meminimalkan t
  tunduk pada
semua i, x_i adalah bilangan bulat positif
x1 + x2 + x3 - t <0
x1 + x4 + x5 - t <0
...
x3 + x6 - t ≥ 0
x1 + x2 + x7 - t ≥ 0
...

Jika pertanyaan konkret diperlukan, maka apakah itu solusi minimum yang mematuhi t <= O (maks {# variabel, # kendala}), dengan konstanta dalam O () tergantung pada sparseness? Tetapi bahkan jika jawabannya tidak, saya lebih tertarik untuk mengetahui buku teks atau kertas apa yang akan dipelajari untuk diskusi tentang masalah-masalah seperti itu, dan jika ada bidang studi yang ditujukan untuk hal-hal semacam ini, tetapi saya tidak tahu persyaratan untuk mencari. Terima kasih.

Pembaruan: Dengan refleksi lebih lanjut (dan memikirkan pengurangan 3SAT ke ILP yang agak sederhana, yang menggunakan batasan dengan tiga variabel), saya menyadari bahwa masalah koefisien sangat penting (jika akan ada algoritma yang efisien). Lebih tepatnya, semua variabel x_i memiliki 0 atau 1 koefisien (dengan paling banyak tiga 1 koefisien dalam satu kendala), dan semua variabel t memiliki koefisien -1, dan semua perbandingan memiliki variabel di sebelah kiri dan 0 di sebelah kanan. Saya memperbarui contoh di atas untuk memperjelas.

Jawaban untuk ini (setidaknya untuk pertanyaan konkret tentang linear mengikat solusi) adalah tidak. Ini adalah bagian dari makalah berikut: http://arxiv.org/abs/1011.3493 . Teorema 5.1 adalah motivasi untuk pertanyaan ini.

Contoh tandingannya adalah ini:

kasus dasar:

a_1 '+ b_1' - t ≥ 0
a_1 '' + b_1 '' - t ≥ 0
a_1 + b_1 '- t ≤ -1
a_1 '+ b_1' '- t ≤ -1

kasus rekursif:

a_n '+ b_n' + a_ {n-1} - t ≥ 0
a_n '' + b_n '' + a_ {n-1} - t ≥ 0
a_n + b_n '+ a_ {n-1}' '- t ≤ -1
a_n '+ b_n' + a_ {n-1} '' - t ≤ -1

dan mengharuskan mereka semua untuk tidak negatif.

Anda dapat membuktikan dengan induksi bahwa setiap solusi nyata harus memenuhi a_n ''> = a_n + 2 ^ n. Kami mengubah "<0" -kualitas sama menjadi "≤ -1" karena setiap solusi integer memenuhi "≤ -1" jika dan hanya jika memenuhi "<0".

Jadi, moralnya adalah bahwa n ketidaksetaraan dari bentuk ini dapat memiliki sifat bahwa semua solusi bilangan bulat memiliki setidaknya satu bilangan bulat setidaknya eksponensial dalam n, tentu saja tidak dibatasi secara linear seperti yang kita duga sebelumnya.

Jika matriks koefisien benar - benar unimodular , maka solusi yang efisien ada melalui pemrograman linier biasa. Ini berlaku untuk ILP apa pun, tidak hanya yang jarang - meskipun Anda lebih mungkin dapat mengeksploitasi properti ini untuk ILP yang jarang seperti milik Anda.

Saya menduga Anda mungkin sudah mengetahui hal ini, jadi izinkan saya mencoba dan memberi Anda jawaban yang lebih baik. Sebelum terlalu memikirkan hal-hal spesifik, jawaban untuk pertanyaan konkret Anda adalah "ya", ada batasan. Perpotongan n ketidaksetaraan dalam variabel m mendefinisikan polytope. Karena koefisien berperilaku sangat baik, kita dapat menentukan batas atas pada dimensi koordinat titik-titiknya dengan sedikit aritmatika. Ini memberi Anda batas atas yang sangat mudah pada dimensi titik integer mana pun dalam polytope, dan dengan demikian pada solusi untuk program integer Anda. Sudahkah Anda mencoba ini?

Masalah Anda khususnya memiliki sedikit struktur (saya ingin tahu, dari mana asalnya?) Jadi saya yakin bahwa kita bisa lebih tepat daripada ini jika kita membahasnya lebih lanjut.

Sekarang, untuk pertanyaan yang lebih umum tentang mencari informasi tentang topik ini. Ini adalah jenis masalah yang secara tradisional jatuh dalam teori pemrograman linier dan integer, bagian dari pemrograman matematika.

Ini adalah bidang penelitian yang cukup aktif, tetapi sebagian besar pekerjaan dilakukan di departemen riset operasi di bawah judul "optimisasi" dan "pemrograman matematika" alih-alih ilmu komputer. Ada banyak buku pelajaran yang tersedia membahas topik tersebut. Anda mungkin mempertimbangkan yang oleh Wolsey , yang kami gunakan di Berkeley. Berikut adalah daftar mitos dan counterexamples yang kurang digunakan oleh Greenberg, termasuk program integer dan linear, yang dapat memberi Anda gambaran tentang hal-hal apa yang dipertimbangkan orang dalam menganalisis masalah-masalah tersebut. Wolsey padat, tetapi tempat yang cukup baik untuk memulai - ada banyak teknik untuk menganalisis ILP dan meningkatkan formulasi masalah sampai titik efisiensi.

Izinkan saya menambahkan bahwa jika Anda mengejar pendekatan naif yang saya sarankan, dengan menganalisis geometri polytope, istilah untuk mencari akan berkaitan dengan membatasi ukuran koordinat dari simpul polytope. Istilah-istilah ini muncul lebih sering dalam literatur matematika tentang polytopes.

Anda mungkin menemukan akun yang menarik ini:

http://en.wikipedia.org/wiki/Polyhedral_combinatorics

dan khususnya artikel oleh G. Ziegler:

Ceramah tentang 0-1 polytopes

di:

Kalai, Gil; Ziegler, Günter M. (2000), Polytopes: Combinatorics and Computation, Seminar DMV, 29, Birkhäuser, ISBN 9783764363512.