Merancang Algoritma Optimasi dengan HorusLP

Riset operasi dan optimisasi cembung adalah bidang matematika terapan yang telah menemukan aplikasi komersial yang luas selama bertahun-tahun. Karena daya komputasi menjadi lebih terjangkau dan tersedia secara luas, para peneliti mulai membangun algoritme pengoptimalan yang semakin canggih untuk membantu mereka membuat keputusan yang lebih baik. Saat ini, aplikasi yang didukung oleh riset operasi menggerakkan segalanya mulai dari perutean dalam logistik global hingga kelancaran produksi listrik di industri energi.

Ketika teknologi yang mendasarinya tumbuh dalam kompleksitas, seperangkat alat baru telah dibuat untuk membantu peneliti dan pengembang bekerja lebih produktif. Alat-alat ini, seperti AMPL, CVXPY, dan PuLP, memungkinkan pengembang untuk dengan cepat menentukan, membangun, dan menjalankan algoritme pengoptimalan dan antarmuka dengan berbagai pemecah masalah.

Namun, sementara teknologi pengoptimalan dan kebutuhan bisnis terus berkembang dalam kecanggihan, sebagian besar alat ini kurang lebih tetap sama dan tidak berkembang cukup cepat untuk memenuhi kebutuhan industri. Akibatnya, mengembangkan, mengelola, men-debug, dan menyetel algoritme ini sering kali membutuhkan biaya kognitif yang besar, terutama di lingkungan bisnis yang bergerak cepat.

Hari ini, saya ingin memperkenalkan HorusLP, pustaka pengoptimalan Python yang membantu arsitektur alur kerja pengembangan algoritme. Kami akan berbicara tentang masalah yang dirancang untuk dipecahkan oleh alat ini, kemudian memberikan gambaran singkat tentang pustaka Python, dan kami akan membangun beberapa contoh algoritme pengoptimalan.

Masalah yang Dihadapi Pengembang Algoritma Optimasi

Salah satu masalah abadi yang dihadapi sebagian besar pengembang adalah keseimbangan antara membangun perangkat lunak idiomatis yang dapat dipelihara, efisien, dan memberikan produk dalam batasan waktu proyek. Baik Anda sedang mengerjakan aplikasi berbasis browser, API web, atau layanan mikro otentikasi pengguna, sering kali ada kompromi antara cara yang "benar" dan cara yang "cepat" untuk mencapai tujuan Anda. Tradeoff yang melekat ini menjadi lebih menonjol seiring dengan meningkatnya kompleksitas produk.

Di sebagian besar disiplin ilmu, pengembang dapat mengatasi masalah ini dengan memilih kerangka kerja atau pustaka yang membantu arsitektur. Di front-end yang menghadap web, banyak pengembang memilih React atau Angular; di dunia pengembangan API, insinyur perangkat lunak dapat memilih dari Django, ASP.NET MVC, atau Play, di antara banyak lainnya. Namun, jika menyangkut pengembang algoritme pengoptimalan yang sederhana, hanya ada sedikit alat arsitektur untuk membantu mengelola kompleksitas arsitektur. Pengembang dibiarkan mengelola variabel, kendala, dan berbagai tujuan sendiri. Terlebih lagi, algoritma riset operasi umumnya sulit untuk diintrospeksi, memperburuk masalah.

Tujuan utama HorusLP adalah untuk menyediakan kerangka kerja arsitektural untuk mengembangkan algoritma optimasi. Dengan memberikan konsistensi struktural, kerangka kerja membuat organisasi lebih mudah dan memungkinkan pengembang untuk fokus pada apa yang mereka lakukan yang terbaik: membangun algoritme.

Tantangan Alur Kerja Pengoptimalan Umum

Ada beberapa sumber utama kompleksitas ketika mengembangkan algoritma OR:

Kompleksitas dari variabel

• Variabel seringkali harus ditambahkan untuk mengakomodasi kebutuhan bisnis tambahan dan tidak ada cara mudah untuk melacaknya untuk digunakan dalam definisi model dan pelaporan nanti.
• Variabel terkait perlu dikelompokkan dan dilacak, dan tidak ada cara yang jelas untuk mengelolanya.

Kompleksitas dari kendala

• Kendala perlu ditambahkan dan dihapus untuk mendukung berbagai skenario dan untuk melakukan debugging, tetapi tidak ada tempat yang jelas untuk menambah atau menghapus kendala.
• Kendala sering terkait/bergantung satu sama lain, dan tidak ada cara alami untuk mengekspresikan hubungan mereka.

Kompleksitas dari tujuan

• Ekspresi objektif bisa menjadi berat jika memiliki banyak komponen. Hal ini dapat diperburuk jika berbagai komponen diberi bobot, dan bobotnya perlu disesuaikan berdasarkan kebutuhan bisnis.

Kompleksitas dari debugging

• Tidak ada cara mudah untuk melihat hasil model selama pengembangan. Pengembang harus secara eksplisit mencetak variabel baru dan nilai kendala untuk melihat hasilnya. Hal ini menyebabkan kode digandakan dan pengembangan lebih lambat.
• Ketika menambahkan kendala menyebabkan model menjadi tidak layak, mungkin tidak jelas mengapa kendala menyebabkan model menjadi tidak layak. Biasanya, pengembang harus menghilangkan berbagai kendala dan mencari ketidakcocokan melalui coba-coba

