Ada banyak cara yang berbeda untuk mendefinisikan dan memecahkan masalah optimasi. Anda dapat misalnya menggunakan algoritma serakah, pemrograman kendala, pemrograman bilangan bulat campuran, algoritma genetika atau pencarian lokal. Dalam posting ini, kami menyelami pemrograman kendala. Sebagai contoh, masalah pewarnaan graf digunakan untuk mengilustrasikan cara kerja pemrograman kendala.

Jika Anda memerlukan pengenalan masalah pengoptimalan dan pencarian heuristik, Anda dapat membaca postingan di bawah ini.

Pewarnaan Graf

Mari kita mulai dengan masalah pewarnaan graf. Masalah ini digunakan di seluruh posting untuk mengilustrasikan konsep pemrograman kendala.

Untuk peta tertentu, Anda ingin mewarnai setiap negara. Anda memiliki jumlah warna yang tidak terbatas. Tidak diperbolehkan memberi warna yang sama pada negara yang berdekatan. Berapa jumlah warna terendah yang Anda butuhkan untuk mengisi peta?

Variabelnya adalah warna yang Anda berikan pada negara. Kendalanya adalah tidak boleh memberikan warna yang sama pada negara yang berdekatan . Tujuannya adalah untuk meminimalkan jumlah warna yang digunakan .

Kedengarannya mudah? Dalam prakteknya bisa sulit! Ini adalah bagian dari solusi untuk Afrika:

Cara lain untuk memvisualisasikan masalah ini adalah dengan menggunakan simpul dan sisi. Negara-negara yang berdekatan terhubung dengan keunggulan. Verteks sesuai dengan negara. Ini adalah contoh sebelumnya yang diilustrasikan dengan cara ini:

Apa itu Pemrograman Kendala?

Ide utama dari constraint programming (CP) adalah menggunakan constraint untuk mengurangi sekumpulan nilai yang dapat diambil oleh setiap variabel. Di CP, program (atau pemecah) melacak nilai yang dapat muncul. Setelah setiap gerakan, ruang pencarian dipangkas. Ini berarti bahwa nilai-nilai yang tidak dapat terjadi lagi akan dihapus. Dapat terjadi bahwa tidak ada lagi langkah yang memungkinkan sementara pemecah belum menemukan solusi yang layak. Dalam hal ini, pemecah memulai dari titik sebelumnya di mana ia membuat keputusan dan mempertimbangkannya kembali.

Dasar

Fokus CP adalah pada kelayakan, bukan optimalitas. Setelah keputusan, pemecah memeriksa kelayakan dan memangkas ruang pencarian. Pada gambar di bawah ini Anda dapat melihat pemecah CP dasar. Bagian besar adalah pencarian dan penyimpanan kendala, yang akan saya jelaskan secara rinci nanti. Singkatnya: pencarian adalah tempat pengambilan keputusan, dan penyimpanan batasan berisi semua nilai variabel yang mungkin di penyimpanan domain dan menahan batasan. Perpindahan dilakukan (mis. Anda mewarnai negara dengan warna merah), dan di penyimpanan kendala, penyimpanan domain dipangkas berdasarkan perpindahan tersebut. Ada juga feasibility check, artinya bila perpindahan tidak memungkinkan karena melanggar satu atau lebih constraint, maka perlu dilakukan roll back (kegagalan).

Pada contoh di bawah ini, Anda dapat melihat bahwa saat Anda mewarnai suatu negara dengan warna merah, untuk negara yang terhubung dengan warna merah harus dihapus dari penyimpanan domain, karena pemindahan tersebut tidak mungkin dilakukan lagi.

Anda mungkin bertanya-tanya: Bagaimana pemrograman kendala dapat menemukan solusi yang optimal? Khususnya pada masalah pewarnaan graf, sangat mudah untuk menemukan solusi yang layak. Yang paling mudah adalah dengan memberikan warna yang berbeda pada setiap negara. Itu adalah solusi yang layak tetapi jauh dari optimal. Ada berbagai cara untuk menyelesaikan ini. Salah satu contohnya adalah terus menyelesaikan masalah, dan menambahkan batasan bahwa solusi baru harus menggunakan warna yang lebih sedikit dari yang sebelumnya.

Mencari

Untuk pencarian, ada beberapa aturan bagus yang dapat Anda ikuti yang dapat meningkatkan pencarian secara drastis. Yang pertama adalah prinsip gagal pertama . Ini berarti Anda mencoba dulu di mana Anda kemungkinan besar akan gagal. Ini membuat segalanya lebih mudah pada akhirnya dan mengurangi pohon pencarian paling banyak. Dalam pewarnaan graf, lebih baik memulai dengan negara yang terhubung ke banyak negara lain, daripada negara yang tidak memiliki banyak koneksi:

Ini membantu, karena lebih sulit memberi warna pada negara ini jika Anda sudah mewarnai negara-negara sekitarnya. Kemungkinan besar ketika Anda tidak memulai dengan negara ini, Anda harus memberinya warna baru, yang ingin Anda hindari.

Ada berbagai jenis pencarian yang dapat Anda terapkan. Bergantung pada masalahnya, Anda dapat memilih yang terbaik (atau mencoba semuanya):

• Pelabelan variabel/nilai
  Dengan metode pencarian ini, Anda memulai dengan variabel. Dalam pewarnaan graf, negara adalah variabel dan warna adalah nilainya. Anda memilih variabel (negara) untuk ditetapkan selanjutnya dengan cara yang cerdas. Misalnya, Anda dapat memilih salah satu yang memiliki nilai serendah mungkin. Kemudian, Anda memilih nilai (warna) yang akan didapat variabel ini. Seringkali suatu nilai dipilih yang menyisakan sebanyak mungkin pilihan untuk variabel lain. Di bawah contoh mudah.

• Pelabelan nilai/variabel
  Cara lain untuk menangani pencarian adalah mulai dengan nilai. Anda memiliki warna dan Anda memilih negara untuk memberi warna ini. Ini justru kebalikan dari pelabelan variabel/nilai. Dalam soal pewarnaan graf, Anda dapat membuat kumpulan negara yang semuanya memiliki warna yang sama.
• Pemisahan domain
  Dengan pemisahan domain, Anda tidak menetapkan nilai ke variabel secara langsung. Sebagai gantinya, Anda membagi domain (kemungkinan nilai) dari sebuah variabel menjadi dua set atau lebih. Ini adalah komitmen yang lebih lemah daripada mengatakan: negara ini harus memiliki nilai ini, karena Anda masih memiliki pilihan untuk negara tersebut, salah satu nilai dari himpunan.
• Kerusakan simetri selama pencarian
  Kerusakan simetri dapat meningkatkan pencarian secara drastis. Anda perlu mencegah solusi simetris dieksplorasi, karena ini membuang-buang waktu. Secara teoritis, solusi simetris persis sama. Cara untuk mulai merusak simetri dalam pewarnaan graf adalah dengan memperbaiki warna untuk negara tertentu. Cara yang lebih baik untuk memecah simetri adalah dengan mengurutkan variabel (negara) atau dengan hanya memperhitungkan nilai saat ini (warna) dan satu nilai baru (warna).

• Pengacakan dan mulai ulang
  Dimungkinkan juga untuk mencoba solusi yang berbeda dalam urutan acak. Anda hanya memilih nilai variabel secara acak dan memeriksa apakah solusinya layak. Jika tidak ada solusi yang ditemukan setelah beberapa kali atau beberapa kali percobaan, Anda memulai ulang pencarian.

Toko kendala

Ada berbagai jenis kendala yang mungkin diterapkan di penyimpanan kendala. Batasan digunakan untuk pemeriksaan kelayakan dan pemangkasan penyimpanan domain. Batasan 'normal' adalah, dalam kasus pewarnaan graf, suatu negara yang terhubung ke negara lain tidak boleh memiliki warna yang sama. Namun ada kendala menarik lainnya yang bisa Anda buat berdasarkan masalah tersebut. Tujuan penambahan batasan adalah untuk memperketat masalah. Jika Anda membuat definisi yang lebih ketat, solusi optimal dapat ditemukan lebih cepat.

Berikut adalah berbagai jenis kendala yang dapat Anda tambahkan ke penyimpanan kendala:

• Kendala global
  Kendala paling penting yang dapat Anda tambahkan adalah kendala global. Kendala global membantu memangkas ruang pencarian dan dapat mendeteksi ketidaklayakan lebih awal. Kendala global membantu menyampaikan struktur masalah kepada pemecah secara langsung. Contoh kendala global adalah kendala alldifferent . Kendala ini berarti bahwa semua variabel harus memiliki nilai yang berbeda. Dalam pewarnaan graf, ketika empat negara semuanya terhubung, semuanya harus memiliki warna yang berbeda. Jika kami hanya memiliki tiga warna tersisa untuk negara-negara ini, solusinya tidak mungkin: kami dapat memutar kembali dan melaporkan kegagalan.

