pengantar

Tulis sebuah solver untuk pemrograman linear integer .

Tantangan

Tugas Anda adalah menulis solver untuk integer linear programming (ILP). Dalam ILP, ketidaksetaraan linear dari set yang tidak diketahui (semuanya adalah bilangan bulat) diberikan, dan tujuannya adalah untuk menemukan minimum atau maksimum dari fungsi linear.

Misalnya, untuk ketidaksetaraan (contoh diambil dari Mixed Integer Linear Programming )

 4x+2y-15≤0
  x+2y- 8≤0
  x+ y- 5≤0
- x      ≤0
   - y   ≤0

dan fungsi objektif 3x+2y, fungsi objektif maksimum harus 12( x=2,y=3), sedangkan minimum harus 0( x=y=0).

Input diberikan sebagai array 2d (atau yang setara mengikuti spesifikasi standar), setiap baris sesuai dengan satu ketidaksetaraan, dengan pengecualian dari baris terakhir. Angka dalam array adalah koefisien, dan ≤0bagian tersebut selalu dihilangkan. Jika ada nelemen di setiap baris, itu berarti ada yang n-1tidak diketahui.

Baris terakhir dari array berhubungan dengan fungsi linear. Koefisien terdaftar.

Misalnya, array input untuk masalah di atas adalah

[[4,2,-15],[1,2,-8],[1,1,-5],[-1,0,0],[0,-1,0],[3,2,0]].

Outputnya harus minimum dan maksimum, diberikan dalam bentuk apa pun yang wajar.

Untuk masalah berikut (dua batasan diambil dari masalah di atas):

[[4,2,-15],[1,2,-8],[1,1,-5],[3,2,0]].

Maksimum masih 12, tetapi minimum tidak ada dan fungsi objektif dapat memiliki nilai negatif yang besar (dalam arti nilai absolut). Dalam hal ini, program harus menampilkan 12, mengikuti nilai palsu yang diputuskan oleh penjawab. Kasus lain adalah bahwa tidak ada solusi sama sekali, misalnya,

[[4,2,-15],[-1,-2,7],[-1,0,3],[0,1,0],[3,2,0]].

Dalam hal ini, nilai-nilai palsu juga harus menjadi output. Akan lebih baik untuk membedakan kasus di mana "nilai optimal" untuk fungsi objektif adalah tak terbatas dan kasus di mana tidak ada solusi sama sekali, tetapi ini tidak perlu.

Input hanya berisi koefisien integer baik untuk ketidaksetaraan dan untuk fungsi tujuan. Semua yang tidak diketahui juga bilangan bulat. Matriks koefisien dari ketidaksetaraan dijamin memiliki peringkat penuh.

Uji Kasus

Kredit ke @ KirillL. untuk menemukan bug di test suite asli dan memperdalam pemahaman saya tentang masalah ILP.

Input
Output

[[4,2,-15],[1,2,-8],[1,1,-5],[-1,0,0],[0,-1,0],[3,2,1]]
[1,13]

[[4,2,-15],[1,2,-8],[1,1,-5],[3,2,0]]
[-inf, 12]

[[4,2,-15],[-1,-2,7],[-1,0,3],[0,1,0],[3,2,0]]
[NaN, NaN]

[[-1,-1,-1,-1,-1,8],[1,1,1,1,0,0],[5,5,5,5,6,7]]
[55, inf]

[[-1,-1,-1,-1,-1,8],[1,1,1,1,0,0],[0,0,0,0,0,4]]
[4, 4]

[[4,2,-15],[-1,-2,7],[-1,0,3],[0,1,0],[0,0,4]]
[NaN, NaN]

Spesifikasi

Tidak perlu khawatir tentang penanganan pengecualian.
Ini adalah kode-golf , jumlah byte terendah yang menang.
Jumlah maksimal yang tidak diketahui: 9. Jumlah maksimal ketidaksetaraan: 12.
Anda dapat mengambil input dan memberikan output melalui formulir standar apa pun , dan Anda bebas memilih format.
Seperti biasa, celah default berlaku di sini.

