HorusLP-Gurobi: Arsitektur Pengoptimalan Tingkat Tinggi untuk Gurobi

Sebagai teknologi optimasi menjadi lebih canggih, pemecah komersial telah mulai memainkan peran yang semakin penting dalam industri. Dibandingkan dengan pemecah sumber terbuka, solusi komersial cenderung memiliki lebih banyak fitur untuk menyelesaikan model pengoptimalan yang kompleks seperti penyelesaian awal, permulaan hangat, dan penyelesaian terdistribusi.

Salah satu solver komersial paling populer di pasar adalah Gurobi, dinamai menurut salah satu pendiri Zonghao Gu, Edward Rothberg, dan Robert Bixby, masing-masing pelopor dalam ruang solver komersial. Gurobi telah mendukung banyak proyek pengoptimalan profil tinggi dalam sejarah baru-baru ini termasuk proyek alokasi bandwidth FCC dan proyek penugasan kembali tahanan Penjara Negara Bagian Pennsylvania.

Hari ini, kita akan melihat bagaimana HorusLP, sebuah paket perangkat lunak yang menyediakan antarmuka deklaratif tingkat tinggi untuk pemodelan pengoptimalan, terintegrasi dengan API Gurobi untuk menghadirkan pengalaman pemodelan intuitif kepada pengguna sambil memanfaatkan fitur-fitur paling canggih dari Gurobi.

Pengoptimalan: Penyegaran Cepat

Bagi mereka yang tidak akrab dengan optimasi atau riset operasi, optimasi mengacu pada kumpulan teknik matematika yang menemukan nilai optimal variabel dalam sistem persamaan yang tunduk pada sistem kendala. Jika kalimat di atas terdengar agak kering, mungkin sebuah contoh akan membantu mengilustrasikannya.

Misalkan Anda memiliki ransel dengan daya dukung 15 pon. Anda memiliki beberapa item di depan Anda, masing-masing dengan bobot dan nilai uang tertentu:

1. Kamera: berat 2 lbs, nilai $5
2. Figurine: berat 4 lbs, nilai $7
3. Sari: berat 7 lbs, nilai $2
4. Tanduk: berat 10 lbs, nilai $10.

Anda ingin memilih barang untuk dimasukkan ke dalam ransel Anda sehingga berat totalnya tetap di bawah 15 pon tetapi nilainya dimaksimalkan. (Jika Anda memerlukan lebih banyak konteks tentang mengapa kami memasukkan barang-barang bernilai tinggi ke dalam ransel, Anda dianjurkan untuk menggunakan imajinasi Anda untuk sebuah narasi. Narasi kandidat yang baik termasuk menyelamatkan barang-barang dari kebakaran dan pelelangan tanah… atau beberapa aktivitas jahat yang kami lakukan. lebih suka tidak menyebutkan.)

Kita dapat merumuskan masalah sebagai masalah optimasi berikut:

 Let // Each variable stands for whether we put the item into the knapsack Camera = {0, 1} Figurine = {0, 1} Cider = {0, 1} Horn = {0, 1} // Maximize dollar value Maximize 5 * camera + 7 * figurine + 2 * cider + 10 * horn // Weight must stay below 15 pounds 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

Setelah kami merumuskan masalah ini, kami dapat menerapkan teknik pengoptimalan untuk menemukan item terbaik untuk dimasukkan ke dalam ransel kami. Anda dapat menemukan contoh solusi dari artikel saya sebelumnya tentang menyelesaikan masalah optimasi menggunakan Python dan menyelesaikan masalah optimasi menggunakan inti HorusLP API.

Teknik matematika yang mendasarinya cukup menarik, tetapi di luar cakupan artikel ini. Jika Anda ingin mengetahui lebih lanjut, saya sarankan mencari di sini dan di sini, keduanya milik Gurobi.

Gurobi

Sementara masalah pengoptimalan paling awal diselesaikan oleh tim matematikawan yang bekerja dengan kalkulator, sebagian besar masalah pengoptimalan saat ini diselesaikan dengan menggunakan perangkat lunak khusus yang disebut pemecah. Sementara sebagian besar pemecah umumnya dapat menemukan solusi dari sebagian besar masalah pemrograman linier dan bilangan bulat yang dirumuskan dengan baik, beberapa pemecah masalah jauh lebih mampu daripada yang lain. Mereka dapat memecahkan kelas masalah yang tidak dapat dipecahkan oleh orang lain, memecahkan masalah lebih cepat dengan menerapkan matematika mutakhir, atau memecahkan masalah besar dan sulit menggunakan komputer terdistribusi. Fitur tercanggih biasanya disediakan dalam pemecah komersial yang dikembangkan dan dipelihara oleh perusahaan yang mengkhususkan diri dalam membangun pemecah tercepat dan tercanggih.

Gurobi adalah salah satu pemimpin di pasar pemecah masalah komersial, digunakan oleh segmen besar komunitas pengoptimalan termasuk pemerintah, lembaga akademis, dan perusahaan yang beroperasi di industri mulai dari keuangan hingga logistik. Dalam hal kecepatan, gurobi secara konsisten mengungguli beberapa tolok ukur yang digunakan untuk menilai pemecah komersial dan open source.

Gurobi juga dilengkapi dengan API Python yang kuat yang memungkinkan Anda membuat model dari Python. Fitur ini memberi pemodel akses ke semua pustaka manipulasi data Python yang berguna selama konstruksi model, yang sangat membantu dalam prosesnya. Sebagai demonstrasi dari gurobi Python API, berikut adalah bagaimana Anda dapat memodelkan masalah knapsack:

 import gurobipy as gr m = gr.Model() camera = m.addVar(name='camera', vtype=gr.GRB.BINARY) figurine = m.addVar(name='figurine', vtype=gr.GRB.BINARY) cider = m.addVar(name='cider', vtype=gr.GRB.BINARY) horn = m.addVar(name='horn', vtype=gr.GRB.BINARY) m.addConstr(2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 , 'size constraint') m.setObjective(5 * camera + 7 * figurine + 2 * cider + 10 * horn, gr.GRB.MAXIMIZE) m.optimize() print(camera.x) print(figurine.x) print(horn.x) print(cider.x)

Menjalankan contoh akan memberi Anda output berikut:

 Optimize a model with 1 rows, 4 columns and 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Coefficient statistics: Matrix range [2e+00, 1e+01] Objective range [2e+00, 1e+01] Bounds range [1e+00, 1e+00] RHS range [2e+01, 2e+01] Found heuristic solution: objective 14.0000000 Presolve time: 0.01s Presolved: 1 rows, 4 columns, 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Root relaxation: objective 1.700000e+01, 1 iterations, 0.00 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time * 0 0 0 17.0000000 17.00000 0.00% - 0s Explored 0 nodes (1 simplex iterations) in 0.01 seconds Thread count was 4 (of 4 available processors) Solution count 2: 17 14 Optimal solution found (tolerance 1.00e-04) Best objective 1.700000000000e+01, best bound 1.700000000000e+01, gap 0.0000% -0.0 1.0 1.0 -0.0

HorusLP

HorusLP adalah pustaka pemodelan pengoptimalan yang dibangun berdasarkan pengalaman mengembangkan algoritme pengoptimalan. Pustaka pemodelan yang tersedia saat ini kekurangan alat yang diperlukan untuk bekerja dengan jenis masalah yang kompleks dan beragam yang biasanya dihadapi oleh aplikasi komersial riset operasi.

Sementara sebagian besar pustaka pengoptimalan menawarkan antarmuka imperatif tingkat rendah, karena model pengoptimalan menjadi lebih kompleks, alat yang lebih baik diperlukan untuk mengelola kompleksitas. HorusLP adalah perpustakaan yang menyediakan alat tingkat tinggi untuk mengelola kompleksitas ini. HorusLP juga menyediakan alat debugging dan pelaporan yang kuat yang memungkinkan pengembangan dan iterasi lebih cepat.

Pada intinya, HorusLP adalah perpustakaan berorientasi objek yang menyediakan arsitektur yang sangat dibutuhkan di sekitar model pengoptimalan. Dengan memanfaatkan sintaks berorientasi objek Python, perpustakaan HorusLP menyediakan struktur di mana model pengoptimalan dapat dioptimalkan. Hasilnya adalah basis kode yang dipisahkan, modular, dan mudah dibaca.

Jika Anda ingin pengenalan yang lebih mendetail tentang pustaka inti HorusLP dengan contoh kode, Anda dapat menemukan tutorialnya di sini.

Integrasi HorusLP-Gurobi

Sementara API inti HorusLP menyediakan API tingkat tinggi yang nyaman untuk membangun model pengoptimalan, ia dibangun di atas PuLP, yang, meskipun mampu menggunakan Gurobi sebagai pemecah masalah, tidak memiliki akses ke beberapa kemampuan Gurobi yang lebih canggih.

HorusLP-Gurobi adalah versi HorusLP API yang dibuat menggunakan Python API Gurobi. Ini memungkinkan pengguna akses langsung ke fitur-fitur canggih Gurobi, sambil menjaga agar HorusLP API tetap konsisten.

Salah satu filosofi utama yang memandu pengembangan HorusLP-Gurobi adalah konsistensi dengan API inti HorusLP. Dengan menjaga konsistensi struktur minimalis HorusLP, pengguna pemecah sumber terbuka dapat dengan mudah bertransisi menggunakan Gurobi dengan menginstal Gurobi API dan mengganti pernyataan impor.

Untuk model sederhana, model berbasis HorusLP akan mengambil lebih banyak baris kode daripada hanya menggunakan API Python secara imperatif. Namun, saat proses pengembangan berlanjut dan model menjadi lebih kompleks, desain berorientasi objek dan deklaratif dari HorusLP API akan memudahkan debugging dan pengembangan. Orientasi objek juga akan membuat model lebih mudah dibaca, karena definisi model menciptakan pemusatan dan dengan jelas menggambarkan tujuan, batasan, dan variabel, dll.

Tanpa basa-basi lagi, mari selami beberapa contoh kode!

Contoh Kode

API HorusLP Dasar

Karena HorusLP-Gurobi menjaga konsistensi API, kode dari tutorial inti HorusLP dapat dipindahkan dengan perubahan sederhana dalam impor. Namun, untuk menggunakan HoruLP-Gurobi, Anda harus memastikan bahwa Anda telah menginstal pengoptimal Gurobi dan antarmuka Python Gurobi. Anda bisa mendapatkan Gurobi dengan menghubungi mereka di sini.

Setelah Anda menginstal Gurobi, kita bisa mulai dengan pengkodean dengan HorusLP-Gurobi! Mari kita mulai dengan menginstal paket yang diperlukan:

 Pip install horuslp horuslp-gurobi

Setelah instalasi selesai, kita dapat mulai menggunakan HorusLP-Gurobi! Ingat kembali contoh soal knapsack sebelumnya. Kita dapat menggunakan HorusLP-Gurobi untuk memodelkan masalah sebagai berikut:

Pertama, impor perpustakaan yang relevan.

 from horuslp_gurobi.core.Variables import BinaryVariable from horuslp_gurobi.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp_gurobi.core.constants import MAXIMIZE

Tentukan beberapa variabel.

 class KnapsackVariables(VariableManager): # we define variables by declaring the “vars” class variable vars = [ BinaryVariable('camera'), BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn')

Sekarang, kita dapat mendefinisikan batasan menggunakan kelas batasan.

 class SizeConstraint(Constraint): # implement the 'define' function, the variables will get passed in by name def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

Kami kemudian dapat mengimplementasikan tujuan dengan cara yang sama.

 class ValueObjective(ObjectiveComponent): # implement the define function and return the objective expression def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn

Dan akhirnya, kita bisa mendefinisikan masalahnya.

 class KnapsackProblem(Problem): # defining a problem using the Horus API is a matter of setting variables in the subclass variables = KnapsackVariables objective = ValueObjective # constraints is a list variable, since there can be multiple constraints,. constraints = [SizeConstraint] # make sure to set the sense! sense = MAXIMIZE

Dan kami membuat instance masalah dan memanggil fungsi penyelesaian. Ini adalah dimana keajaiban terjadi.

 prob = KnapsackProblem() # instantiate prob.solve() # call the solve method prob.print_results() # optional: print the standard Horus debug report print(prob.result_variables) # optional: print the variable results as a list

Jalankan kode dan Anda akan melihat output berikut:

 Optimize a model with 1 rows, 4 columns and 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Coefficient statistics: Matrix range [2e+00, 1e+01] Objective range [2e+00, 1e+01] Bounds range [1e+00, 1e+00] RHS range [2e+01, 2e+01] Found heuristic solution: objective 14.0000000 Presolve time: 0.01s Presolved: 1 rows, 4 columns, 4 nonzeros Variable types: 0 continuous, 4 integer (4 binary) Root relaxation: objective 1.700000e+01, 1 iterations, 0.00 seconds Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time * 0 0 0 17.0000000 17.00000 0.00% - 0s Explored 0 nodes (1 simplex iterations) in 0.01 seconds Thread count was 4 (of 4 available processors) Solution count 2: 17 14 Optimal solution found (tolerance 1.00e-04) Best objective 1.700000000000e+01, best bound 1.700000000000e+01, gap 0.0000% 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}

Bagian pertama adalah pemecah Gurobi, dan bagian kedua adalah keluaran dari HorusLP. Seperti yang Anda lihat, algoritme menyarankan agar kami mengambil patung dan tanduk, menghasilkan 14 pon item dengan nilai $17.

Salah satu keuntungan menggunakan HorusLP dengan Gurobi adalah Anda mendapatkan banyak informasi “gratis”. Banyak informasi yang biasanya ingin dilihat selama pengembangan, seperti nilai setiap variabel, nilai tujuan akhir, dan nilai kendala secara otomatis dihitung dan dikeluarkan dalam format yang mudah dibaca.

Jika Anda telah membaca artikel sebelumnya tentang inti HorusLP, Anda akan melihat bahwa ini adalah API yang hampir sama persis. Untuk menjaga API tetap sederhana, antarmuka inti HorusLP dan HorsLP-Gurobi identik, dengan perbedaan antara pemecah yang diabstraksikan dalam implementasi superclass.

Jadi, kita akan meninggalkan pengenalan HorusLP pada contoh sederhana ini; contoh yang lebih kompleks yang menunjukkan fitur canggih HorusLP dapat ditemukan di artikel sebelumnya.

Fitur Gurobi

Gurobi menyediakan banyak fitur canggih untuk memecahkan masalah yang kompleks. Sebagian besar fitur dapat diakses melalui objek Model. Untuk memungkinkan kompatibilitas penuh dengan Gurobi API, objek model mudah diakses dari kelas masalah sebagai model .

Misalnya, jika Anda ingin menulis file MPS dari model knapsack, di Gurobi Anda dapat menulis sesuatu seperti m.write('knapsack.mps') . Saat menggunakan HorusLP-Gurobi, Anda cukup:

 # import the problem as usual from horuslp_gurobi.core.Variables import BinaryVariable from horuslp_gurobi.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp_gurobi.core.constants import MAXIMIZE # define the constraint class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 # define the objectives as above class ValueObjective(ObjectiveComponent): def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn # define the variables used by the constraints and objectives class KnapsackVariables(VariableManager): vars = [ BinaryVariable('camera'), BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn') # define the problem as in the above example class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE # instantiate the problem. We don't need to call solve or print any reports. prob = KnapsackProblem() prob.model.write('knapsack.mps') # this is the only bit of new code!

Dan Anda akan melihat file MPS di direktori kerja Anda.

Anda dapat menggunakan antarmuka ini untuk mengakses fitur Gurobi tingkat lanjut seperti menghitung IIS, membuat panggilan balik, atau memberikan petunjuk variabel.

Fitur Gurobi Tingkat Lanjut di Layanan Anda

Hari ini kita melihat versi library HorusLP yang dibangun di atas Gurobi Python API. Selain fitur pelaporan dan debugging dari inti HorusLP, Anda sekarang memiliki akses ke semua fitur canggih Gurobi yang dapat diakses dengan mulus melalui integrasi dengan API Python Gurobi.

Jika Anda adalah pengguna Gurobi saat ini atau seseorang yang tertarik menggunakan optimasi Gurobi, saya harap Anda mencoba HorusLP! Anda dapat menemukan kode contoh, membuat saran, atau berkontribusi pada HorusLP-Gurobi di GitHub.