HorusLP berharap untuk membuat tantangan ini lebih mudah dikelola dengan menyediakan struktur, peralatan, praktik terbaik untuk meningkatkan produktivitas pengembang dan pemeliharaan produk.

Tutorial HorusLP: Algoritma Pengoptimalan dan Ikhtisar API

Tanpa basa-basi lagi, mari selami dan lihat apa yang dapat dilakukan perpustakaan HorusLP untuk Anda!

Karena HorusLP didasarkan pada Python dan PuLP, kami ingin menginstalnya menggunakan pip. Jalankan yang berikut ini di baris perintah Anda:

 Pip install horuslp pulp

Setelah instalasi selesai, mari kita lanjutkan dan buka file Python. Kami akan menerapkan masalah knapsack dari artikel saya sebelumnya tentang riset operasi.

Pustaka HorusLP memiliki API deklaratif yang sangat sederhana dan boilerplate yang sangat sedikit. Mari kita mulai dengan mengimpor kelas dan variabel yang diperlukan:

 from horuslp.core.Variables import BinaryVariable # we will be using binary variables, so we will import the BinaryVariable class from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent # We will also need to import the constraint class, variable manager class, the main problem class, and the objective class to define the objective. from horuslp.core.constants import MAXIMIZE # since we're maximizing the resulting value, we want to import this constant

Setelah kita mengimpor semua variabel, mari kita definisikan variabel yang kita butuhkan untuk masalah ini. Kami melakukan ini dengan membuat subkelas manajer variabel dan mengisinya dengan variabel biner:

 class KnapsackVariables(VariableManager): vars = [ BinaryVariable('camera'), # the first argument is the name of the variable BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn') ]

Sekarang setelah variabel didefinisikan, mari kita definisikan batasannya. Kami membuat batasan dengan mensubklasifikasikan kelas batasan utama dan mengimplementasikan fungsi "define".

 class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

Dalam fungsi define, Anda dapat meminta variabel yang diperlukan berdasarkan nama. Kerangka kerja akan menemukan variabel di manajer variabel dan meneruskannya ke fungsi define.

Setelah kendala diimplementasikan, kita dapat mengimplementasikan tujuan. Karena ini adalah tujuan yang sederhana, kami akan menggunakan ObjectiveComponent :

 class ValueObjective(ObjectiveComponent): def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn

Fungsi define memiliki pengaturan yang sangat mirip dengan fungsi define kelas kendala. Namun, alih-alih mengembalikan ekspresi kendala, kami mengembalikan ekspresi affine.

Sekarang setelah variabel, batasan, dan tujuan didefinisikan, mari kita definisikan modelnya:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE

Untuk membangun model, kami membuat kelas yang merupakan subkelas dari kelas Masalah dan menentukan variabel, tujuan, kendala, dan pengertian. Dengan masalah yang ditentukan, kita dapat menyelesaikan masalah:

 prob = KnapsackProblem() prob.solve()

Setelah penyelesaian, kita dapat mencetak hasilnya menggunakan fungsi print_results kelas masalah. Kita juga dapat mengakses nilai variabel tertentu dengan melihat kelas result_variables .

 prob.print_results() print(prob.result_variables)

Jalankan skrip, dan Anda akan melihat output berikut:

 KnapsackProblem: Optimal camera 0.0 figurine 1.0 cider 0.0 horn 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'camera': 0.0, 'figurine': 1.0, 'cider': 0.0, 'horn': 1.0}

Anda harus melihat status masalah, nilai akhir variabel, nilai objektif, dan nilai ekspresi kendala. Kami juga melihat nilai yang dihasilkan dari variabel sebagai kamus.

Dan begitulah, masalah HorusLP pertama kami di sekitar 35 baris!

Dalam contoh yang akan datang, kita akan menjelajahi beberapa fitur yang lebih canggih dari perpustakaan HorusLP.

Menggunakan VariableGroups

Terkadang, variabel terkait dan termasuk dalam kelompok logis. Dalam kasus masalah knapsack, semua variabel dapat ditempatkan ke dalam grup objek. Kita dapat memfaktorkan ulang kode untuk menggunakan grup variabel. Pastikan menyimpan kode dari bagian sebelumnya karena kami akan merujuknya di tutorial berikutnya!

Ubah pernyataan impor seperti ini:

 from horuslp.core.Variables import BinaryVariableGroup from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp.core.constants import MAXIMIZE

Sekarang kita juga perlu mengubah deklarasi variabel knapsack seperti:

 class KnapsackVariables(VariableManager): vars = [ BinaryVariableGroup('objects', [ 'camera', 'figurine', 'cider', 'horn' ]) ]

Argumen pertama adalah nama grup variabel, variabel kedua adalah daftar nama untuk variabel dalam grup itu.

