INTEGER PROGRAMMING

Dalam masalah integer programming, jika model mengharapkan semua variabel basis bernilai integer (bulat positif atau nol), dinamakan pure all integer programming. Jima model hanya mengharapkan variabel tertentu bernilai integer, dinamakan mixed integer programming. Dan jika model hanya mengharapkan nilai nol atau satu untuk variabelnya, dinamakan zero one integer programming.
a. Pendekatan pembulatan
Suatu pendekatan yang sederhana dalam menyelesaikan masalah integer programming adalah dengan membulatkan nilai variabel keputusan yang diperoleh melalui LP. Pendekatan ini mudah dan praktis dalam usaha, waktu, dan biaya yang diperlukan untuk memperoleh solusi. Bahkan pendekatan pembulatan merupakan cara yang efektif untuk masalah integer programming. Yang besar dimana biaya perhitungan sangat tinggi atau untuk masalah dimana nilai-nilai solusi variabel keputusan besar.
b. metode grafik
masalah yang hanya melibatkan dua variable dapat diselesaikan secara grafik. Pendekatan ini identik dengan metode grafik linear programming kecuali solusi optimum harus memenuhi persyaratan bilangan bulat. Pendekatan yang termudah untuk menyelesaikan masalah integer programming dua dimensi adalah dengan menggunakan kertas grafik dan mengambarkan sekumpulan titik integer dalam ruang solusi layak.
c. metode gomory (cutting plane algorithm)
suatu prosedur sistematik untuk memperoleh solusi integer optimum terhadap pure integer programming pertama kali dikemukakan oleg R.E Gomory pada tahun 1958. Langkah-langkah prosedur gomory adalah:
• Sewlesaikan integer programming menggunakan metode simpleks jika masalahnya sederhana diselesaikan dengan pendekatan grafik sehingga pendekatan gomory kurang efisien.
• Periksa solusi optimum, jika variabel basis memiliki nilai integer, solusi optimum integer telah diperoleh dan proses solusi berakhir. Jika satu atau lebih variable basis memiliki nilai pecah terus ketahap selanjutnya.
• Buat suatu kendala gomory (suatu bidang pemotong atau cuttingplane) dan cari solusi optimum selalui prosedur dual simpeks.
d. metode branch & bound
metode ini diperkenalkan oleh and dan doig, dan dikembangkan lebih lanjut oleh little dan peneliti lainnya. Teknik ini dapat diterapkan untuk masalah pure maupun mixed integer programming. Langkah untuk metode maksimasi adalah:
• Selesaikan masalah linear programming dengan metode simpleks biasa tanpa pembatas bilangan bulat.
• Teliti solusi uptimumnya. Jika variabel basis yang diharapkan buat maka telah tercapai. Jika satu atau lebih variabel basis yang diharapkan bulat ternyata tidak bulat, lanjutkan langkah selanjutnya.
• Nilai solusi pecah yang layak dicabangkan kedalam sub-sub masalah. Tujuannya adalah untuk menghilangkan solusi kontinu yang tidak memenuhi persyaratan bulat dari masalah ini.
• Nilai solusi optimum kontinu fungsi tujuan ditetapkan sebagai batas atas. Solusi bulat terbaik menjadi batas bawah. Sub-sub masalah memiliki batas atas kurang dari batas bawah yang suatu solusi bulat layak adalah sama baik atau lebih baik dari batas atas untuk setiap submasalah yang dicari.

Sumber;
Mulyono. Sri, S.E.,M.Sc. Riset Operasional. Fakultas Ekonomi Universitas Indonesia. 2002.

Programa bilangan bulat

Merupakan bentuk lain dari programa linear (LP) dimana asumsi divisibilitasnya melemah atau hilang sama sekali. Bentuk ini muncul karena dalam kenyataannya tidak semua variabel keputusan dapat berupa bilangan pecahan. Asumsi divibilitas melemah, artinya sebagian dari nilai variabel keputusan harus berupa bilangan bulat (integer) dan sebagian lainnya boleh berupa bilangan pecahan. Persoalan integer programming (IP) dimana hanya sebagian dari variabel keputusan yang harus integer disebut sebagai persoalan IP campuran. Apabila seluruh variabel keputusan dari suatu persoalan programa linear (LP) harus berharga integer, maka persoalan tersebut sebagai persoalan programa bilangan bulat (IP) murni.

Menyelesaikan IP dengan teknik Cutting Plane
Pendekatan yang dilakukan dalam teknik cutting plane adalah dengan membuat pembatas tambahan yang memotong ruang fisibel dari LP relaksasi sehingga dapat mengeliminasi solusi yang tidak integer. Proses pemotongan akan terus berlangsung sehingga diperoleh solusi dengan seluruh variabel (yang dikehendaki) berharga integer. Keberhasilan teknik ini sangat terbatas, bergantung pada struktur persoalan yang dihadapi. Artinya, hanya persoalan tertentu yang dapat diselesaikan dengan teknik ini. Karena itu, sekarang teknik ini hamper tidak pernah digunakan lagi.

Sumber:
Dimyanti, Ahmad. Operations Research. Model-model pengambilan keputusan. Sinar Baru Algensindo. Bandung. 1999.