Gelişmiş LP Çözme

LP teknolojisinin olgunluğuna rağmen, bazı kullanım alanları daha gelişmiş teknikler gerektirir. Örneğin, her birinin güçlü ve zayıf yönleri olan bir dizi farklı LP algoritması ve uygulaması mevcuttur. Dahası, sayısal kararsızlık, çözücülerin yavaşlamasına veya belirli modelleri çözememesine neden olabilir.

Bu rehberde LP çözücülerden en yüksek performansı ve güvenilirliği elde etmenize yardımcı olacak kavramlar tanıtılıp örnekler bulunur.

Kavramlar

Bu bölümde LP çözücülerin ileri düzey kullanımıyla ilgili temel kavramlar açıklanmaktadır. Okuyucuların LP'de ikililik kavramını bildiğini varsayıyoruz.

LP algoritmalarının aileleri

LP için aşağıdaki algoritma sınıflarına VEYA araçları aracılığıyla erişilebilir.

  1. İlk pratik LP algoritması olan Simplex algoritması, hâlâ en popüler olanıdır. Algoritma, uygun bölgenin köşe noktaları boyunca ilerler ve optimum bir çözüme ulaşana kadar hedef fonksiyonunun değerini yinelemeli bir şekilde iyileştirir. İki tür tek yönlü algoritma vardır:

    1. Primal Simplex, primal uygun bölgenin köşelerinde adım adım ilerler. Bu varyant, özellikle uygun olan birincil bölgenin sabit olduğu çeşitli hedef fonksiyonlara sahip bir dizi LP problemini çözmede etkilidir.
    2. Çift tek yönlü uygun ikili uygun bölgenin köşelerinde adımlar atar. Bu varyant, özellikle çift uygulanabilir bölgenin sabit olduğu (örneğin yalnızca değişkenlerin sınırları değiştiğinde) bir dizi LP problemini çözmede etkilidir. Bu nedenle çift tekx, MIP çözücülerde yaygın olarak kullanılır.

  2. Bariyer veya iç nokta yöntemleri, LP için ikinci pratik algoritma ailesidir. Bariyer yöntemleri, verimli (polinom zaman) yakınsaklığın teorik garantilerini pratikte güvenilir performansla eşleştirir. Düşük performans gösterdiğinde tek yönlü algoritmayı tamamlarlar. Örneğin, bazı çözücüler hem tek hem de bariyerleri paralel olarak çalıştırmayı teklif eder ve çözümü ilk bitiren algoritmadan döndürür.

  3. Birinci dereceden yöntemler, iterasyonlara yön vermek için özel olarak gradyan bilgilerini (yani birinci derece türevleri) kullanan bir algoritma ailesidir. Gradyan iniş iyi bilinen bir örnektir. Bu yöntemler, doğrusal olmayan optimizasyon ve makine öğreniminde popülerdir. LP söz konusu olduğunda birinci dereceden yöntemler, basit ve bariyerden daha büyük sorunlara ölçeklenebilir ve ayrıca çok daha küçük bellek gereksinimleri olabilir. Ayrıca sayısal sorunlara karşı daha hassastırlar ve yüksek doğrulukta çözümler bulmakta zorlanabilirler.

Aşağıdaki tabloda, VEYA araçlarında kullanılabilen LP çözücüler listelenmiştir. Bu tabloda, her bir çözücüde, üç algoritma ailesinden hangisinin uygulandığı gösterilmiştir.

Çözme aracı Tek Tek Bariyer İlk sipariş
Clp X X
OSBML X X
GlopG X
GLPK X X
GurobiL X X
PDLPG X
XpressL X X

G, çözücünün Google tarafından geliştirildiğini gösterir. L, çözücü için ilgili üçüncü taraf geliştirici tarafından verilen bir lisans gerektiğini belirtir.

Hangi çözücülerin ve algoritmaların kullanılacağıyla ilgili öneriler için Öneriler bölümüne bakın.

Çözüm tam olarak ne anlama geliyor?

LP çözücülerden en iyi şekilde yararlanmak için bir çözücü, bir LP sorununa çözüm bulduğunu iddia ettiğinde ne ima edildiğini anlamak önemlidir. Bu bölümde, bu soruyu yanıtlamak için gereken temel bilgiler, özellikle de çözümlerin sayısal tamlığı ve benzersiz olmaması göz önünde bulundurulur.

Toleranslar

LP çözücüler hemen hemen her zaman kayan nokta aritmetiği kullanır ve bu nedenle çözümleri sayısal hataya neden olur. Bunu hesaba katmak ve zaten yeterince iyi olan çözümler üzerinde çaba göstermekten kaçınarak performansı artırmak için, çözücüler bu çözümler belirli toleranslara kadar olan koşulları karşıladığında çözümleri kabul eder ve bir sorunu çözdüğünü iddia eder.