Sekarang kita perlu mengubah batasan dan definisi objektif. Alih-alih menanyakan nama individu, kita akan menanyakan grup variabel, yang akan diteruskan sebagai kamus di mana kuncinya adalah nama dan nilainya adalah variabelnya. Ubah batasan dan definisi objektif seperti:

 class SizeConstraint(Constraint): def define(self, objects): return 2 * objects['camera'] + 4 * objects['figurine'] + 7 * objects['cider'] + 10 * objects['horn'] <= 15 class ValueObjective(ObjectiveComponent): def define(self, objects): return 5 * objects['camera'] + 7 * objects['figurine'] + 2 * objects['cider'] + 10 * objects['horn']

Sekarang kita dapat menggunakan definisi masalah yang sama dan menjalankan perintah:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results() print(prob.result_variables)

Anda akan melihat ini di output Anda:

 KnapsackProblem: Optimal objects[camera] 0.0 objects[figurine] 1.0 objects[cider] 0.0 objects[horn] 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'objects': {'camera': 0.0, 'figuring': 1.0, 'cider': 0.0, 'horn': 1.0}}

Mengelola Banyak Kendala

Model dengan kendala tunggal relatif jarang. Saat bekerja dengan banyak kendala, ada baiknya untuk memiliki semua kendala di satu tempat sehingga dapat dilacak dan dikelola dengan mudah. HorusLP membuatnya alami.

Misalkan, misalnya, kita ingin melihat bagaimana hasilnya akan berubah jika kita memaksa model untuk menambahkan kamera ke ransel kita. Kami akan menerapkan batasan tambahan dan menambahkannya ke definisi masalah kami.

Kembali ke model yang kita terapkan di tutorial pertama. Tambahkan batasan berikut:

 class MustHaveItemConstraint(Constraint): def define(self, camera): return camera >= 1