• Kendala redundan
  Kendala redundan adalah kendala yang tidak menambah nilai dalam mengecualikan solusi. Tetapi kendala redundan signifikan secara komputasi, karena mengurangi ruang pencarian. Kendala berlebihan menangkap sesuatu yang tidak mungkin tetapi tidak ditangkap dalam kendala. Contoh dalam pewarnaan graf: jumlah warna tidak boleh melebihi jumlah negara.
• Kendala pengganti
  Dengan menggabungkan kendala yang ada, Anda mendapatkan kendala pengganti. Batasan pengganti sangat membantu karena memberikan pandangan yang lebih global. Contohnya adalah menggabungkan batasan yang ada atau mengambil kombinasi linear dari batasan tersebut.
• Kendala tersirat
  Jenis kendala lain yang dapat Anda tambahkan adalah kendala tersirat. Memperoleh properti dari beberapa kendala yang ada memberikan kendala tersirat.

Apa hubungan antara CP dan MIP?

Anda mungkin pernah mendengar tentang pemrograman bilangan bulat campuran. Ini adalah teknik lain untuk memodelkan masalah optimisasi diskrit. MIP menggunakan berbagai cara untuk menemukan solusi terbaik untuk suatu masalah. Di bawah ini, Anda dapat membaca apa persamaan dan perbedaan antara CP dan MIP.

Apa itu pemrograman bilangan bulat campuran?

Pemrograman bilangan bulat campuran (MIP) adalah teknik optimisasi matematis yang melibatkan pencarian solusi optimal untuk suatu masalah dengan memecahkan sistem persamaan linier dan ketidaksetaraan yang mengandung variabel bilangan bulat dan kontinu. MIP berfokus pada optimalitas. Untuk memahami MIP dan matematika di baliknya dengan benar, penting untuk mengetahui cara kerja pemrograman linier dan algoritma simpleks. Baca artikel di bawah ini jika Anda ingin mendapatkan penyegaran tentang itu:

Pemecah MIP mengendurkan kendala dengan mengizinkan nilai kontinu untuk variabel bilangan bulat. Ini memungkinkan untuk menggunakan algoritma simpleks. Setelah itu, teknik lain digunakan untuk mencari solusi yang valid (nilai bilangan bulat untuk variabel bilangan bulat). Teknik-teknik ini berada di luar cakupan posting ini, tetapi jika Anda tertarik, Anda dapat mencari istilah seperti cabang dan ikatan, cabang dan potong dan potong bidang (misalnya potongan Gomory dan potongan polihedral).

Bagaimana CP dan MIP terkait

Secara matematis, masalah MIP dapat dirumuskan sebagai masalah CP (atau masalah CP sebagai masalah MIP). Jadi dalam pengertian itu, mereka sama. Tetapi karena cara mereka untuk mencapai solusi optimal berbeda, Anda mungkin ingin mempertimbangkan pendekatan mana yang terbaik untuk masalah spesifik Anda. MIP menggunakan relaksasi linier sedangkan CP menggunakan inferensi logis. CP bekerja dalam banyak kasus lebih cepat untuk masalah dengan banyak kendala 'atau', sementara MIP dapat menangani kendala 'dan' lebih cepat. Jika Anda menggunakan pemecah MIP komersial, mereka mungkin menerapkan teknik CP di dalamnya, seperti membuat batasan tingkat tinggi dan penalaran logis. MIP biasanya lebih fleksibel dan lebih dapat diandalkan. Jika Anda punya waktu, selalu baik untuk menguji teknik yang berbeda untuk melihat mana yang terbaik untuk masalah Anda.

Kesimpulan

Semoga Anda menikmati pengantar ini tentang pemrograman kendala. Ini adalah teknik yang berfokus pada kelayakan. Penyimpanan kendala dan cara mencari solusi adalah komponen kunci dari CP. Anda dapat meningkatkan formulasi model secara drastis jika Anda menambahkan berbagai jenis kendala ke penyimpanan kendala. Inti dari pemecah CP menyebar melalui kendala dan memeriksa apakah solusinya masih layak dan apakah pemangkasan mungkin dilakukan. Pemangkasan berarti menghapus nilai dari domain variabel. Pemecah CP dapat menemukan solusi optimal, jika Anda memberi mereka cukup waktu.

Pemrograman bilangan bulat campuran adalah cara lain untuk merumuskan masalah optimisasi diskrit. Ini menggunakan teknik aljabar untuk menemukan solusi optimal. Bergantung pada masalahnya, Anda dapat memilih apakah CP atau MIP lebih cocok.

Di bawah ini Anda dapat menemukan lebih banyak posting tentang pengoptimalan matematika.

Terkait