• Pengoptimalan Bilangan Bulat

Masalah pengoptimalan linear yang mengharuskan beberapa variabel menjadi bilangan bulat disebut Program Bilangan Bulat Campuran (MIP).

Variabel ini dapat muncul dengan beberapa cara:

• Variabel bilangan bulat yang mewakili jumlah item, seperti mobil atau rangkaian televisi, dan masalahnya adalah menentukan jumlah setiap item yang akan diproduksi untuk memaksimalkan keuntungan.
  Biasanya, masalah tersebut dapat disiapkan sebagai masalah pengoptimalan linear standar, dengan persyaratan tambahan bahwa variabel harus berupa bilangan bulat. Bagian berikutnya menunjukkan contoh jenis masalah ini.

• Variabel Boolean yang mewakili keputusan dengan nilai 0-1.
  Sebagai contoh, pertimbangkan masalah yang melibatkan penetapan pekerja (lihat Penetapan). Untuk menyiapkan jenis masalah ini, Anda dapat menentukan variabel Boolean x_i,j yang sama dengan 1 jika pekerja i ditetapkan ke tugas j, dan 0 jika sebaliknya.

Untuk mendapatkan penjelasan yang baik tentang pengoptimalan bilangan bulat, sebaiknya baca Cookbook pemodelan Mosek.

Alat

Google menyediakan beberapa cara untuk menyelesaikan masalah MIP:

• MPSolver: Wrapper untuk beberapa pemecah MIP pihak ketiga, yang menggunakan teknik cabang dan ikatan standar.
• Pemecah masalah CP-SAT: Pemecah pemrograman batasan yang menggunakan metode SAT (kepuasan).
• Pemecah masalah CP asli: Pemecah pemrograman kendala.

Catatan: Google juga menawarkan cloud API untuk resolver MILP melalui AI Workshop. Jika tertarik untuk menggunakan pemecah masalah tersebut, Anda dapat mendaftar untuk mendapatkan akses.

Pemecah masalah mana yang harus saya gunakan?

Tidak ada aturan kuat untuk memutuskan apakah akan menggunakan pemecah MIP atau pemecah CP-SAT. Sebagai panduan kasar:

• Pemecah masalah MIP lebih cocok untuk masalah yang dapat disiapkan sebagai LP standar, tetapi dengan variabel bilangan bulat arbitrer, seperti contoh pertama di atas.
• Pemecah masalah CP-SAT lebih cocok untuk masalah yang sebagian besar variabelnya bersifat Boolean, seperti contoh kedua di atas.

Untuk MIP standar yang memiliki variabel bilangan bulat dan Boolean, sering kali tidak ada perbedaan yang jelas dalam kecepatan antara kedua pemecah masalah, sehingga pilihan Anda mungkin bergantung pada preferensi pribadi.

Untuk contoh yang menggunakan pemecah masalah MIP dan CP-SAT, lihat Menyelesaikan Masalah Tugas dan bagian tugas lainnya.

Cara lain untuk menyelesaikan masalah pemrograman bilangan bulat adalah menggunakan pemecah alur jaringan.
Lihat Penetapan sebagai Masalah Alur Biaya Min untuk contoh.
Untuk soal yang dapat disiapkan sebagai alur jaringan, pemecah alur biaya minimum dapat lebih cepat daripada pemecah MIP atau CP-SAT. Namun, tidak semua MIP dapat disiapkan dengan cara ini.