Untuk menambahkan batasan ke model, kita hanya perlu menambahkannya ke definisi masalah seperti ini:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [ SizeConstraint, MustHaveItemConstraint # just add this line :) ] sense = MAXIMIZE

Jalankan masalahnya, dan Anda akan melihat output berikut:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 cider 0.0 horn 1.0 ValueObjective: 15.00 SizeConstraint: 12.00 MustHaveItemConstraint: 1.00

Anda akan melihat batasan baru dicetak di stdout, dan nilai variabel optimal yang diubah.

Mengelola Kendala Dependen dan Grup Kendala

Kendala sering terkait satu sama lain baik karena mereka bergantung satu sama lain, atau karena mereka secara logis termasuk dalam kelompok yang sama.

Misalnya, jika Anda ingin menetapkan batasan untuk membatasi jumlah nilai absolut dari sekumpulan variabel, Anda harus terlebih dahulu menentukan batasan untuk menyatakan hubungan nilai absolut antara variabel yang dimaksud, dan kemudian menentukan batas nilai absolut. Terkadang, Anda perlu menerapkan batasan serupa ke sekelompok variabel untuk mengekspresikan hubungan spesifik antar variabel.

Untuk mengekspresikan pengelompokan ini, kita dapat menggunakan fitur batasan dependen dari definisi batasan kita. Untuk melihat bagaimana fitur batasan dependen dapat digunakan, refactor SizeConstraint dari masalah sebelumnya seperti:

 class SizeConstraint(Constraint): dependent_constraints = [MustHaveItemConstraint] def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

Dan sekarang untuk menguji bahwa batasan dependen diimplementasikan secara otomatis, mari kita MustHaveItemConstraint dari definisi masalah:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [ SizeConstraint, ] sense = MAXIMIZE

Dan jalankan kodenya lagi, dan Anda akan melihat yang berikut di stdout:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 cider 0.0 horn 1.0 ValueObjective: 15.00 SizeConstraint: 12.00 MustHaveItemConstraint: 1.00

Sepertinya MustHaveItemConstraint diimplementasikan! Untuk contoh yang lebih kompleks tentang bagaimana batasan dependen dapat digunakan, lihat contoh penempatan staf di akhir tutorial.

Mengelola Beberapa Tujuan Tertimbang

Seringkali, selama pengembangan algoritme pengoptimalan kami, kami akan menemukan ekspresi objektif yang terdiri dari beberapa bagian. Sebagai bagian dari eksperimen kami, kami dapat mengubah penimbangan berbagai komponen objektif untuk membuat algoritme bias menuju hasil yang diinginkan. CombinedObjective menyediakan cara yang bersih dan sederhana untuk mengekspresikan ini.

Misalkan kita ingin membiaskan algoritma untuk memilih figurine dan cider. Mari kita refactor kode dari bagian sebelumnya untuk menggunakan CombinedObjective .

Pertama, impor kelas CombinedObjective seperti:

 from horuslp.core import CombinedObjective

Kami dapat menerapkan komponen tujuan independen seperti:

 class ILoveCiderFigurineObjectiveComponent(ObjectiveComponent): def define(self, figurine, cider): return figurine + cider

Sekarang kita dapat menggabungkan tujuan nilai dan tujuan cider/figurine dengan menerapkan CombinedObjective :

 class Combined(CombinedObjective): objectives = [ (ILoveCiderFigurineObjectiveComponent, 2), # first argument is the objective, second argument is the weight (ValueObjectiveComponent, 1) ]

Sekarang mari kita ubah definisi masalah seperti ini:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = Combined constraints = [SizeConstraint] sense = MAXIMIZE

Jalankan masalahnya, dan Anda akan melihat output berikut:

 KnapsackProblem: Optimal camera 1.0 figurine 1.0 cider 1.0 horn 0.0 Combined: 18.00 ILoveCiderFigurineObjectiveComponent: 2.00 * 2 ValueObjectiveComponent: 14.00 * 1 SizeConstraint: 13.00 MustHaveItemConstraint: 1.00

Outputnya akan menguraikan nilai tujuan gabungan, nilai masing-masing komponen tujuan, bobot, dan tentu saja nilai semua kendala.

Menemukan Kendala yang Tidak Kompatibel

Saat mengembangkan algoritma, kita sering mengalami model yang tidak layak. Jika modelnya kompleks, dapat menjadi tantangan untuk menentukan mengapa model tersebut tiba-tiba tidak layak. HorusLP memiliki alat yang berguna untuk membantu Anda dalam kasus tersebut.

Misalkan kita menambahkan kendala dan berakhir dengan rangkaian kendala berikut:

 class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 class SizeConstraint2(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 20 class MustHaveItemConstraint(Constraint): def define(self, cider): return cider >= 1 class IncompatibleConstraint1(Constraint): def define(self, camera): return camera >= 1 class IncompatibleConstraint2(Constraint): def define(self, camera): return camera <= 0

Kami memiliki beberapa batasan pada ukuran total barang di ransel, batasan yang mengharuskan cider harus ada di ransel, dan satu set batasan yang tidak kompatibel yang mengharuskan kamera berada di dalam dan tidak di dalam ransel. (Tentu saja, dalam algoritme dunia nyata, kendala biasanya tidak begitu jelas dan melibatkan hubungan dan kendala variabel yang kompleks.)

Misalkan juga kendala dikelompokkan dengan cara berikut, mungkin membuat deteksi lebih sulit:

 class CombinedConstraints1(Constraint): dependent_constraints = [SizeConstraint2, IncompatibleConstraint1] class CombinedConstraints2(Constraint): dependent_constraints = [SizeConstraint, IncompatibleConstraint2] # MustHaveItemConstraint will be included in the problem definition independently

Berikut adalah definisi masalah:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [CombinedConstraints1, CombinedConstraints2, MustHaveItemConstraint] sense = MAXIMIZE

Jalankan masalahnya, dan Anda akan melihat hasil berikut:

 KnapsackProblem: Infeasible

Oh tidak! Apa yang kita lakukan? Jika kita menggunakan sebagian besar alat, kita harus memulai sesi debugging yang sulit di mana kita mempersempit kendala yang berpotensi konflik satu per satu. Untungnya, HorusLP memiliki fitur pencarian ketidakcocokan untuk membantu Anda mempersempit kendala yang tidak kompatibel lebih cepat. Cara paling sederhana untuk menggunakan fitur pencarian ketidakcocokan adalah dengan mengubah panggilan print_results sebagai berikut:

 prob.print_results(find_infeasible=True)

Sederhana seperti itu! Jalankan kode, dan sekarang Anda akan melihat yang berikut sebagai output:

 KnapsackProblem: Infeasible Finding incompatible constraints... Incompatible Constraints: ('CombinedConstraints1', 'CombinedConstraints2')

Besar! Sekarang kami telah menetapkan bahwa MustHaveItemConstraint bukanlah penyebab ketidaklayakan dan bahwa masalahnya adalah karena CombinedConstraints1 dan CombinedConstraints2 .

Itu memberi kita beberapa informasi, tetapi di antara kendala gabungan ada empat kendala dependen. Bisakah kita mengidentifikasi mana dari empat kendala yang tidak kompatibel? Baiklah. Ubah panggilan print_results Anda sebagai berikut:

 prob.print_results(find_infeasible=True, deep_infeasibility_search=True)

Ini akan membuat pencarian ketidaklayakan memperluas batasan dependen sehingga kami mendapatkan gambaran yang jauh lebih terperinci tentang apa yang menyebabkan ketidaklayakan. Jalankan ini dan Anda akan melihat output berikut:

 KnapsackProblem: Infeasible Finding incompatible constraints... Incompatible Constraints: ('IncompatibleConstraint1', 'IncompatibleConstraint2')

Meskipun tergoda untuk menjalankan pencarian ketidaklayakan yang mendalam setiap saat, untuk masalah realistis dengan sejumlah besar kendala total, pencarian ketidaklayakan yang mendalam dapat menjadi sangat intensif sumber daya dan memakan waktu. Oleh karena itu, yang terbaik adalah menjalankan pencarian ketidaklayakan dasar untuk mempersempit kemungkinan dan menjalankan pencarian ketidaklayakan yang mendalam pada subset yang lebih kecil setelah melakukan beberapa penyelidikan manual.

Membangun Algoritma dari File Data

Saat membangun model, kami jarang memiliki kemewahan untuk membuat kode keras setiap kendala dan variabel. Seringkali, program kita harus cukup fleksibel untuk mengubah model tergantung pada data input. Misalkan alih-alih input hard-code kami ingin membangun masalah knapsack kami dari JSON berikut:

 { "items": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "figurine", "value": 7, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "horn", "value": 10, "weight": 10}, {"name": "banana", "value": 9, "weight": 2} ], "capacity": 15 }

Kita dapat melakukan ini dengan mengandalkan dukungan kwargs dari fungsi "define" yang kita terapkan untuk batasan dan tujuan.

Mari kita modifikasi kode dari masalah knapsack sederhana (masalah yang kita implementasikan di bagian 1 dari tutorial). Pertama, mari kita masukkan string JSON ke dalam file. Tentu saja, kita biasanya membacanya dari sumber eksternal, tetapi demi kesederhanaan mari kita simpan semuanya dalam satu file. Tambahkan yang berikut ini ke kode Anda:

 JSON = ''' { "items": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "figurine", "value": 7, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "horn", "value": 10, "weight": 10}, {"name": "banana", "value": 9, "weight": 2} ], "capacity": 15 } '''

Mari kita juga memastikan bahwa program kita dapat menguraikannya. Tambahkan yang berikut ini ke pernyataan impor Anda:

 Import json

Sekarang, mari kita ubah kode penyiapan variabel kita sebagai berikut:

 mip_cfg = json.loads(JSON) class KnapsackVariables(VariableManager): vars = [ BinaryVariable(i['name']) for i in mip_cfg['items'] ]

Ini akan mendefinisikan variabel untuk setiap item di JSON, dan menamainya dengan tepat.

Mari kita ubah batasan dan definisi objektif seperti ini:

 class CapacityConstraint(Constraint): def define(self, **kwargs): item_dict = {i['name']: i['weight'] for i in mip_cfg['items']} return sum(kwargs[name] * item_dict[name] for name in kwargs) <= mip_cfg['capacity'] class ValueObjective(ObjectiveComponent): def define(self, **kwargs): item_dict = {i['name']: i['value'] for i in mip_cfg['items']} return sum(kwargs[name] * item_dict[name] for name in kwargs)

Dengan meminta **kwargs alih-alih variabel tertentu, fungsi define mendapatkan kamus yang berisi semua variabel berdasarkan nama. Fungsi definisi batasan kemudian dapat mengakses variabel dari kamus.

Catatan: Untuk grup variabel, ini akan menjadi kamus bersarang di mana level pertama adalah nama grup dan level kedua adalah nama variabel.

Sisanya cukup sederhana:

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [CapacityConstraint] objective = ValueObjective sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results()

Jalankan program ini dan Anda akan melihat output berikut:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 apple 0.0 horn 1.0 banana 1.0 ValueObjective: 24.00 CapacityConstraint: 14.00

Mendefinisikan Metrik Kustom di HorusLP

Terkadang, untuk tujuan debug dan pelaporan, kami akan membuat metrik khusus yang tidak dinyatakan secara langsung dalam tujuan atau sebagai batasan. HorusLP memiliki fitur untuk membuat penentuan metrik khusus menjadi sederhana.

Misalkan kita ingin melacak berapa banyak buah yang dimasukkan model dari bagian sebelumnya ke dalam ransel. Untuk melacaknya, kami dapat menentukan metrik khusus. Mari kita mulai dengan mengimpor kelas dasar Metrik:

 From horuslp.core import Metric

Sekarang mari kita tentukan metrik khusus:

 class NumFruits(Metric): name = "Number of Fruits" def define(self, apple, banana): return apple + banana

Seperti yang Anda lihat, antarmuka yang ditentukan terlihat sangat mirip dengan kelas komponen kendala dan tujuan. Jika Anda telah mengikuti tutorial sejauh ini, ini seharusnya cukup familiar bagi Anda.

Sekarang kita perlu menambahkan metrik ke definisi masalah. Antarmuka di sini sekali lagi sangat mirip dengan definisi kendala:

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [CapacityConstraint] objective = ValueObjective metrics = [NumFruits] sense = MAXIMIZE

Jalankan ini dan Anda akan melihat output berikut:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 apple 0.0 horn 1.0 banana 1.0 ValueObjective: 24.00 CapacityConstraint: 14.00 Number of Fruits: 1.00

Anda dapat melihat jumlah buah yang tercetak di bagian bawah.

Mengatasi Masalah yang Lebih Kompleks: Dua Ransel

Mari kita bekerja melalui contoh yang sedikit lebih kompleks. Misalkan alih-alih satu ransel, kita memiliki tas dan koper. Kami juga memiliki dua kelas objek, tahan lama dan rapuh. Koper, karena lebih protektif, dapat menampung barang-barang yang rapuh dan tahan lama. Tas, di sisi lain, hanya bisa menampung barang-barang tahan lama. Misalkan juga bahwa data untuk item diberikan dalam JSON berikut:

 { "fragile": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "glasses", "value": 3, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "pear", "value": 5, "weight": 3}, {"name": "banana", "value": 9, "weight": 2} ], "durable": [ {"name": "figurine", "value": 7, "weight": 4}, {"name": "horn", "value": 10, "weight": 10}, {"name": "leatherman", "value": 10, "weight": 3} ], "suitcase_capacity": 15, "bag_capacity": 20 }

