Pemrograman Integer Campuran: Panduan untuk Pengambilan Keputusan Komputasi

Riset operasi, ilmu menggunakan komputer untuk membuat keputusan yang optimal, telah digunakan dan diterapkan di banyak bidang perangkat lunak. Untuk memberikan beberapa contoh, perusahaan logistik menggunakannya untuk menentukan rute optimal untuk pergi dari titik A ke titik B, perusahaan listrik menggunakannya untuk menentukan jadwal produksi listrik, dan perusahaan manufaktur menggunakannya untuk menemukan pola staf yang optimal untuk pabrik mereka.

Hari ini, kita akan mengeksplorasi kekuatan riset operasi dengan menelusuri masalah hipotetis. Secara khusus, kami akan menggunakan pemrograman integer campuran (MIP) untuk menentukan pola kepegawaian yang optimal untuk pabrik hipotetis.

Algoritma Riset Operasi

Sebelum kita menyelami contoh masalah kita, akan sangat membantu untuk membahas beberapa konsep dasar dalam riset operasi dan memahami sedikit alat yang akan kita gunakan hari ini.

Algoritma Pemrograman Linier

Pemrograman linier adalah teknik riset operasi yang digunakan untuk menentukan hasil terbaik dalam model matematika di mana tujuan dan kendala dinyatakan sebagai sistem persamaan linier. Contoh model pemrograman linier mungkin terlihat seperti ini:

 Maximize a + b (objective) Subject to: a <= 2 (constraint 1) b <= 3 (constraint 2)

Dalam contoh yang sangat sederhana, kita dapat melihat bahwa hasil optimal adalah 5, dengan a = 2 dan b = 3. Meskipun ini adalah contoh yang agak sepele, Anda mungkin dapat membayangkan model pemrograman linier yang menggunakan ribuan variabel dan ratusan kendala .

Contoh yang baik mungkin masalah portofolio investasi, di mana Anda mungkin berakhir dengan sesuatu seperti di bawah ini, dalam kode semu:

 Maximize <expected profit from all stock investments> Subject to: <investment in the technology sector must be between 10% - 20% of portfolio> <investment in the consumer staples must not exceed investment in financials> Etc. ...

Yang akan agak rumit dan sulit dipecahkan dengan tangan atau coba-coba. Perangkat lunak riset operasi akan menggunakan beberapa algoritma untuk menyelesaikan masalah ini dengan cepat. Jika Anda tertarik dengan algoritme yang mendasarinya, saya sarankan untuk mempelajari metode simpleks di sini dan metode titik interior di sini.

Algoritma Pemrograman Integer

Pemrograman integer seperti pemrograman linier dengan tunjangan tambahan untuk beberapa atau semua variabel menjadi nilai integer. Meskipun ini mungkin tidak tampak seperti peningkatan besar pada awalnya, ini memungkinkan kita untuk memecahkan banyak masalah yang mungkin tidak terpecahkan hanya dengan menggunakan pemrograman linier.

Salah satu masalah tersebut adalah masalah knapsack, di mana kita diberikan satu set item dengan nilai dan bobot yang ditetapkan dan diminta untuk menemukan kombinasi nilai tertinggi dari item yang dapat kita masukkan ke dalam knapsack kita. Model pemrograman linier tidak akan dapat menyelesaikan ini karena tidak ada cara untuk mengekspresikan gagasan bahwa Anda dapat memasukkan item ke dalam ransel Anda atau tidak, tetapi Anda tidak dapat memasukkan sebagian item ke dalam ransel Anda—setiap variabel adalah kontinu variabel!

Contoh masalah knapsack mungkin memiliki parameter berikut:

Dan model MIP akan terlihat seperti ini:

 Maximize 5a + 7b + 2c + 10d (objective: maximize value of items take) Subject to: 2a + 4b + 7c + 10d <= 15 (space constraint)

Solusi optimal dalam hal ini adalah a=0, b=1, c=0, d=1, dengan nilai item total adalah 17.

Masalah yang akan kita pecahkan hari ini juga memerlukan pemrograman bilangan bulat karena seorang karyawan di sebuah pabrik dapat dijadwalkan untuk shift atau tidak—demi kesederhanaan, Anda tidak dapat menjadwalkan seorang karyawan untuk 2/3 shift di pabrik ini.

Untuk memungkinkan pemrograman integer, beberapa algoritma matematika digunakan. Jika Anda tertarik dengan algoritme yang mendasarinya, saya sarankan untuk mempelajari algoritme bidang potong dan algoritme cabang-dan-terikat di sini.

Contoh Soal: Penjadwalan

Deskripsi Masalah

Hari ini, kita akan mengeksplorasi masalah penempatan staf di sebuah pabrik. Sebagai manajemen pabrik, kami ingin meminimalkan biaya tenaga kerja, tetapi kami ingin memastikan cakupan yang cukup untuk setiap shift untuk memenuhi permintaan produksi.

Misalkan kita memiliki lima shift dengan tuntutan staf berikut:

Dan, misalkan kita memiliki pekerja berikut:

Untuk menjaga agar masalahnya tetap sederhana, mari kita asumsikan untuk saat ini bahwa ketersediaan dan biaya adalah satu-satunya masalah.

Alat kami

Untuk masalah hari ini, kita akan menggunakan software open source branch-and-cut yang disebut CBC. Kami akan berinteraksi dengan perangkat lunak ini menggunakan PuLP, yang merupakan perpustakaan pemodelan riset operasi populer untuk Python. Anda dapat menemukan informasi tentangnya di sini.

PuLP memungkinkan kita untuk membangun model MIP dengan cara yang sangat Pythonic dan terintegrasi dengan baik dengan kode Python yang ada. Ini sangat berguna karena beberapa alat manipulasi dan analisis data paling populer ditulis dengan Python, dan sebagian besar sistem riset operasi komersial memerlukan pemrosesan data ekstensif sebelum dan sesudah pengoptimalan.

Untuk mendemonstrasikan kesederhanaan dan keanggunan PuLP, berikut adalah masalah knapsack dari sebelumnya dan diselesaikan di PuLP:

 import pulp as pl # declare some variables # each variable is a binary variable that is either 0 or 1 # 1 means the item will go into the knapsack a = pl.LpVariable("a", 0, 1, pl.LpInteger) b = pl.LpVariable("b", 0, 1, pl.LpInteger) c = pl.LpVariable("c", 0, 1, pl.LpInteger) d = pl.LpVariable("d", 0, 1, pl.LpInteger) # define the problem prob = pl.LpProblem("knapsack", pl.LpMaximize) # objective function - maximize value of objects in knapsack prob += 5 * a + 7 * b + 2 * c + 10 * d # constraint - weight of objects cannot exceed 15 prob += 2 * a + 4 * b + 7 * c + 10 * d <= 15 status = prob.solve() # solve using the default solver, which is cbc print(pl.LpStatus[status]) # print the human-readable status # print the values print("a", pl.value(a)) print("b", pl.value(b)) print("c", pl.value(c)) print("d", pl.value(d))

Jalankan ini, dan Anda akan mendapatkan output:

 Optimal a 0.0 b 1.0 c 0.0 d 1.0

Sekarang ke masalah penjadwalan kami!

Mengkodekan Solusi Kami

Pengkodean solusi kami cukup mudah. Pertama, kita ingin mendefinisikan data kita:

 import pulp as pl import collections as cl # data shift_requirements = [1, 4, 3, 5, 2] workers = { "Melisandre": { "availability": [0, 1, 4], "cost": 20 }, "Bran": { "availability": [1, 2, 3, 4], "cost": 15 }, "Cersei": { "availability": [2, 3], "cost": 35 }, "Daenerys": { "availability": [3, 4], "cost": 35 }, "Theon": { "availability": [1, 3, 4], "cost": 10 }, "Jon": { "availability": [0, 2, 4], "cost": 25 }, "Tyrion": { "availability": [1, 3, 4], "cost": 30 }, "Jaime": { "availability": [1, 2, 4], "cost": 20 }, "Arya": { "availability": [0, 1, 3], "cost": 20 } }

Selanjutnya, kita akan ingin mendefinisikan model:

 # define the model: we want to minimize the cost prob = pl.LpProblem("scheduling", pl.LpMinimize) # some model variables cost = [] vars_by_shift = cl.defaultdict(list) for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable("%s_%s" % (worker, shift), 0, 1, pl.LpInteger) vars_by_shift[shift].append(worker_var) cost.append(worker_var * info['cost']) # set the objective to be the sum of cost prob += sum(cost) # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum(vars_by_shift[shift]) >= requirement

Dan sekarang kita tinggal memintanya untuk memecahkan dan mencetak hasilnya!

 status = prob.solve() print("Result:", pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ "shift": shift, "workers": [var.name for var in vars if var.varValue == 1], }) for result in sorted(results, key=lambda x: x['shift']): print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']))

Setelah Anda menjalankan kode, Anda akan melihat output berikut:

 Result: Optimal Shift: 0 workers: Arya_0 Shift: 1 workers: Melisandre_1, Bran_1, Theon_1, Arya_1 Shift: 2 workers: Bran_2, Jon_2, Jaime_2 Shift: 3 workers: Bran_3, Daenerys_3, Theon_3, Tyrion_3, Arya_3 Shift: 4 workers: Bran_4, Theon_4

Tingkatkan Kesulitan Sedikit: Kendala Tambahan

Meskipun model sebelumnya menarik dan berguna, model ini tidak sepenuhnya menunjukkan kekuatan pemrograman integer campuran. Kita juga dapat dengan mudah menulis perulangan for untuk menemukan x pekerja termurah untuk setiap shift, di mana x adalah jumlah pekerja yang dibutuhkan untuk satu shift. Untuk mendemonstrasikan bagaimana MIP dapat digunakan untuk memecahkan masalah yang akan menantang untuk dipecahkan secara imperatif, mari kita periksa apa yang akan terjadi jika kita menambahkan beberapa kendala tambahan.