code-golf math optimization Weijun Zhou
sumber

Generalises codegolf.stackexchange.com/q/155460/194

Peter Taylor

Anda belum secara eksplisit menyebutkannya dalam deskripsi tugas, tetapi saya curiga Anda mencari implementasi asli dari algoritma, dan bukan kode membosankan yang menggunakan perpustakaan yang ada? Namun demikian, saya bermain dengan test case Anda di R dan tidak bisa persis mereproduksi hasilnya. Misalnya, [55, inf] case hanya bekerja ketika variabel terikat menjadi non-negatif. Tapi kemudian kasus [-inf, 12] juga menghasilkan hasil yang normal [0, 12]. Di sisi lain, ketika batas bawah -inf, kasus [55, inf] gagal untuk menyelesaikan dalam skenario min dan max.

Kirill L.

Ya saya mencari implementasi asli.

Weijun Zhou

@ KirillL. Bisakah Anda memberikan vektor di mana fungsi dalam test case [55, inf] memberikan nilai lebih kecil dari 55? Saya baru saja mengeceknya dengan solver online dan kasingnya sepertinya baik-baik saja. Saya memiliki alasan berikut ketika membuat test case ini: Pembatasan pertama membutuhkan jumlah semua variabel bebas menjadi geq 8, tetapi yang kedua membutuhkan jumlah semua kecuali yang terakhir menjadi leq 0. Jika kita pernah mencoba untuk mengurangi Tujuan dengan mengurangi salah satu dari 4 var gratis pertama, itu akan memerlukan var akhir harus ditingkatkan dengan jumlah yang sama maka nilai yang lebih besar untuk tujuan.

Weijun Zhou

Ini cuplikan saya , meskipun tidak berfungsi di TIO karena perpustakaan hilang. Ini memberi 55, tetapi keluar dengan "model tidak terikat" ketika saya batalkan komentar pada garis set.bounds. Sangat mungkin, kesalahan ada di pihak saya. Bisakah Anda juga memberikan tautan ke pemecah online?

Kirill L.

Python 3 , 534 byte

import itertools as t
import operator as o
I=float("inf")
e=lambda p,A:sum([i[0]*i[1]for i in zip(p,A[:-1])])+A[-1]
def w(x,j):
	d=len(x[0])-1;C=[0]*d;v,w=I,I
	while 1:
		L={(*n,):(sum([0 if e(n,A)<=0 else e(n,A)for A in x[:-1]]),j*e(n,x[-1]))for n in [[sum(a) for a in zip(C,c)]for c in t.product(*[[-1,0,1]]*d)]};C,P=min(L.items(),key=o.itemgetter(1))[0],C;v,w,p,q=L[C][0],L[C][1],v,w
		if(all([e(C,A)<=e(P,A)for A in x[:-1]]))*(j*(e(C,x[-1])-e(P,x[-1]))<0)+(p==v>0):return I
		if(p==v)*(q<=w):return j*q
f=lambda x:(w(x,1),w(x,-1))

Cobalah online!

Ikhtisar

Ini adalah algoritma berulang, mulai dari yang asli. Ini mengumpulkan posisi tetangga dan menetapkan fungsi potensial: di x:(a,b)mana xposisi, aadalah jumlah jarak posisi dari setengah ruang dari setiap ketidaksetaraan linear, badalah nilai dari tujuan pada posisi itu.

x:(a,b) < y:(c,d)iff a<cataua=c and b<d

Iterasi berhenti, ketika:

koordinat pertama dari potensi belum menurun dan positif: sistem ini tidak layak
jarak dari setiap setengah ruang telah menurun seperti tujuannya: sistem tidak terikat.
tidak ada yang sebelumnya dan potensi belum menurun: itu adalah nilai optimal.

mmuntag
sumber

Pemrograman Linier Integer