Lingkungan uji program bilangan bulat
Selesaikan program linear bilangan bulat kecil dengan branch-and-bound eksak dan lihat setiap simpul pencarian. Titik terbaik dilaporkan terbukti optimal hanya jika seluruh pohon pencarian telah dijelajahi.
Program dibatasi hingga 4.000 karakter dan 40 baris, 8 variabel, serta 8 kendala yang memuat dua variabel atau lebih; batas simpul antara 1 hingga 5.000 dan pencarian juga berhenti setelah 3.000.000 langkah aritmetika eksak. Semua dihitung di perangkat Anda dalam proses latar dengan batas 15 detik. Unduhan berupa laporan JSON dan CSV simpul. Baris pertama: maximize atau minimize dan fungsi objektif. Lalu tulis satu kendala per baris. Maksimal 4.000 karakter. Tinjau pengaturan sebelum menjalankan.
Hasil Anda
Lingkungan uji program bilangan bulat
- Tuliskan fungsi objektif pada baris pertama, seperti maximize 5x + 4y.
- Tambahkan satu kendala per baris, batas seperti x, y >= 0, dan baris opsional seperti integer x atau binary z.
- Atur batas simpul lalu jalankan pencarian.
- Baca status, solusi terbaik sementara, batas terbaik, dan celahnya; lalu unduh laporan JSON atau CSV simpul.
Yang perlu diketahui
Program dibatasi hingga 4.000 karakter dan 40 baris, 8 variabel, serta 8 kendala yang memuat dua variabel atau lebih; batas simpul antara 1 hingga 5.000 dan pencarian juga berhenti setelah 3.000.000 langkah aritmetika eksak. Semua dihitung di perangkat Anda dalam proses latar dengan batas 15 detik. Unduhan berupa laporan JSON dan CSV simpul.
Branch-and-bound
Setiap simpul menyelesaikan relaksasi linear secara eksak dengan metode simpleks. Variabel bilangan bulat yang bernilai pecahan dibagi menjadi dua cabang: x <= floor (pembulatan ke bawah) dan x >= ceiling (pembulatan ke atas). Simpul dipangkas jika relaksasinya tidak layak atau tidak dapat mengungguli titik bilangan bulat terbaik yang ditemukan. Metode: Wolsey, Integer Programming, edisi ke-2, bab 7 (2020).
Arti “terbukti”
Jika setiap simpul telah diselesaikan atau dipangkas dengan batas eksak, solusi terbaik sementara terbukti optimal atau masalah terbukti tidak layak. Jika batas simpul atau anggaran langkah menghentikan pencarian lebih awal, solusi itu hanya titik terbaik yang ditemukan sejauh ini; laporan menampilkan batas terbaik dan selisih di antara keduanya.
Aturan input
Secara default, semua variabel dianggap bilangan bulat. Jika Anda mencantumkan beberapa variabel dengan deklarasi integer, misalnya integer x, y, variabel yang dicantumkan itu tetap bilangan bulat, sedangkan variabel yang tidak dicantumkan menjadi kontinu. Kendala satu variabel menjadi batas. Relaksasi yang tak terbatas menghentikan pencarian karena program bilangan bulat mungkin tak terbatas atau tidak layak.