Apa itu Python-MIP

Python-MIP, singkatan dari Mixed Integer Programming, adalah sebuah perpustakaan Python OSS yang dirancang untuk memecahkan masalah optimisasi yang kompleks.

Di balik antarmuka Python, Python-MIP didukung oleh perpustakaan C++ bernama Cbc (Coin-or branch and cut), sebuah perpustakaan yang sangat dioptimalkan yang terkenal karena kemampuannya dalam memecahkan masalah pemrograman bilangan bulat campuran. Kombinasi antara performa Cbc dan kemudahan Python dapat menangani berbagai tugas optimisasi.

Python-MIP tidak hanya terbatas pada Mixed-Integer Linear Programming. Perpustakaan ini juga mampu menangani masalah Continuous Linear Programming. Kelebihan ini membuat Python-MIP cocok untuk berbagai kasus penggunaan, mulai dari penelitian operasional dan logistik hingga pembelajaran mesin dan ilmu data.

Fitur Utama Python-MIP

Perpustakaan Python-MIP menonjol karena beberapa fitur utama yang menjadikannya alat yang sangat baik untuk tugas optimisasi.

• Mixed-Integer Linear Programming (MILP) dan Continuous Linear Programming (LP)
  Python-MIP tidak terbatas pada satu jenis masalah optimisasi saja. Perpustakaan ini dapat menangani masalah MILP dan LP, menjadikannya alat yang serbaguna yang dapat menyesuaikan diri dengan persyaratan berbagai tugas optimisasi.

• Kemudahan Penggunaan
  Salah satu daya tarik utama Python-MIP adalah antarmukanya yang "Pythonic". Perpustakaan ini menyediakan antarmuka yang tingkat tinggi dan mudah digunakan yang dirancang agar mudah digunakan oleh pengguna. Hal ini mengurangi hambatan bagi pengguna baru, sehingga memudahkan pemula untuk mulai menggunakan perpustakaan ini.

• Performa Tinggi
  Meskipun Python-MIP menyediakan antarmuka Python yang sederhana dan mudah digunakan, di balik layar, perpustakaan ini didukung oleh perpustakaan Cbc. Ini adalah perpustakaan C++ yang sangat dioptimalkan yang dirancang khusus untuk memecahkan masalah pemrograman bilangan bulat campuran. Dengan memanfaatkan kekuatan Cbc, Python-MIP menyediakan alat berperforma tinggi yang dapat menangani masalah yang besar dan kompleks dengan efisien.

• Fungsionalitas Callback
  Salah satu fitur lebih lanjut dari Python-MIP adalah fungsionalitas callback-nya. Ini memungkinkan pengguna untuk menyisipkan logika kustom ke dalam proses pemecahan, yang dapat digunakan untuk memodifikasi perilaku solver. Hal ini memberikan tingkat fleksibilitas yang tinggi, memungkinkan pengguna untuk menyesuaikan proses pemecahan sesuai dengan kebutuhan spesifik mereka.

Perbandingan dengan PuLP

Meskipun PuLP adalah perpustakaan Python terkenal lainnya untuk optimisasi, ada beberapa alasan mengapa yang lebih suka Python-MIP. Keunggulan utama Python-MIP adalah performanya. Karena menggunakan solver Cbc sebagai dasarnya, Python-MIP sering kali memiliki kinerja yang lebih baik daripada PuLP, terutama untuk masalah yang lebih besar dan lebih kompleks. Selain itu, antarmuka Python-MIP dianggap lebih "Pythonic" dan intuitif dibandingkan dengan PuLP, sehingga lebih mudah digunakan bagi pengembang Python. Terakhir, fungsionalitas callback Python-MIP menyediakan alat yang kuat untuk kustomisasi yang tidak tersedia di PuLP.

Jenis Masalah Optimisasi yang Dapat Diselesaikan oleh Python-MIP

Python-MIP mampu menyelesaikan berbagai jenis masalah optimisasi, termasuk:

• Linear Programming (LP)
• Mixed-Integer Linear Programming (MILP)

Studi Kasus

Kita akan mempertimbangkan sebuah studi kasus tentang mengoptimalkan jaringan logistik untuk sebuah perusahaan manufaktur besar.

Deskripsi Masalah

Perusahaan tersebut mengoperasikan beberapa fasilitas produksi dan melayani jaringan pengecer yang luas. Tujuannya adalah meminimalkan biaya total transportasi dari fasilitas produksi ke pengecer. Masalah ini melibatkan variabel dan batasan berikut:

• Fasilitas produksi, masing-masing dengan kapasitas produksi tertentu
• Pengecer, masing-masing dengan permintaan tertentu
• Biaya transportasi dari setiap fasilitas ke setiap pengecer
• Permintaan dari setiap pengecer harus dipenuhi
• Total produksi di setiap fasilitas tidak boleh melebihi kapasitasnya

Formulasi Masalah

Masalah ini dapat dirumuskan sebagai masalah MILP. Fungsi tujuan dan batasan dapat dijelaskan sebagai berikut (dengan c_{ij} adalah biaya pengiriman dari fasilitas i ke pengecer j, x_{ij} adalah jumlah yang dikirim dari i ke j, s_i adalah pasokan di fasilitas i, dan d_j adalah permintaan di pengecer j):

Minimalkan:

Dengan batasan:

Kode Python-MIP

Mari kita sekarang representasikan masalah dan selesaikan menggunakan Python-MIP.

from mip import Model, xsum, MINIMIZE, CONTINUOUS

# Define the data
costs = [[2, 4, 5, 2], [3, 1, 3, 2], [2, 3, 2, 3]]  # costs from each facility to each retailer
supply = [1000, 2000, 1500]  # supply capacity at each facility
demand = [500, 900, 1800, 300]  # demand at each retailer

# Create a new model
m = Model("Transportation", sense=MINIMIZE)

# Create variables
x = [[m.add_var(var_type=CONTINUOUS) for j in range(len(demand))] for i in range(len(supply))]

# Set the objective function
m.objective = xsum(costs[i][j]*x[i][j] for i in range(len(supply)) for j in range(len(demand)))

# Add constraints
for i in range(len(supply)):
    m += xsum(x[i][j] for j in range(len(demand))) <= supply[i]

for j in range(len(demand)):
    m += xsum(x[i][j] for i in range(len(supply))) >= demand[j]

# Solve the problem
m.optimize()

# Print the solution
for i in range(len(supply)):
    for j in range(len(demand)):
        if x[i][j].x >= 0.99:
            print(f"Ship {x[i][j].x} units from facility {i} to retailer {j}")

Ship 500.0 units from facility 0 to retailer 0
Ship 300.0 units from facility 0 to retailer 3
Ship 900.0 units from facility 1 to retailer 1
Ship 300.0 units from facility 1 to retailer 2
Ship 1500.0 units from facility 2 to retailer 2

Skrip dimulai dengan mendefinisikan data, kemudian membuat model dan mendefinisikan variabel, fungsi tujuan, dan batasan. Selanjutnya, pemanggilan fungsi optimize digunakan untuk menyelesaikan masalah. Solusi kemudian dicetak, menunjukkan bagaimana mengirimkan barang dari setiap fasilitas ke setiap pengecer untuk meminimalkan biaya transportasi.

Referensi

https://www.python-mip.com/