Doğrusal programlama problemlerini ele alma

$$ \begin{align*} \min\quad & -2x_1 - x_2 \\ \text{s.t.}\quad& x_1 + x_2 \le 1\\ & x_1, x_2 \ge 0 \end{align*} $$

ve ilişkili ikili problemi

$$ \begin{align*} \max\quad& y \\ \text{s.t.}\quad& -2 - y \ge 0\\ &-1 - y \ge 0 \\ &y \le 0 \end{align*} $$

Bu problem çifti, $ x_1 = 1, x_2 = 0 $ ve ikili çözüm $ y = -2 $ şeklinde benzersiz bir optimum çözümüne sahiptir. Aşağıdaki çözümlerden hangisi çözücü tarafından optimum olarak kabul edilebilir? Bunu yanıtlamak için aşağıdaki miktarları tanımlarız:

  • İkilik boşluğu, asal hedef değeri ile ikili hedef değeri arasındaki farktır. Bu durumda, $ |(-2x_1 - x_2) - y| $.
  • Primal uygulanabilirlikler, temel kısıtlamaların ihlalidir. Bu örnekte, $ (\max\{ (x_1+x_2) - 1, 0 \}, \max\{-x_1, 0\}, \max\{-x_2, 0\}) $.
  • İkili uygulanabilirlik, ikili kısıtlamaların ihlalidir. Bu durumda, $ (\max\{ 2 + y, 0 \}, \max\{ 1 + y, 0 \}, \max\{ y, 0 \}) $.

Bir çözücü; ikili boşluk, primal uygulanabilirlikler ve çift uygulanabilirlikler belirli bir tolerans değerinden daha küçükse bir çözümü optimum olarak tanımlar.1

Özellikle toleransların uygulanması, çözücüler ve algoritmalar arasında hem doğal hem de eş zamanlı olmayan nedenlerle farklılık gösterir. Örneğin, tek yönlü algoritmadaki ikilik boşluğu yalnızca sayısal hatalardan kaynaklanırken, tam aritmetikte bile ilkel ve çift uygulanabilirlikler mevcut olabilir. Bazı yöntemler, $ x_1 \ge 0, x_2 \ge 0, $ ve $ y \le 0 $ koordinasyona sahip diğer problemlerin sınır kısıtlamalarını doğrudan uygular. Ancak bazı yöntemler, $x_1 \ge 0, x_2 \ge 0, $ ve $ y \le 0 $ gibi diğer problemlerin sınır kısıtlamalarını doğrudan uygular. Diğerleri ise $x_1 + x_2 \le 1$ gibi doğrusal kısıtlamaların ihlallerinden farklı şekilde

Toleransların etkisine ilişkin bir örnek olarak yukarıdaki ilkel-çifte uygulanan $ \epsilon = \frac{1}{2} $ mutlak toleransını dikkate alın. Çözüm $ x_1 = 1,5, x_2 = 0, y = -3 $ için sıfır dualite boşluğu ve tamamı $ \epsilon $ değerinden düşük ya da bu değere eşittir.Dolayısıyla bir çözücü, bu çözümü "optimum" ilan edebilir. Ancak nesnel değeri (-3), gerçek optimum hedef değerinden -2 farklıdır. Tipik varsayılan $ \epsilon $ değerleri, $10^{-6}$ ile $10^{-8}$ arasındadır. Bu da bu tür uç nokta örneklerini nadir görülen ancak imkansız hale getirmez.

Çözüm türleri

LP sorunları birden fazla optimum çözüme sahip olabilir. Toleransları hesaba katarken bu durum daha da yüksektir. Yukarıda sunulan üç farklı LP algoritmaları ailesinin döndürdüğü çözümlerin özelliklerini kısaca ele alacağız.

Tek yönlü algoritmalar her zaman uygun bölgenin köşelerini veya köşe noktalarını döndürür. Bu çözümler daha seyrek olma eğiliminde oldukları için bazı durumlarda tercih edilir.

Bariyer ve birinci dereceden yöntemler genellikle köşe noktalarını döndürmez. (Teori, bu kılavuzun kapsamı dışında kalan ek nitelikler sağlar.)

Geçmişteki nedenlerle ve tepe noktası çözümlerinin çekici özellikleri olduğundan, çözücüler genellikle varsayılan olarak, bir bariyer algoritması tarafından bulunan bir çözümden optimum köşe noktasına gitmek için bir çapraz geçiş prosedürü uygular. Birinci dereceden yöntemlerle bulunan çözümler için şu anda çapraz geçiş özelliği sunulmamaktadır.