Kendala Tambahan

Misalkan, karena peraturan ketenagakerjaan yang baru, tidak ada pekerja yang dapat ditugaskan lebih dari 2 shift. Untuk memperhitungkan peningkatan pekerjaan, kami telah merekrut bantuan Kelompok Staf Dothraki, yang akan memasok hingga 10 pekerja Dothraki untuk setiap shift dengan tarif $40 per shift.

Selain itu, anggaplah, karena beberapa konflik antarpribadi yang sedang berlangsung di luar pabrik kami, Cersei dan Jaime tidak dapat bekerja secara bergiliran bersama Daenerys atau Jon. Selain itu, Jaime dan Cersei tidak dapat bekerja secara bergantian. Akhirnya, Arya, yang memiliki hubungan interpersonal yang sangat kompleks, tidak dapat bekerja dalam shift yang sama dengan Jaime, Cersei, atau Melisandre.

Penambahan dua kendala dan sumber daya baru ini sama sekali tidak membuat masalah tidak dapat dipecahkan melalui cara-cara imperatif, tetapi ini membuat solusi menjadi lebih sulit, karena seseorang harus memperhitungkan biaya peluang dari penjadwalan pekerja ke shift tertentu.

Larutan

Namun, dengan pemrograman integer campuran, ini jauh lebih mudah. Kami hanya perlu mengubah kode kami seperti ini:

Tentukan daftar larangan dan beberapa batasan:

 ban_list = { ("Daenerys", "Jaime"), ("Daenerys", "Cersei"), ("Jon", "Jaime"), ("Jon", "Cersei"), ("Arya", "Jaime"), ("Arya", "Cersei"), ("Arya", "Melisandre"), ("Jaime", "Cersei") } DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

Isi variabel untuk menerapkan larangan dan batasan shift maks:

 for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable("%s_%d" % (worker, shift), 0, 1, pl.LpInteger) # store some variable data so we can implement the ban constraint var_data = (worker,) vars_by_shift[shift].append((worker_var, var_data)) # store vars by variable so we can implement the max shift constraint vars_by_worker[worker].append(worker_var) cost.append(worker_var * info['cost'])

Tambahkan variabel Dothraki:

 for shift in range(len(shift_requirements)): dothraki_var = pl.LpVariable('dothraki_%d' % shift, 0, DOTHRAKI_MAX, pl.LpInteger) cost.append(dothraki_var * DOTHRAKI_COST) dothrakis_by_shift[shift] = dothraki_var

Kami juga membutuhkan loop yang sedikit dimodifikasi untuk menghitung persyaratan shift dan ban:

 # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum([var[0] for var in vars_by_shift[shift]]) + dothrakis_by_shift[shift] >= requirement # set the ban requirements for shift, vars in vars_by_shift.items(): for var1 in vars: for var2 in vars: worker_pair = var1[1][0], var2[1][0] if worker_pair in ban_list: prob += var1[0] + var2[0] <= 1 # set the labor standards: for worker, vars in vars_by_worker.items(): prob += sum(vars) <= 2

Dan akhirnya, untuk mencetak hasilnya:

 status = prob.solve() print("Result:", pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ "shift": shift, "workers": [var[1][0] for var in vars if var[0].varValue == 1], "dothrakis": dothrakis_by_shift[shift].varValue }) for result in sorted(results, key=lambda x: x['shift']): print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']), 'dothrakis hired:', int(result['dothrakis']))

Dan kita harus baik-baik saja. Jalankan kode dan Anda akan melihat output seperti di bawah ini:

 Result: Optimal Shift: 0 workers: Arya dothrakis hired: 0 Shift: 1 workers: Melisandre, Theon, Tyrion, Jaime dothrakis hired: 0 Shift: 2 workers: Bran, Jon dothrakis hired: 1 Shift: 3 workers: Bran, Daenerys, Theon, Tyrion, Arya dothrakis hired: 0 Shift: 4 workers: Melisandre, Jaime dothrakis hired: 0

Dan begitulah, hasil yang menghormati daftar pekerja yang dilarang, mengikuti peraturan ketenagakerjaan, dan menggunakan pekerja Dothraki dengan bijaksana.

Kesimpulan

Hari ini, kami menjelajahi penggunaan pemrograman integer campuran untuk membuat keputusan yang lebih baik. Kami membahas algoritma dan teknik yang mendasari yang digunakan dalam riset operasi dan melihat contoh masalah yang mewakili bagaimana pemrograman bilangan bulat campuran digunakan di dunia nyata.

Saya harap artikel ini menginspirasi Anda untuk mempelajari lebih lanjut tentang riset operasi dan membuat Anda berpikir tentang bagaimana teknologi ini dapat diterapkan pada proyek Anda. Kami hanya benar-benar melihat puncak gunung es ketika datang ke dunia algoritma optimasi dan riset operasi yang menarik.

Anda dapat menemukan semua kode yang terkait dengan artikel ini di GitHub. Jika Anda ingin berdiskusi lebih lanjut, bagikan komentar Anda di bawah!