Mari kita lihat bagaimana ini mengubah model. Mari kita mulai dengan batu tulis kosong karena modelnya akan sangat berbeda. Mulailah dengan pengaturan masalah:

 import json from horuslp.core.Variables import BinaryVariableGroup from horuslp.core import Constraint, VariableManager, Problem, Metric, ObjectiveComponent from horuslp.core.constants import MAXIMIZE JSON = ''' { "fragile": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "glasses", "value": 3, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "pear", "value": 5, "weight": 3}, {"name": "banana", "value": 9, "weight": 2} ], "durable": [ {"name": "figurine", "value": 7, "weight": 4}, {"name": "horn", "value": 10, "weight": 10}, {"name": "leatherman", "value": 10, "weight": 3} ], "suitcase_capacity": 15, "bag_capacity": 20 } ''' mip_cfg = json.loads(JSON)

Sekarang mari kita atur variabelnya. Kami akan menyiapkan variabel biner untuk setiap kemungkinan kombinasi item/wadah.

 class KnapsackVariables(VariableManager): vars = [ # suitcase can hold both fragile and durable goods BinaryVariableGroup('suitcase_f', [i['name'] for i in mip_cfg['fragile']]), BinaryVariableGroup('suitcase_d', [i['name'] for i in mip_cfg['durable']]), # bag can only hold durable goods. BinaryVariableGroup('bag_d', [i['name'] for i in mip_cfg['durable']]) ]

Sekarang kami ingin menerapkan batasan berat untuk koper dan tas.

 class SuitcaseCapacityConstraint(Constraint): def define(self, suitcase_d, suitcase_f): fragile_weight = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) durable_weight = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return fragile_weight + durable_weight <= mip_cfg['suitcase_capacity'] class BagCapacityConstraint(Constraint): def define(self, bag_d): durable_weight = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return durable_weight <= mip_cfg['bag_capacity']