Öneriler

LP çözücülerin ileri düzey kullanımı için aşağıdaki önerilerde bulunuruz.

Sorun verilerini ölçeklendirme

Çözücüler, sayısal sorunlar nedeniyle modellerde yavaş yakınlaşma veya başarısızlıklarla karşılaşabilir. Bu tür sorunların birçok nedeni olabilir. Burada bir örnek verelim.

LP modellerinde çok küçük veya büyük sayısal sabitlerin görünmesi yaygın bir durumdur. Yukarıdaki örneği genişleterek, "sağlayıcı 1" veya "sağlayıcı 2"ye atanmış müşterilerin oranını \(x_1\) \(x_2\) gösteriyorsa ve bu müşterilere hizmetten en iyi şekilde yararlanmak istiyorsak aşağıdaki amaç işlevini yazabiliriz:

$$ \min -c_1x_1 - c_2x_2 $$

Bu örnekte:

  • $ c_1 $ müşterileri 1. sağlayıcıya atamanın avantajıdır
  • c_2 $ müşterileri 2. sağlayıcıya atamanın avantajıdır

Aşağıdaki kısıtlamaları karşılayan ikililer, $ \epsilon $ mutlak tolerans değeri ile uygun olarak kabul edilir:

  • $ y \le -c_1 + \epsilon $,
  • $ y \le -c_2 + \epsilon $.

$ c_1 $ ve $ c_2 $ fayda birimleri, $ \epsilon $ ile aynı ölçekte olan küçük kesirli değerlerse ikili uygulanabilirlik koşulları oldukça zayıf hale gelir. Bu nedenle, çok alt düzeyde bir asal optimum belirlenebilir.

Diğer yandan, avantaj birimleri "mikrodolar" (1.000 000 mikrodolar = 1 dolar) ise elde edilen çok büyük mutlak değerler çözümde çok yüksek kesinlik ister ve kayan nokta sayılarının sınırları nedeniyle muhtemelen makul olmayan bir yükseklikte olur. Problem bu şekilde oluşturulursa çözücüler yakınlaşmayabilir. İleri düzey modelciler, iyi oluşturulmuş bir problemi formüle ederken, problem verilerinin çözücünün toleranslarına uygun bir şekilde ölçeklendirilip ölçeklendirilmediğini düşünmelidir.

Toleranslar, sayısal hataları önlemenin yanı sıra daha iyi performans için ayarlanmış olabilir. Simplex ve bariyer yöntemleri toleranslara çok duyarlı değildir ancak çözümün sonunda ilerlemenin durduğu gözlemlenirse bazen daha yüksek toleranslardan yararlanabilir. Öte yandan, birinci dereceden yöntemler genellikle çok daha hassastır. Birinci dereceden yöntemleri kullananlar, bağlamın izin verdiği ölçüde toleransları gevşeterek daha hızlı çözümlerden yararlanabilir.

Glop'un toleransları için GlopParameters içindeki primal_feasibility_tolerance, dual_feasibility_tolerance ve solution_feasibility_tolerance öğelerine bakın. Algoritmada primal_feasibility_tolerance ve dual_feasibility_tolerance'nin kullanıldığını, sayısal sorunları işaretlemek için ise solution_feasibility_tolerance'nin çözüm sonrası işaretlendiğini unutmayın. PDLP için eps_optimal_absolute ve eps_optimal_relative hükümlerine bakın.

Bu tür sorunlar hakkında daha fazla bilgi edinmek için Gurobi'nin Sayısal Sorunlar için Yönergeler sayfasına bakın. Yönergeler Gurobi kullanıcıları için yazılmış olsa da birçok ilkeler genel olarak geçerlidir.

Çözücü ve algoritma seçimi

Çözücü ve algoritma seçiminin ne kadar büyük olabileceğine dair bir örnekle başlıyor ve ardından LP çözücüleri seçmeye yönelik bir kılavuz sunuyoruz.

Uygulamada değişkenlik

Hans Mittelmann tarafından LP çözücüleri karşılaştırmak için kullanılan bir grup örnekteki çözüm sürelerini karşılaştırarak LP algoritmaları ve çözücüler arasındaki performanstaki değişkenliği gösteriyoruz. Örnekler, göreli performansın uç noktalarını göstermek için açık bir şekilde seçilir ve tipik davranışı temsil etmeyebilir.

