Yaguang Yang'ın çalışması, doğrusal programlama için daha önce teorik olarak geliştirilen ve polinom iterasyon sınırı O(√nL) olarak verilen yay-arama tabanlı uygunsuz iç-nokta algoritmasını kullanılabilir bir Matlab çözücüsüne dönüştürmektedir. Yazılım, standart biçimde Ax=b, x≥0 kısıtları altında cTx amaç fonksiyonunu minimize eder; ön-işleme, başlangıç noktası seçimi, seyrek Cholesky sistemlerinin çözümü, yay üzerindeki adım açısının hesaplanması, merkezleme parametresinin seçimi, dejenerasyon yönetimi, son-işleme ve optimalite kontrolünü tek ana işlev altında birleştirir.
Kalite kontrolünde arcLP ile Mehrotra'nın öngörücü-düzeltici iç-nokta algoritmasının Matlab uygulaması aynı başlangıç noktaları, aynı ön/son-işleme ve aynı durdurma ölçütleri altında Netlib doğrusal programlama benchmark problemlerinde karşılaştırılmıştır. Kaynak, test edilen problemlerin tamamında arcLP'nin optimum çözüme ulaştığını bildirir. Tablo 1'in Verianla tarafından yapılan doğrudan sayımı, 51 problemde arcLP'nin 24 kez daha az, 11 kez aynı, 16 kez daha fazla iterasyon kullandığını; toplam iterasyonların 1084'e karşı 1099 olduğunu göstermektedir. Bununla birlikte bazı problemlerde arcLP'nin uygunsuzluk artığı Mehrotra'dan daha büyüktür; dolayısıyla sonuç “arcLP her problemde daha iyidir” biçiminde yorumlanmamalıdır.
Çalışmanın en önemli bilimsel sınırı, O(√nL) yakınsama ispatının bu yazılım makalesinde yeniden türetilmemesidir. Makale söz konusu teorik sonucu önceki çalışmaya dayandırır ve burada esas olarak uygulama mimarisini, sayısal stratejileri ve benchmark davranışını belgelemektedir.
Doğrusal programlamada çözülmek istenen temel problem nedir?
arcLP'nin giriş problemi standart doğrusal programlama biçimidir:
\[ \min c^T x,\qquad \text{öyle ki } Ax=b,\quad x\ge 0. \tag{1} \]
Burada \(A\in\mathbb{R}^{m\times n}\) kısıt matrisi, \(b\in\mathbb{R}^{m}\) sağ taraf vektörü, \(c\in\mathbb{R}^{n}\) amaç katsayıları ve \(x\in\mathbb{R}^{n}\) optimize edilecek karar vektörüdür.
Primal problemin duali kaynakta şöyle verilir:
\[ \max b^T\lambda,\qquad \text{öyle ki }A^T\lambda+s=c,\quad s\ge0. \tag{2} \]
\(\lambda\in\mathbb{R}^{m}\) dual değişken vektörü, \(s\in\mathbb{R}^{n}\) ise dual gevşeklik vektörüdür. İç-nokta yöntemi \((x^0,s^0)>0\) olan iç noktadan başlar ve her \(k\) iterasyonunda \((x^k,s^k)>0\) koşulunu korur. Hedef, doğrusal programlama için optimumluğun gerekli ve yeterli koşullarını veren Karush-Kuhn-Tucker koşullarına ulaşmaktır.
“Infeasible interior-point” ne anlama geliyor?
Buradaki “infeasible” ifadesi problemin çözümsüz olduğu anlamına gelmez. Yöntemin başlangıç ve ara noktalarının bütün eşitlik kısıtlarını tam olarak sağlamak zorunda olmadığı, ancak pozitif iç bölgede ilerlerken primal ve dual artıkların azaltıldığı bir iç-nokta yaklaşımını ifade eder. Bu ayrım, yazılımdaki “infeasible instance” tespitiyle karıştırılmamalıdır; ikincisi gerçekten uygulanabilir çözümü bulunmayan LP örneklerini ifade eder.
Neden yay-arama?
Klasik birçok iç-nokta uygulamasında arama yönü doğrusal bir adım biçiminde ele alınırken arcLP, optimizere doğru bir yay üzerinde ilerler. Kaynak, ilgili adım açısı \(\alpha_k\)'nın analitik olarak hesaplanabildiğini belirtmektedir. Ayrıntılı türetim mevcut yazılım makalesinde yeniden verilmemiş, önceki matematiksel çalışmalara yönlendirilmiştir.
Başlangıç noktası nasıl seçiliyor?
Yazılım iki farklı yöntemle aday başlangıç noktaları üretir ve her aday için şu büyüklüğü değerlendirir:
\[ \max\left\{ \|Ax^0-b\|, \|A^T\lambda^0+s^0-c\|, \frac{(x^0)^Ts^0}{n} \right\}. \tag{3} \]
İlk terim primal eşitlik artığını, ikinci terim dual artığı, üçüncü terim ise başlangıçtaki primal-dual tamamlayıcılık seviyesini temsil eder. arcLP bu ölçütü daha küçük yapan aday başlangıç noktasını seçer. Yazarın gerekçesi, daha küçük başlangıç ölçütünün gerekli iterasyon sayısını azaltabilmesidir; ancak bu ifade kesin bir her-problem garantisi olarak sunulmamaktadır.
Ön-işleme ve son-işleme neden önemli?
Algoritmanın teorik analizi belirli veri varsayımlarına dayanırken gerçek Netlib problemleri bu varsayımları doğrudan karşılamayabilir. arcLP bu nedenle önceki CurveLP çalışmasında geliştirilen ön-işleme prosedürlerini kullanır. Son-işleme de aynı kaynakta tanımlanan yaklaşımı izler. Ana `arcLP` işlevi ön-işlemeyi, gerekiyorsa \(A\) matrisinin tam satır rütbesine getirilmesine yönelik seçeneği, başlangıç noktası seçimini, ana optimizasyon döngüsünü, son-işlemeyi ve son optimalite kontrolünü birlikte yürütür.
Matris ölçekleme konusunda kaynak ne söylüyor?
Çalışma, koşullandırması kötü matrislerde ölçeklemenin geleneksel olarak kullanılmasına rağmen önceki testlerde bunun genel hesaplama verimini artırmadığını ve bu nedenle genel matris ölçeklemenin arcLP uygulamasına dahil edilmediğini belirtir. Bununla birlikte şu oran hesaplanır:
\[ \frac{\max |A_{i,j}|} {\min\{|A_{k,l}|:A_{k,l}\neq0\}}. \tag{4} \]
Bu oran matrisin sıfır olmayan elemanlarının büyüklük aralığını ölçer ve ön-işleme kurallarından birinin uygulanıp uygulanmayacağına karar vermede kullanılır. Kaynağın 2. sayfasındaki `calRatioCondition(A)` işlev açıklaması bu bilgiyi \(A,b,c\) ölçeklemesine karar vermekle ilişkilendirirken, 3. sayfa genel ölçeklemenin uygulanmadığını söyler. Bu nedenle iki ifade aynı şeymiş gibi sessizce birleştirilmemelidir.
Bağımlı satırlar ve Markowitz ölçütü
`makeAfull(A,b,c,x,s,lambda,rB,rC,lOld,xOld,sOld)` işlevi, \(A\)'nın doğrusal bağımlı satırlarını ayıklarken seyrekliği mümkün olduğunca korumak için Markowitz pivot ölçütünü kullanır. Bununla birlikte kaynak, satır bağımlılıklarının kaldırılmasının varsayılan akışa genel bir prosedür olarak eklenmediğini, özellikle dejenerasyon yönetimi gerekli olduğunda devreye alınabilecek bir istisna olduğunu açıklar.
Hesaplamanın en pahalı kısmı: seyrek Cholesky sistemleri
Yazar, Mehrotra yönteminde olduğu gibi arcLP'de de baskın hesaplama maliyetinin seyrek Cholesky sistemlerinin çözümünden kaynaklandığını belirtir:
\[ AD^2A^Tu=L\Lambda L^Tu=v. \tag{5} \]
Burada \(D\) ve \(\Lambda\) köşegen matrisler, \(L\) alt üçgensel matris, \(u\) ve \(v\) vektörlerdir. Matlab'ın kötü koşullandırılmış seyrek sistemlerin bütün özel durumlarını doğrudan karşılamadığı gerekçesiyle uygulama, yazarın önceki çalışmasında açıklanan doğrusal cebir stratejisini kullanır.
Dejenerasyon nasıl ele alınıyor?
Doğrusal programlama problemlerindeki dejenere çözümler iç-nokta yöntemleri için sayısal güçlük oluşturabilir. arcLP bu durum için isteğe bağlı bir prosedür içerir. Ana çağrıdaki \(d\) parametresi bu davranışı denetler: kaynakta \(d=1\) dejenerasyonla ilgilenen işlevi kullanır, \(d=0\) ise varsayılan olarak bu işlevi kullanmaz.
Merkezleme parametresi σk nasıl seçiliyor?
arcLP'nin ayırt edici unsurlarından biri merkezleme parametresi \(\sigma_k\)'nın özelleştirilmiş bir Golden Section aramasıyla belirlenmesidir. Kaynağa göre klasik Golden Section araması aralığı her iterasyonda yaklaşık 0,618 katsayısıyla daraltırken kullanılan özel yapı aralığı 0,5 katsayısıyla küçültmektedir. Yazar bu nedenle parametre aramasının daha hızlı daraldığını ve daha verimli olduğunu savunmaktadır.
Adım açısının yeniden ölçeklenmesi
Hesaplanan yay açısı sayısal kararlılığı artırmak amacıyla her iterasyonda şu şekilde sınırlandırılır:
\[ \alpha_k= \min\{0.9999\alpha_k,\;0.99\pi/2\} <0.99\pi/2. \]
Kaynağın sayısal deneylerine göre bu yeniden ölçekleme, erken iterasyonlarda \(x^k\) ve \(s^k\)'nın sıfıra aşırı hızlı yaklaşmasını önler; böylece Denklem (5)'teki doğrusal sistemlerin çözümündeki sayısal güçlükleri azaltmayı ve algoritmanın sağlamlığını artırmayı amaçlar.
Sınırsız ve uygulanamaz problemler nasıl tespit ediliyor?
arcLP bazı durumları optimizasyon sırasında veya presolve aşamasında sezgisel kurallarla tespit eder. Sınırsızlık için kullanılan temel eşik:
\[ \max_i|x_i|>M,\qquad M=10^{10}. \]
Uygulanamazlık için benzer biçimde:
\[ \max_i|\lambda_i|>M \]
kontrolü kullanılır. Ayrıca pozitif \(x\) ve \(s\)'yi korurken duality gap'i azaltacak adım bulunamaması da uygulanamazlık göstergesi olarak ele alınır. Hem primal hem dual problemin uygulanamaz olduğu durumlar için maksimum iterasyon sayısına ulaşılması bir raporlama koşuludur.
Presolve aşamasında ise örneğin \(A\)'nın bir sütunu tamamen sıfır ve ilgili amaç katsayısı \(c_i<0\) ise, \(x_i\) kısıtları etkilemeden sınırsız büyüyebildiği ve minimizasyon amaç değerini sınırsız düşürebildiği için problem sınırsız olarak tespit edilebilir. Yazar bu durum tespit edilirse ana optimizasyon döngüsüne geçmeden işlemin sonlandırıldığını belirtmektedir.
Burada önemli sınır, makalenin kendi ifadesiyle bu mekanizmaların üzerinde “some numerical tests” yapılmış olması ve sonuçların “reasonable detection” sağlamasıdır. Dolayısıyla bunlar kapsamlı biçimde kanıtlanmış genel bir infeasibility/unboundedness sertifika teorisi olarak sunulmamalıdır.
Durdurma ölçütü
Ana durdurma ölçütü primal artık, dual artık ve dualite ölçüsünü birlikte normalize eder:
\[ \frac{\|r_b^k\|}{\max\{1,\|b\|\}} + \frac{\|r_c^k\|}{\max\{1,\|c\|\}} + \frac{\mu_k} {\max\{1,|c^Tx^k|,|b^T\lambda^k|\}} <10^{-8}, \]
burada
\[ r_b^k=Ax^k-b, \qquad r_c^k=A^T\lambda^k+s^k-c. \]
Program ayrıca iyi bir arama yönü bulunamaması durumunda \(\alpha_x^k<10^{-8}\) ve \(\alpha_s^k<10^{-8}\) olduğunda durabilir. Kaynak, artıkların ciddi biçimde kötüleştiği sayısal durumlar ve \(\mu<10^{-8}\) için de ek durdurma kontrolleri tanımlar.
Çalışmanın desteklediği sonuçlar
- arcLP'nin standart biçimli doğrusal programlama problemlerini çözebilen çalışan bir Matlab uygulaması olduğu gösterilmektedir.
- Uygulama, kaynakta verilen Netlib testlerinin tamamında optimum çözüm üretmiştir.
- Tablo 1, arcLP'nin Mehrotra uygulamasına karşı iterasyon ve eşitlik-kısıtı artığı bakımından birçok problemde rekabetçi olduğunu göstermektedir.
- Teorik olarak O(√nL) polinom iterasyon sınırına sahip algoritmanın pratikte de kullanılabilir bir uygulamasının mümkün olduğu gösterilmektedir.
- Yazılım Linux ve Windows'ta test edilmiştir; makale ayrıca bir hakemin macOS'ta çalıştırdığını bildirmektedir.
Çalışmanın desteklemediği sonuçlar
- arcLP'nin her doğrusal programlama probleminde Mehrotra yönteminden daha hızlı olduğu gösterilmemiştir.
- Tablo 1 duvar saati süresinin her problem için arcLP lehine olduğunu kanıtlamaz; tabloda temel olarak iterasyon, amaç değeri ve uygunsuzluk raporlanmaktadır.
- Bu 2026 metamakale O(√nL) sınırının tam matematiksel ispatını yeniden sunmamaktadır.
- Kaynakta verilen uygulanamazlık ve sınırsızlık sezgiselleri bütün olası LP örnekleri için kusursuz bir sınıflandırıcı olarak kanıtlanmamıştır.
- MATLAB kodunun bütün ticari LP çözücülerinden evrensel olarak üstün olduğu sonucu çıkarılamaz.
Türkiye açısından olası önemi
Çalışma Türkiye verisiyle yapılmış bir yerel araştırma değildir. Buna rağmen doğrusal programlama; üretim planlama, enerji sistemleri, lojistik, ulaştırma, çizelgeleme, kaynak tahsisi ve mühendislik optimizasyonunda kullanılan temel matematiksel yapılardan biridir. Bu nedenle açık kaynaklı ve teorik yakınsama özelliği belgelenmiş bir Matlab çözücüsünün Türkiye'deki üniversite ve mühendislik araştırmalarında öğretim, algoritma karşılaştırması ve yöntem geliştirme açısından değeri olabilir. Ancak gerçek endüstriyel kullanım için problem ölçeği, veri koşullandırması, donanım, doğrulama gereksinimi ve mevcut üretim yazılımlarıyla entegrasyon ayrıca değerlendirilmelidir.
Çalışmanın Yöntemi ve Bulguları
arcLP işlev arayüzü
[x,obj,kk,infe,lambda,s,exflag]=arcLP(A,b,c,d,tol,iter)
| Çıktı | Kaynakta verilen anlam |
|---|---|
| x | Optimal primal çözüm |
| obj | Optimal amaç fonksiyonu değeri |
| kk | Optimum çözüme ulaşmak için kullanılan iterasyon sayısı |
| infe | \(\|Ax-b\|_2\), eşitlik kısıtlarının artığı |
| lambda | Optimal dual çözüm |
| s | Dual gevşeklik değişkeninin karşılık gelen değeri |
| exflag | Çıkış durumu |
Çıkış bayrakları
| exflag | Anlam |
|---|---|
| 0 | Başarılı sonlanma |
| 1 | Kaynak API tanımına göre uygulanamaz problem sertifikası |
| 2 | Kaynak API tanımına göre sınırsız problem sertifikası |
| 3 | Primal ve dual problemlerin her ikisinin uygulanamaz olduğuna ilişkin durum |
| 4 | Eksik giriş verisi: A, b veya c |
Basit doğrulama örneği
Kaynağın verdiği küçük problem:
\[ \min x_1,\qquad x_1+x_2=5,\quad x_1\ge0,\quad x_2\ge0. \]
Buna göre \(A=[1\;1]\), \(b=5\), \(c=[1\;0]^T\)'dir. arcLP, kaynakta bildirildiği üzere beş iterasyonda
\[ x^*=[0\;5]^T \]
çözümünü bulmaktadır.
Netlib kalite kontrolü
Yazar, arcLP ve `mehrotra.m` uygulamalarını Netlib'in Matlab biçimine dönüştürülmüş standart LP problemlerinde aynı ön-işleme, son-işleme, başlangıç noktaları, seçenekler ve durdurma kriterleriyle karşılaştırmıştır. Kaynak, kapsamlı test kümesinde en büyük problem için 16.675 kısıt ve 104.374 değişken bulunduğunu belirtmektedir.
Tablodaki “+” işaretli problemlerde dejenerasyon seçeneği yalnız Mehrotra yöntemi için açılmış; “*” işaretli problemde ise her iki yöntem için açılmıştır.
| Problem | Mehrotra iter. | arcLP iter. | Mehrotra amaç | arcLP amaç | Mehrotra uygunsuzluk | arcLP uygunsuzluk |
|---|---|---|---|---|---|---|
| Adlittle | 15 | 16 | 2.2549e+05 | 2.2549e+05 | 3.4e–08 | 3.0e–11 |
| Afiro | 9 | 9 | –464.7531 | –464.7531 | 8.0e–12 | 6.2e–13 |
| Agg | 22 | 20 | –3.5992e+07 | –3.5992e+07 | 5.2e–05 | 3.7e–06 |
| Agg2 | 20 | 21 | –2.0239e+07 | –2.0239e+07 | 5.2e–07 | 3.1e–08 |
| Agg3 | 18 | 20 | 1.0312e+07 | 1.0312e+07 | 8.8e–09 | 1.5e–08 |
| Bandm | 22 | 20 | –158.6280 | –158.6280 | 8.3e–10 | 3.6e–11 |
| Beaconfd | 11 | 11 | 3.3592e+04 | 3.3592e+04 | 1.4e–10 | 1.8e–12 |
| Blend | 14 | 14 | –30.8122 | –30.8122 | 4.9e–11 | 1.6e–12 |
| Bnl1 | 35 | 34 | 1.9776e+03 | 1.9776e+03 | 3.4e–09 | 2.9e–09 |
| Bnl2+ | 38 | 35 | 1.8112e+03 | 1.8112e+03 | 9.3e–07 | 3.5e–06 |
| Brandy | 19 | 24 | 1.5185e+03 | 1.5185e+03 | 6.2e–08 | 2.4e–06 |
| Degen2+ | 17 | 19 | –1.4352e+03 | –1.4352e+03 | 2.0e–10 | 5.9e–10 |
| Degen3* | 22 | 35 | –9.8729e+02 | –9.8729e+02 | 1.2e–09 | 8.6e–08 |
| fffff800 | 31 | 28 | 5.5568e+05 | 5.5568e+05 | 7.7e–04 | 3.7e–09 |
| Israel | 29 | 27 | –8.9665e+05 | –8.9664e+05 | 1.8e–08 | 3.4e–08 |
| Lotfi | 18 | 16 | –25.2647 | –25.2646 | 2.7e–07 | 7.8e–09 |
| Maros_r7 | 21 | 20 | 1.4972e+06 | 1.4972e+06 | 6.4e–09 | 1.7e–09 |
| Osa_07+ | 35 | 32 | 5.3578e+05 | 5.3578e+05 | 1.5e–07 | 8.4e–10 |
| Osa_14 | 37 | 42 | 1.1065e+06 | 1.1065e+06 | 3.0e–08 | 5.2e–09 |
| Osa_30 | 36 | 42 | 2.1421e+06 | 2.1421e+06 | 1.3e–08 | 1.3e–08 |
| Qap12 | 24 | 23 | 5.2289e+02 | 5.2289e+02 | 6.2e–09 | 2.9e–10 |
| Qap15+ | 44 | 28 | 1.0410e+03 | 1.0410e+03 | 1.5e–05 | 8.4e–08 |
| Qap8+ | 13 | 12 | 2.0350e+02 | 2.0350e+02 | 7.1e–09 | 6.2e–11 |
| Sc105 | 11 | 11 | –52.2021 | –52.2021 | 9.8e–11 | 2.2e–12 |
| Sc205 | 12 | 12 | –52.2021 | –52.2021 | 8.8e–11 | 4.4e–11 |
| Sc50a | 9 | 10 | –64.5751 | –64.5751 | 8.3e–08 | 8.5e–13 |
| Sc50b | 8 | 10 | –70.0000 | –70.0000 | 9.1e–07 | 3.6e–12 |
| Scagr25 | 18 | 19 | –1.4753e+07 | –1.4753e+07 | 4.6e–09 | 1.7e–08 |
| Scagr7 | 17 | 17 | –2.3314e+06 | –2.3314e+06 | 1.1e–07 | 7.0e–10 |
| Scfxm1+ | 22 | 21 | 1.8417e+04 | 1.8417e+04 | 1.6e–08 | 3.3e–05 |
| Scfxm2 | 26 | 24 | 3.6660e+04 | 3.6660e+04 | 2.6e–08 | 4.8e–05 |
| Scfxm3+ | 23 | 23 | 5.4901e+04 | 5.4901e+04 | 9.8e–08 | 1.2e–04 |
| Scrs8 | 30 | 28 | 9.0430e+02 | 9.0430e+02 | 1.8e–10 | 1.0e–10 |
| Scsd1 | 13 | 11 | 8.6666 | 8.6666 | 8.7e–14 | 3.3e–15 |
| Scsd6 | 16 | 16 | 50.5000 | 50.5000 | 8.6e–15 | 2.6e–13 |
| Scsd8 | 14 | 15 | 9.0500e+02 | 9.0500e+02 | 1.3e–10 | 2.6e–13 |
| Sctap1 | 27 | 20 | 1.4123e+03 | 1.4123e+03 | 0.0031 | 1.4e–11 |
| Sctap2 | 21 | 22 | 1.7248e+03 | 1.7248e+03 | 4.4e–07 | 1.4e–12 |
| Sctap3 | 22 | 21 | 1.4240e+03 | 1.4240e+03 | 5.9e–07 | 1.9e–12 |
| Share1b | 25 | 26 | –7.6589e+04 | –7.6589e+04 | 1.5e–06 | 1.9e–07 |
| Share2b | 15 | 15 | –4.1573e+02 | –4.1573e+02 | 7.9e–10 | 1.4e–10 |
| Ship04l | 18 | 19 | 1.7933e+06 | 1.7933e+06 | 2.9e–11 | 1.3e–10 |
| Ship04s | 20 | 19 | 1.7987e+06 | 1.7987e+06 | 4.5e–09 | 3.1e–10 |
| Ship08l | 22 | 20 | 1.9091e+06 | 1.9090e+06 | 1.0e–10 | 1.8e–11 |
| Ship08s | 20 | 19 | 1.9201e+06 | 1.9201e+06 | 4.5e–12 | 1.7e–09 |
| Ship12l | 21 | 21 | 1.4702e+06 | 1.4702e+06 | 1.0e–08 | 3.0e–10 |
| Ship12s | 19 | 21 | 1.4892e+06 | 1.4892e+06 | 2.1e–13 | 5.0e–11 |
| Stocfor1+ | 14 | 13 | –4.1132e+04 | –4.1132e+04 | 1.1e–10 | 8.6890e–11 |
| Stocfor2 | 22 | 22 | –3.9024e+04 | –3.9024e+04 | 1.6e–09 | 4.3e–09 |
| Stocfor3 | 38 | 37 | –3.9976e+04 | –3.9977e+04 | 6.4e–08 | 7.7e–08 |
| Truss | 26 | 24 | 4.5882e+05 | 4.5882e+05 | 9.5e–06 | 5.2e–07 |
Tablo 1'in doğrudan sayımında arcLP 24 problemde daha az iterasyon, 11 problemde eşit iterasyon, 16 problemde daha fazla iterasyon kullanmaktadır. Toplam iterasyon sayıları sırasıyla 1084 ve 1099'dur. Uygunsuzluk artığı bakımından arcLP 34 problemde daha düşük, 1 problemde aynı, 16 problemde daha yüksek değere sahiptir. Amaç değerleri tabloda verilen hassasiyette 51 problemin 47'sinde aynıdır; Israel, Lotfi, Ship08l ve Stocfor3 satırlarında son basamak düzeyinde farklar görünmektedir.
Sonuçların tek yönlü olmadığını gösteren örnekler önemlidir. Qap15+ probleminde Mehrotra 44 iterasyon kullanırken arcLP 28 iterasyon kullanmış ve uygunsuzluk 1.5e–05'ten 8.4e–08'e düşmüştür. Sctap1'de 27'ye karşı 20 iterasyon ve 0.0031'e karşı 1.4e–11 uygunsuzluk görülür. Buna karşılık Degen3* probleminde arcLP 35, Mehrotra 22 iterasyon kullanmakta ve arcLP'nin artığı daha büyüktür. Scfxm2'de arcLP iterasyon bakımından avantajlı olsa da uygunsuzluğu 4.8e–05 iken Mehrotra'nın değeri 2.6e–08'dir. Bu dağılım, “rekabetçi ve genel olarak sağlam” yorumunu desteklerken evrensel üstünlük iddiasını desteklemez.
| field | value |
|---|---|
| title | arcLP çözüm zinciri |
| subtitle | Problem verisinden ön-işleme, başlangıç noktası seçimi, yay-arama iterasyonu, seyrek çözümleyici ve son kontrol katmanına uzanan LP çözüm akışı |
- 1. Problem verisi aşamasında A, b ve c standart LP girdileri ile d, tol ve iter seçenekleri çözücü çağrısına aktarılır
- 2. Ön-işleme katmanında presolve kuralları uygulanır ve bazı uygunsuz ya da sınırsız durumlar erken tespit edilebilir
- 3. Başlangıç noktası seçiminde iki aday arasından Denklem (3) ölçütünü daha küçük yapan çözüm alınır
- 4. Ana yay-arama iterasyonu pozitif x ve s bölgelerinde ilerler; yay açısı ile merkezleme parametresi birlikte güncellenir
- 5. Seyrek doğrusal sistem aşamasında AD²Aᵀu = LΛLᵀu = v biçimindeki Cholesky çözümü ana hesaplama yükünü taşır
- 6. Durdurma ve durum tespitinde normalize artıklar, dualite ölçüsü, adım büyüklükleri ve uygunsuz/sınırsızlık kontrolleri değerlendirilir
- 7. Son-işleme ve nihai kontrolde post-process uygulanır; ardından x, obj, kk, infe, lambda, s ve exflag çıktıları döndürülür
fidelity: source-faithful
scope: Kaynakta açıkça verilmeyen yeni algoritmik alt adım eklenmez.
Yazılım kullanılabilirliği
arcLP Matlab ile yazılmıştır. Kaynağa göre Linux ve Windows sistemlerinde kapsamlı biçimde test edilmiştir; bir hakem macOS üzerinde de çalıştığını bildirmiştir. Ek yazılım bağımlılığı belirtilmemiştir. Kullanıcının Matlab kurulu bir sisteme sahip olması gerekir.
Kaynak ayrıca Matlab derleyicilerinin kodu C/C++ veya Fortran'a dönüştürmek için kullanılabileceğini ve derlenmiş kodun hesaplama süresini en az bir mertebe azaltabileceğini belirtmektedir. Bu ifade bu metamakalede ayrı bir zamanlama tablosuyla doğrulanmadığından, yazarın yazılım kullanım notu olarak değerlendirilmelidir.
Kaynak ve Yöntem Notu
Tam özgün çalışma adı: ArcLP: A Matlab Implementation of an O(√nL) Arc-search Infeasible Interior-Point Algorithm for Linear Programming
Yazar: Yaguang Yang. Tek yazardır ve sorumlu yazardır.
Afiliyasyon: Independent Researcher, US.
Kaynak türü: Hakemli Software Metapaper.
Dergi: Journal of Open Research Software, Cilt 14, Sayı 1, Makale 57.
DOI: 10.5334/jors.674.
Yayınevi: Ubiquity Press.
Tarih: 11 Ocak 2026'da gönderilmiş, 28 Temmuz 2026'da kabul edilmiş, 12 Ağustos 2026'da yayımlanmıştır.
Hakemlik durumu: Bu metin hakem değerlendirmesinden geçmiş, yayımlanmış dergi sürümüdür. Aynı başlıklı bir arXiv sürümü bulunsa da bu makalede esas alınan bilimsel kimlik hakemli JORS sürümüdür.
Makale lisansı: Creative Commons Attribution 4.0 International (CC BY 4.0).
Yazılım: arcLP, sürüm 1.0; yazılım lisansı BSD 3-Clause “New” or “Revised”. Makalede depo adı arcLP ve yayıncı Yaguang Yang olarak verilir.
Yazılım yayın tarihi notu: Kaynakta “08/02/2026” yazmaktadır. Tarih biçimi açıkça tanımlanmadığından bu değer ay/gün veya gün/ay biçimine çevrilmeden korunmalıdır.
Finansman: Ayrı bir araştırma hibesi bildirilmemiştir. JORS'un yayın ücretinden feragat ettiği belirtilmiştir; bu yayın ücreti muafiyeti araştırma finansmanı ile karıştırılmamalıdır.
Çıkar çatışması: Yazar çıkar çatışması olmadığını beyan etmektedir.
Veri erişilebilirliği: Ayrı bir veri erişilebilirliği beyanı verilmemiştir. Benchmark problemleri Netlib kaynaklıdır ve yazılım deposu makalede belirtilmiştir.
CRediT/yazar katkıları: Ayrı CRediT beyanı bulunmamaktadır; yazılımın tek katkıcısı Yaguang Yang olarak belirtilmiştir.
Bilimsel yorum sınırı: Bu çalışma bir yazılım metamakalesidir. O(√nL) yakınsama sınırının tam ispatı ve makalede atıfta bulunulan performans profili mevcut 7 sayfalık belgede yeniden türetilmemekte, önceki Kaynak (6)'ya dayandırılmaktadır. Benchmark sonuçları arcLP'nin hesaplamalı olarak rekabetçi olduğunu destekler; her LP örneğinde daha hızlı, daha doğru veya bütün ticari çözücülerden üstün olduğunu kanıtlamaz.
Kaynak sadakati: Bilimsel içerik yüklenen çalışmanın metin, formül ve Tablo 1 verilerine dayanmaktadır. Dış doğrulama yalnız bibliyografik yayın kimliği ve hakemli sürümün doğrulanması için kullanılmış; dış kaynaklardan yeni deneysel veya sayısal bilimsel bulgu eklenmemiştir.
Bir yorum bırakın
E-posta adresiniz yayınlanmayacaktır. Gerekli alanlar * ile işaretlenmiştir