Sekarang kita perlu menerapkan batasan yang sedikit lebih kompleks — batasan yang memastikan item tidak masuk ke dalam koper dan tas — yaitu, jika variabel "di dalam koper" adalah 1, maka "di dalam tas" variabel harus nol, dan sebaliknya. Tentu saja, kami ingin memastikan untuk mengizinkan kejadian di mana item tersebut berakhir di kedua wadah juga.

Untuk menambahkan batasan ini, kita perlu mengulangi semua item tahan lama, menemukan variabel "di dalam koper" dan variabel "di dalam tas" dan menegaskan bahwa jumlah variabel ini kurang dari 1.

Kami secara dinamis dapat mendefinisikan batasan dependen dengan cukup mudah di HorusLP:

 class UniquenessConstraints(Constraint): def __init__(self): super(UniquenessConstraints, self).__init__() # call the dependent constraint builder function for every durable item, and push them into dependent constraints. dependent_constraints = [self.define_uniqueness_constraint(item) for item in mip_cfg['durable']] self.dependent_constraints = dependent_constraints def define_uniqueness_constraint(self, item): # classes are first-class objects in python, so we can define a class within this function and return it class UQConstraint(Constraint): # we name the constraint based on the item this is for, so that debugging is easier. name = "Uniqueness_%s" % item['name'] def define(self, suitcase_d, bag_d): # the define function can access the variables much in the same way as other functions return suitcase_d[item['name']] + bag_d[item['name']] <= 1 return UQConstraint

Sekarang setelah batasan didefinisikan, mari kita bangun tujuannya. Tujuannya sederhana, jumlah semua nilai yang kami dapatkan dari semua item yang ada di dalam wadah. Dengan demikian:

 class TotalValueObjective(ObjectiveComponent): def define(self, suitcase_f, suitcase_d, bag_d): fragile_value = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) durable_value_s = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) durable_value_d = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return fragile_value + durable_value_s + durable_value_d

Mari kita juga menentukan beberapa metrik khusus sehingga kita dapat melihat sekilas berapa banyak berat yang dimasukkan ke dalam tas dan koper, serta berapa banyak berat koper yang berasal dari barang tahan lama dan barang rapuh:

 class SuitcaseFragileWeightMetric(Metric): def define(self, suitcase_f): return sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) class SuitcaseDurableWeightMetric(Metric): def define(self, suitcase_d): return sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) class BagWeightMetric(Metric): def define(self, bag_d): return sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']])

Sekarang kita telah menyelesaikan semua bagian, mari kita buat contoh masalahnya dan jalankan modelnya:

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [SuitcaseCapacityConstraint, BagCapacityConstraint, UniquenessConstraints] objective = TotalValueObjective metrics = [SuitcaseDurableValueMetric, SuitcaseFragileValueMetric, BagValueMetric] sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results()

Jalankan ini, dan Anda akan melihat output berikut di stdout Anda:

 KnapsackProblem: Optimal suitcase_f[camera] 1.0 suitcase_f[glasses] 1.0 suitcase_f[apple] 1.0 suitcase_f[pear] 0.0 suitcase_f[banana] 1.0 suitcase_d[figurine] 0.0 suitcase_d[horn] 0.0 suitcase_d[leatherman] 0.0 bag_d[figurine] 1.0 bag_d[horn] 1.0 bag_d[leatherman] 1.0 TotalValueObjective: 32.00 SuitcaseCapacityConstraint: 15.00 BagCapacityConstraint: 17.00 Uniqueness_figurine: 1.00 Uniqueness_horn: 1.00 Uniqueness_leatherman: 1.00 SuitcaseDurableWeightMetric: 0.00 SuitcaseFragileWeightMetric: 15.00 BagWeightMetric: 17.00

