Ruang uji pengaturcaraan integer
Selesaikan program linear integer kecil dengan branch-and-bound tepat dan lihat setiap nod carian. Titik terbaik dilaporkan terbukti optimum hanya setelah seluruh pepohon diteroka.
Program dihadkan kepada 4,000 aksara dan 40 baris, 8 pemboleh ubah dan 8 kekangan dengan dua atau lebih pemboleh ubah; had nod ialah 1 hingga 5,000 dan carian turut berhenti selepas 3,000,000 langkah aritmetik tepat. Semua pengiraan dibuat pada peranti anda dalam proses latar dengan had 15 saat. Muat turun termasuk laporan JSON dan CSV nod. Baris pertama: maximize atau minimize bersama objektif. Kemudian satu kekangan pada setiap baris. Sehingga 4,000 aksara. Semak tetapan sebelum menjalankan.
Hasil anda
Ruang uji pengaturcaraan integer
- Tulis objektif pada baris pertama, seperti maximize 5x + 4y.
- Tambah satu kekangan pada setiap baris, batas seperti x, y >= 0, dan baris pilihan seperti integer x atau binary z.
- Tetapkan had nod dan jalankan carian.
- Baca status, penyelesaian terbaik semasa, batas terbaik dan jurang, kemudian muat turun laporan JSON atau CSV nod.
Apa yang akan berlaku
Program dihadkan kepada 4,000 aksara dan 40 baris, 8 pemboleh ubah dan 8 kekangan dengan dua atau lebih pemboleh ubah; had nod ialah 1 hingga 5,000 dan carian turut berhenti selepas 3,000,000 langkah aritmetik tepat. Semua pengiraan dibuat pada peranti anda dalam proses latar dengan had 15 saat. Muat turun termasuk laporan JSON dan CSV nod.
Branch-and-bound
Setiap nod menyelesaikan relaksasi linear dengan tepat menggunakan kaedah simpleks. Pemboleh ubah integer yang nilai relaksasinya pecahan dipecahkan kepada dua cabang, x <= floor dan x >= ceiling. Nod dipangkas apabila relaksasinya tidak berdaya maju atau tidak dapat mengatasi titik integer terbaik yang ditemukan. Kaedah: Wolsey, Integer Programming, edisi ke-2, bab 7 (2020).
Maksud terbukti
Apabila setiap nod diselesaikan atau dipangkas menggunakan batas tepat, penyelesaian terbaik semasa terbukti optimum atau masalah terbukti tidak berdaya maju. Jika had nod atau bajet langkah menghentikan carian lebih awal, penyelesaian semasa hanya titik terbaik yang ditemukan setakat ini; laporan memberikan batas terbaik dan jurang antaranya.
Peraturan input
Semua pemboleh ubah dianggap integer. Jika anda menyenaraikan sesetengahnya dengan integer x, y, pemboleh ubah yang disenaraikan itu kekal integer, manakala yang lain menjadi selanjar. Kekangan satu pemboleh ubah menjadi batas. Jika relaksasi tidak terbatas, carian dihentikan kerana program integer mungkin tidak terbatas atau tidak berdaya maju.