Menemukan solusi sudut yang tepat untuk pemrograman linier menggunakan metode titik interior

Algoritma simpleks berjalan dengan rakus di sudut-sudut polytope untuk menemukan solusi optimal untuk masalah pemrograman linier. Alhasil, jawabannya selalu merupakan sudut dari polytope. Metode titik interior berjalan di bagian dalam polytope. Akibatnya, ketika seluruh bidang polytope optimal (jika fungsi objektifnya sejajar dengan bidang), kita bisa mendapatkan solusi di tengah bidang ini.

Misalkan kita ingin menemukan pojok polytope sebagai gantinya. Sebagai contoh jika kita ingin melakukan pencocokan maksimum dengan menguranginya ke pemrograman linear, kita tidak ingin mendapatkan jawaban yang terdiri dari "pencocokan berisi 0,34% dari tepi XY dan 0,89% dari tepi AB dan ...". Kami ingin mendapatkan jawaban dengan 0 dan 1 (yang simpleks akan berikan kepada kami karena semua sudut terdiri dari 0 dan 1). Apakah ada cara untuk melakukan ini dengan metode titik interior yang menjamin untuk menemukan solusi sudut yang tepat dalam waktu polinomial? (misalnya mungkin kita dapat memodifikasi fungsi tujuan untuk mendukung sudut)

Anda mungkin ingin membaca koran:

Sanjay Mehrotra, Pada menemukan solusi titik menggunakan metode titik interior, Aljabar Linier dan Aplikasinya, Volume 152, 1 Juli 1991, Halaman 233-253, ISSN 0024-3795, 10.1016 / 0024-3795 (91) 90277-4. tautan artikel sciencedirect

Sementara pertanyaan secara umum masuk akal, aneh bahwa Anda memilih pencocokan maksimum sebagai contoh, karena ada banyak algoritma (aliran maksimum untuk pencocokan bipartit kardinalitas maks, algoritma Edmonds untuk pencocokan non-bipartit, dan algoritma Hongaria untuk pencocokan bipartit berat maksimum) itu semua akan memberikan solusi integer vertex untuk masalah tersebut.

Karena kurangnya detail, ini hanyalah komentar yang lebih panjang:

Algoritma waktu polinomial Karmarkar hanya bergerak mendekati tepi. Pada akhirnya, ia menemukan solusi dasar yang cocok (misalnya sudut) yang optimal menggunakan skema pemurnian ¹. Anda dapat menggunakan ini atau teknik serupa untuk pindah ke sudut dari pesawat.

¹ Saya tidak bisa melihatnya di koran asli Karmarkar . Referensi saya adalah "Lineare Optimierung und Netzwerkoptimierung" (Inggris: Optimasi linear dan jaringan) oleh Hamacher dan Klamroth yang memiliki teks berbahasa Jerman dan Inggris secara berdampingan.

Ya, ada metode sederhana dan saya telah menerapkannya dalam C ++ untuk menggabungkan kecepatan metode titik interior dengan keakuratan metode simpleks (menggunakan perbaikan berulang dari kebalikan dari matriks dasar saya dapat mencapai akurasi 1 bagian dalam 10 ^ 15 dan lebih baik pada matriks kendala padat dengan lebih dari 1000 variabel dan kendala).

Kuncinya ada pada metode simpleks yang Anda gunakan. Asumsikan bahwa metode simpleks memiliki mekanisme untuk refactoring basis (misalnya setelah kesalahan pembulatan kumulatif membuatnya perlu), dan bahwa metode refactorization ini hanya menciptakan kembali matriks invers dasar untuk basis yang berisi semua daftar variabel dasar yang diinginkan. Lebih jauh lagi berasumsi bahwa bahkan jika basis yang diinginkan tidak dapat diciptakan kembali secara penuh, bahwa algoritma simpleks dapat melanjutkan dari basis yang mengandung 95% dari basis target, maka jawabannya sangat sederhana.

Yang harus Anda lakukan adalah mengambil solusi dari metode titik interior Anda, menghilangkan variabel yang nilai solusi utamanya dinyatakan nol oleh kelonggaran komplementer, dan diberi ukuran dasar dalam masalah simpleks b, ambil b variabel dalam interior titik solusi dengan nilai-nilai terbesar (atau sebanyak ada nilai-nilai non-nol jika itu kurang dari b), dan refactor basis simpleks untuk mengandung variabel-variabel b. Kemudian lanjutkan metode simpleks hingga terpecahkan. Karena Anda memulai masalah simpleks mendekati selesai, ini biasanya sangat cepat.