Jadi kamera, kacamata, apel, dan pisang masuk ke dalam koper dengan total 15 unit berat, patung, tanduk, dan leatherman semuanya masuk ke dalam tas dengan total 17 berat. Nilai total barang keluar menjadi 32 unit nilai. Menariknya, tidak ada barang tahan lama yang masuk ke dalam koper, kemungkinan besar karena tas memiliki kapasitas yang cukup untuk menampung semua barang tahan lama.

Skenario yang Lebih Besar dan Lebih Realistis: Masalah Kepegawaian

Jika Anda telah sampai sejauh ini dalam tutorial HorusLP kami, selamat! Anda sekarang memiliki ide bagus tentang cara menggunakan HorusLP.

Namun, semua contoh yang telah kami kerjakan sejauh ini merupakan permutasi dari masalah knapsack, dan beberapa persyaratan dan parameter agak tidak realistis. Mari kita selesaikan satu masalah lagi bersama-sama untuk melihat bagaimana HorusLP dapat menyelesaikan masalah yang lebih realistis. Kami akan mengatasi masalah kepegawaian yang diuraikan di paruh kedua artikel Toptal saya sebelumnya.

Untuk kepentingan waktu, kami akan langsung menuju versi final model (dengan konflik pribadi, peraturan tenaga kerja, dan tunjangan pekerja sementara) tetapi implementasi model awal yang lebih sederhana juga tersedia di GitHub.

Jadi mari kita mulai dengan menyiapkan masalah:

 from horuslp.core.Variables import BinaryVariableGroup, IntegerVariableGroup from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent, CombinedObjective from horuslp.core.constants import MINIMIZE shift_requirements = [1, 4, 3, 5, 2] # the number of workers we need to staff for each shift # the availability and pay rates of each of the employees 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 } } # the following people can't work together, sadly. ban_list = { ("Daenerys", "Jaime"), ("Daenerys", "Cersei"), ("Jon", "Jaime"), ("Jon", "Cersei"), ("Arya", "Jaime"), ("Arya", "Cersei"), ("Arya", "Melisandre"), ("Jaime", "Cersei") } # Dothraki Staffing Corp will provide us with expensive temp workers DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

Sekarang mari kita tentukan variabelnya, yang dalam hal ini adalah variabel biner yang menentukan apakah seorang pekerja harus bekerja pada shift mereka, dan variabel integer yang menentukan berapa banyak dothraki yang kita pekerjakan untuk setiap shift:

 class StaffingVariables(VariableManager): vars = [] def __init__(self): # like dependent constraints, we can dynamically define variables in the init function super(StaffingVariables, self).__init__() # regular workers varkeys = [] for employee, availability_info in workers.items(): for shift in availability_info['availability']: varkeys.append((employee, shift)) self.vars.append(BinaryVariableGroup('employee_shifts', varkeys)) # dothrakis dothraki_keys = [i for i in range(len(shift_requirements))] self.vars.append(IntegerVariableGroup('dothraki_workers', dothraki_keys, 0, DOTHRAKI_COST))

Sekarang mari kita terapkan batasan yang mengharuskan kita memiliki staf yang cukup untuk setiap shift:

 class SufficientStaffingConstraint(Constraint): # we need to staff people sufficiently dependent_constraints = [] def __init__(self): super(SufficientStaffingConstraint, self).__init__() for shift_num, shift_req in enumerate(shift_requirements): self.dependent_constraints.append(self.build_shift_constraint(shift_num, shift_req)) def build_shift_constraint(self, sn, sr): class ShiftConstraint(Constraint): name = "shift_requirement_%d" % sn def define(self, employee_shifts, dothraki_workers): variables = [val for key, val in employee_shifts.items() if key[1] == sn] variables.append(dothraki_workers[sn]) return sum(variables) >= sr return ShiftConstraint

Sekarang, kita perlu menerapkan batasan yang mencegah orang tertentu bekerja satu sama lain:

 class PersonalConflictsConstraint(Constraint): # some people can't work together dependent_constraints = [] def __init__(self): super(PersonalConflictsConstraint, self).__init__() for person_1, person_2 in ban_list: for shift in range(len(shift_requirements)): self.dependent_constraints.append(self.build_conflict_constraint(person_1, person_2, shift)) def build_conflict_constraint(self, p1, p2, s): class ConflictConstraint(Constraint): name = "Conflict_%s_%s_%d" % (p1, p2, s) def define(self, employee_shifts): if (p1, s) in employee_shifts and (p2, s) in employee_shifts: return employee_shifts[p1, s] + employee_shifts[p2, s] <= 1 return True # returning true will make the constraint do nothing return ConflictConstraint

And finally the labor standards constraint. We'll implement this one slightly differently for demonstrative purposes:

 class LaborStandardsConstraint(Constraint): # we can make someone work more than two shifts a day. dependent_constraints = [] def __init__(self): super(LaborStandardsConstraint, self).__init__() for worker in workers.keys(): # we don't need a constraint builder function, but in those circumstances # we need to set the needed values as class variables and refer to them # via the self keyword due to how python's closure system works class LaborConstraint(Constraint): # we can't use worker directly! wk = worker name = "labor_standard_%s" % worker def define(self, employee_shifts): # we need to access the worker using self. Change self.wk to worker to see # why we need to do this worker_vars = [var for key, var in employee_shifts.items() if key[0] == self.wk] return sum(worker_vars) <= 2 self.dependent_constraints.append(LaborConstraint)

And now let's set up the objectives. The dothraki cost and regular employee costs are calculated very differently, so we'll put them in separate objective components:

 class CostObjective(ObjectiveComponent): # this is the cost function for all the named workers def define(self, employee_shifts, dothraki_workers): costs = [ workers[key[0]]['cost'] * var for key, var in employee_shifts.items() ] return sum(costs) class DothrakiCostObjective(ObjectiveComponent): # don't forget the Dothrakis def define(self, dothraki_workers): dothraki_costs = [ dothraki_workers[sn] * DOTHRAKI_COST for sn in dothraki_workers ] return sum(dothraki_costs) class TotalCostObjective(CombinedObjective): objectives = [ (CostObjective, 1), (DothrakiCostObjective, 1) ]

And now we can define and run the problem:

 class StaffingProblem(Problem): variables = StaffingVariables objective = TotalCostObjective constraints = [SufficientStaffingConstraint, PersonalConflictsConstraint, LaborStandardsConstraint] sense = MINIMIZE # we're minimizing this time, not maximizing. if __name__ == '__main__': prob = StaffingProblem() prob.solve() prob.print_results()

Run the script and you should see the following:

 StaffingProblem: Optimal employee_shifts[('Melisandre', 0)] 0.0 employee_shifts[('Melisandre', 1)] 1.0 employee_shifts[('Melisandre', 4)] 1.0 employee_shifts[('Bran', 1)] 0.0 employee_shifts[('Bran', 2)] 1.0 employee_shifts[('Bran', 3)] 1.0 employee_shifts[('Bran', 4)] 0.0 employee_shifts[('Cersei', 2)] 0.0 employee_shifts[('Cersei', 3)] 0.0 employee_shifts[('Daenerys', 3)] 1.0 employee_shifts[('Daenerys', 4)] 0.0 employee_shifts[('Theon', 1)] 1.0 employee_shifts[('Theon', 3)] 1.0 employee_shifts[('Theon', 4)] 0.0 employee_shifts[('Jon', 0)] 0.0 employee_shifts[('Jon', 2)] 1.0 employee_shifts[('Jon', 4)] 0.0 employee_shifts[('Tyrion', 1)] 1.0 employee_shifts[('Tyrion', 3)] 1.0 employee_shifts[('Tyrion', 4)] 0.0 employee_shifts[('Jaime', 1)] 1.0 employee_shifts[('Jaime', 2)] 0.0 employee_shifts[('Jaime', 4)] 1.0 employee_shifts[('Arya', 0)] 1.0 employee_shifts[('Arya', 1)] 0.0 employee_shifts[('Arya', 3)] 1.0 dothraki_workers[0] 0.0 dothraki_workers[1] 0.0 dothraki_workers[2] 1.0 dothraki_workers[3] 0.0 dothraki_workers[4] 0.0 TotalCostObjective: 335.00 CostObjective: 290.00 * 1 DothrakiCostObjective: 45.00 * 1 shift_requirement_0: 1.00 shift_requirement_1: 4.00 shift_requirement_2: 3.00 shift_requirement_3: 5.00 shift_requirement_4: 2.00 Conflict_Jon_Cersei_2: 1.00 Conflict_Jon_Jaime_2: 1.00 Conflict_Jon_Jaime_4: 1.00 Conflict_Daenerys_Cersei_3: 1.00 Conflict_Daenerys_Jaime_4: 1.00 Conflict_Arya_Jaime_1: 1.00 Conflict_Arya_Cersei_3: 1.00 Conflict_Arya_Melisandre_0: 1.00 Conflict_Arya_Melisandre_1: 1.00 Conflict_Jaime_Cersei_2: 0.00 labor_standard_Melisandre: 2.00 labor_standard_Bran: 2.00 labor_standard_Cersei: 0.00 labor_standard_Daenerys: 1.00 labor_standard_Theon: 2.00 labor_standard_Jon: 1.00 labor_standard_Tyrion: 2.00 labor_standard_Jaime: 2.00 labor_standard_Arya: 2.00

If you compare this with the problem we implemented in the previous tutorial, you should see that the results match.

Membungkus

Congratulations for making it through our first HorusLP tutorial! You're now a competent practitioner of HorusLP.

I hope that this article convinced you of the benefits of architecting your MIP models, and that you will make use of HorusLP in your coming projects. You can find the HorusLP source code, as well as the code for all the tutorials, on GitHub. Additional HorusLP documentation and a tutorial page will be added to GitHub very soon.

As HorusLP is a fairly new project, we would love to hear from you and incorporate your input. If you have any questions, comments, or suggestions, please drop me a line either through Toptal or using the contact information you can find on GitHub. I hope to hear from you soon!