Glop'un primal ve çift tekx yöntemleri, Gurobi'nin bariyer yöntemi (bir köşe çözümü bulan çapraz geçişli ve çapraz geçişsiz) ile birinci dereceden bir yöntem olan PDLP ile yüksek ve düşük kesinlik düzeyi karşılaştırılmıştır. Aşağıdaki tabloda, süreler 20 dakika (1.200 saniye) ile sınırlı olmak üzere saniye cinsinden çözülmüştür.

Örnek Glop
Primal Simplex		 Glop
Çift Tek Yönlü		 Crossover ile
Gurobi Bariyeri		 Crossover'sız
Gurobi Bariyeri		 PDLP
Yüksek Hassasiyet		 PDLP
Düşük Hassasiyet
ex10 >1200 >1200 79.7 63.5 8.2 2.7
nug08-3 >1200 252.8 144,6 3.2 1.1 0,9
savsched1 >1200 >1200 156.0 22,6 46.4 32.4
wide15 >1200 % >1200 >1200 916,4 56.3
bina enerjisi 178.4 267.5 12,8 12.3 >1200 157.2
s250r10 12.1 520.6 15.2 16.4 >1200 >1200
Çözücü Sürümü VEYA-Araçlar 9.3 VEYA-Araçlar 9.3 Gurobi 9.0 Gurobi 9.0 VEYA-Araçlar 9.3 VEYA-Araçlar 9.3
solver_specific_parameters (varsayılanlar) use_dual_simplex: true Method 2, Threads 1 Method 2, Crossover 0, Threads 1 termination_criteria { eps_optimal_absolute: 1e-8 eps_optimal_relative: 1e-8 } termination_criteria { eps_optimal_absolute: 1e-4 eps_optimal_relative: 1e-4 }

Bu sonuçlardan şu sonucu çıkarıyoruz.

  • Algoritmaların ve çözücülerin göreli performansı, tek bir örnekteki büyüklük sıralamasına göre değişiklik gösterebilir.
  • Hiçbir algoritma ve çözücü, eşit düzeyde diğerlerine göre daha iyi değildir.
  • Crossover (varsayılan olarak etkindir), çözme süresini önemli ölçüde artırır.
  • PDLP, düşük hassasiyette bazen yüksek doğruluktan 10 kat daha hızlı çözüm üretebilir.

LP çözücüleri seçmeyle ilgili kısa bir rehber

Hiçbir LP algoritması veya çözücü en iyi yöntem olmadığından, kullanım alanınıza en uygun seçeneği bulmak için aşağıdaki adımları uygulamanızı öneririz. Performans yeterli değilse ilk adımdan başlayıp sonrakine geçin.

  1. Glop'ı deneyin. Neden: Glop, Google'ın primal ve çift singlex yöntemlerini şirket içinde uygulamasıdır. Glop, açık kaynaklıdır ve Google'ın üretim iş yüklerinde güvenilir bir çözümdür.
    • Varsayılan yapılandırma (primal Simplex) iyi performans göstermiyorsa use_dual_simplex: true kullanarak çift tekxe geçiş yapmayı deneyin.
  2. Lisans varsa ticari bir çözücü (CPLEX, Gurobi veya Xpress) deneyin. Tek yönlü ve bariyer yöntemleriyle denemeler yapın. Nedeni: Bu çözücüler, endüstri standardıdır ve son derece optimize edilmiştir. Ayrıca bariyer yöntemleri, Glop'un sunduğu tek yönlü algoritma algoritmalarını tamamlar.
    • Bariyer kullanıyorsanız bir köşe çözümüne ihtiyacınız yoksa "çapraz geçiş"i devre dışı bırakın.
  3. PDLP'yi deneyin. Yakınsak toleransları uygulamanıza göre ayarlayın. Nedeni: PDLP, tek yönlü ve bariyer yöntemlerinin bellek sınırlarına ulaştığı veya çok yavaş olduğu en büyük sorunlar için tasarlanmıştır. PDLP, tam ama yavaş bir çözüm yerine yaklaşık ama hızlı bir çözüm tercih edildiğinde en iyi performansı gösterir.
  4. Bu noktaya kadar gelebildiyseniz artık ileri düzey bir LP kullanıcısısınız! Daha fazla yardım için lütfen VEYA Araçları destek seçenekleri'ne bakın.

  1. Çoğu zaman bundan daha karmaşıktır. Çözücüler bu koşulları genellikle sorunun dönüştürülmüş/basitleştirilmiş bir sürümünde kontrol eder. Buna, presolved sorunu adı verilir. Bazen çözülmüş problemin çözümü, giriş sorununa yönelik bir çözümden çok uzakta olabilir. Bu durum, CPLEX OptimalInfeas veya Glop IMPRECISE gibi olağan dışı durumlara yol açabilir.↩