Kompleksitas yang diketahui paling cepat untuk algoritma ILP kombinasi?

Saya bertanya-tanya, apa algoritma yang paling terkenal, dalam hal notasi Big- , untuk menyelesaikan Integer Linear Programming? $O$

Saya tahu bahwa masalah adalah -Lengkap, jadi aku tidak mengharapkan apa-apa polinomial. Dan saya tahu ada banyak heuristik dan yang digunakan dalam aplikasi praktis seperti CPLEX, tapi saya lebih tertarik pada formalitas, kompleksitas terburuk dari algoritma yang tepat. $NP$

Beberapa - masalah lengkap memiliki algoritma dalam waktu mana dan adalah polinomial. Vertex cover, set independen dan 3SAT termasuk dalam kategori ini, tetapi secara umum-SAT dan TSP tidak (sejauh yang kita tahu). $NP$ $O(b^n p(n))$ $1 < b < 2$ $p$

Bisakah pernyataan seperti itu dibuat tentang Pemrograman Integer, atau sub-instance tertentu?

Jika ada yang punya referensi untuk masalah terkait dari Aritmatika Presburger Presifier Gratis, saya akan sangat tertarik juga.

algorithms complexity-theory reference-request np-complete integer-programming Ya ampun
sumber

Aardal, Karen, Robert Weismantel, dan Laurence A. Wolsey. "Pendekatan non-standar untuk pemrograman integer." Matematika Terapan Diskrit 123.1 (2002): 5-74. memberi banyak referensi. Mungkin Anda dapat menemukan jawabannya dengan melihat ini, atau menelusuri apa yang dikutip oleh makalah baru ini. Lihatlah Bagian 2 secara khusus.

Juho

Apa perbedaan antara

dan

O ({1.1}^{n})

$O(1.1^{n})$

O (99^{n})

$O(99^{n})$

greybeard

@ Greybeard, tidak banyak untuk P vs NP, tetapi banyak dalam hal traktabilitas kehidupan nyata, tergantung pada konstanta, itu membuat perbedaan besar.

jmite

Saya berharap saya berharap untuk pengingat di muka yang diberikan

dan

, perbedaan dalam

menghasilkan set fungsi yang berbeda, sementara satu di

tidak dan akibatnya akan diabstraksi. .

O (b^{n})

$O(b^n)$

O (c n)

$O(cn)$

b

$b$

c

$c$

greybeard

@jmite Selesai. Apakah referensi penggunaan apa pun untuk Anda, atau apakah Anda dapat menemukan beberapa informasi baru?

Juho

Dari apa yang saya tahu dengan mencari, survei yang pasti tampaknya adalah:

Aardal, Karen, Robert Weismantel, dan Laurence A. Wolsey. "Pendekatan non-standar untuk pemrograman integer." Matematika Terapan Diskrit 123.1 (2002): 5-74.

Secara khusus, Bagian 2.1 membahas pemrograman integer dalam dimensi terbatas, dan menyajikan algoritma karena penulis yang berbeda. Memang, survei mencantumkan banyak referensi, dan membahas beberapa implementasi praktis.

Untuk sejumlah variabel, pemrograman linear integer adalah waktu polinomial yang dapat dipecahkan oleh algoritma Lenstra.

Juho
sumber

baik, tetapi apa algoritma tercepat yang diketahui?

vzn

@vzn Saya tidak tahu, ini paling banyak jawaban yang mencakup "sub-instance tertentu".

Juho

Kompleksitas yang diketahui paling cepat untuk algoritma ILP kombinasi?

Jawaban: