Clever Geek Handbook

PuLP-MiA: Addon Multi-Indeks untuk PuLP (Python Linear Programming Library)

Halo, Habr! Sekarang akan ada posting mini tanpa satu baris kode untuk mereka yang berurusan dengan masalah LP multi-indeks (pemrograman linier) dengan Python dan menyelesaikannya menggunakan perpustakaan port PuLP ... Tidak lama lagi :-)



Saat memformalkan masalah LP, sering kali harus berurusan dengan variabel multi-indeks. Ketika menangani masalah-masalah yang berdimensi besar, sejujurnya ini adalah hal yang lumrah.



Keterkaitan variabel multi-indeks tersebut dalam fungsi tujuan (bentuk linier juga merupakan kriteria pengoptimalan linier) dan batasan (dalam bentuk persamaan linier dan pertidaksamaan) harus dihasilkan secara terprogram. Saat bekerja dengan PuLP (LP library port for Python), ada dua pendekatan utama untuk pembuatan tersebut:



  1. Menghasilkan matriks A (matriks batasan) dengan generator daftar Python secara eksplisit. Misalnya, seperti ini: Masalah Sudoku
  2. Generasi variabel simbolik dengan pengikatan indeks melalui kamus dalam bentuk implisit. Ini dapat dilakukan secara manual melalui dict atau menggunakan plugin PuLP


Masalah LP klasik dari hampir semua dimensi dapat dengan mudah diformalkan dengan salah satu cara ini, tetapi ketika mengembangkan struktur kendala baru (terutama ketika logika keterkaitan variabel menjadi lebih rumit, variabel makna baru muncul, beberapa indeks ditinggalkan atau indeks baru diperkenalkan) agregasi / dekomposisi grup variabel, dll.) membutuhkan pelacakan mudah variabel multi-indeks dalam kode program Python itu sendiri, yang secara langsung tidak ada dalam pendekatan di atas.



Untuk mengatasi masalah ini, diusulkan untuk menggunakan add -on PuLP-MiA (tautan ke repositori dengan deskripsi singkat tentang fungsionalitas).



Penulis jauh dari pemikiran bahwa ini adalah solusi untuk semua masalah yang timbul dalam formalisasi dan solusi masalah LP dengan struktur batasan yang kompleks, namun, dalam praktik bertahun-tahun (terutama ketika modifikasi terjadi dengan interval waktu yang lama), pendekatan tersebut telah terbukti dengan sendirinya, terutama karena fasilitas berikut:



  • Pembuatan / pengikatan ke variabel yang ada terjadi secara otomatis
  • Asosiasi eksplisit dari nama variabel dan indeksnya
  • Nama variabel - string arbitrer
  • Indeks - nilai numerik
  • Jumlah indeks tidak terbatas secara kondisional (mungkin tidak ada indeks sama sekali)
  • Hasil pemecahan masalah LP ditampilkan dalam bentuk kamus, dimana kuncinya adalah variabel multi indeks bukan nol (perilakunya dapat diubah)


Mungkin addon akan sangat berguna bagi seseorang dalam penelitian operasi jangka panjang. Lisensi MIT. Ini dipasang secara tradisional melalui pip .



PS Bagi yang sudah selesai membaca, masih akan kecil



contoh pembentukan rangkaian batasan)) 
from itertools import product
from pulp_mia import Task, Constraint

i_set = list(range(5))
j_set = list(range(5))
m_set = list(range(2))
g_set = list(range(4))
s_set = list(range(5))
k_set = list(range(5))

task = Task(debug=True)
for i, m, g, s, k in product(i_set, m_set, g_set, s_set, k_set):
    a_new = Constraint('<=')
    for j in j_set:
        a_new.setCoeff(('x', i, j, m, g, s, k), 1)
    a_new.setBValue(1)
    task.addConstraint(a_new)

print(task)
#TASK info:
#    NAME: test-task
#    SIZE: 5000 x 1000




(selebihnya, simak uraian singkat tentang addon )



PPS ya, jauh di bawah tenda tinggal kamus biasa.


More articles:


All Articles