Araştırmacılar Ufuk Açıcı Sorun İçin Yeni Hız Limitine Yaklaşıyor | Quanta Dergisi

Gezgin satıcı problemi bilinen en eski hesaplamalı sorulardan biridir. Kilometreyi en aza indirerek belirli bir şehir listesi boyunca ideal rotayı sorar. Basit gibi görünse de sorunun oldukça zor olduğu biliniyor. En kısa yolu bulana kadar tüm olası rotaları kontrol etmek için kaba kuvvet kullanabilseniz de, böyle bir strateji sadece bir avuç şehirden sonra savunulamaz hale gelir. Bunun yerine, doğrusal programlama adı verilen, soruna kabaca bir denklem seti olarak yaklaşan ve en iyi çözümü bulmak için olası kombinasyonları metodik olarak kontrol eden titiz bir matematik modeli uygulayabilirsiniz.

Ancak bazen tam sayı tutarlarını içeren problemler için optimizasyon yapmanız gerekir. 500.7 koltuk üreten bir fabrika optimizasyon planının ne faydası var? Bunun için araştırmacılar sıklıkla doğrusal programlamanın bir çeşidine başvuruyorlar. tamsayılı doğrusal programlama (ILP). Üretim planlama, havayolu ekibi planlama ve araç rotalama gibi ayrı kararlar içeren uygulamalarda popülerdir. "Temel olarak ILP, hem teoride hem de pratikte yöneylem araştırmasının ekmek ve tereyağıdır" dedi Santosh VempalaGeorgia Teknoloji Enstitüsü'nde bilgisayar bilimcisi.

ILP'yi ilk formüle ettiklerinden beri 60 yıldan fazla bir süre önceAraştırmacılar, ILP sorunlarını çözen çeşitli algoritmalar keşfettiler, ancak bunların hepsi gerekli adım sayısı açısından nispeten yavaştı. Bulabilecekleri en iyi versiyon (bir tür hız sınırı), problemin değişkenlerinin (bir satıcının bir şehri ziyaret edip etmediği gibi) yalnızca ikili değerleri (sıfır veya 1) kabul edebildiği önemsiz durumdan geliyor. Bu durumda ILP, boyut olarak da adlandırılan değişken sayısına göre üstel olarak ölçeklenen bir çalışma zamanına sahiptir. (Yalnızca bir değişken varsa, olası her kombinasyonu test etmek ve sorunu çözmek yalnızca iki adım alır; iki değişken dört adım, üç ortalama sekiz adım vb. anlamına gelir.)

Ne yazık ki değişkenler sıfır ve 1'in ötesinde bir değer aldığında algoritmanın çalışma süresi çok daha uzun olur. Araştırmacılar uzun zamandır bu önemsiz ideale yaklaşıp yaklaşamayacaklarını merak ediyorlardı. İlerleme yavaş olmuştur, kayıt 1980'lerde belirlendi ve yalnızca artan iyileştirmeler beri yapıldı.

Ama son iş by Victor Reis, şu anda İleri Araştırma Enstitüsü'nde ve Thomas RothvossWashington Üniversitesi'nde onlarca yıldır en büyük çalışma süresi sıçramasını gerçekleştirdi. Olası çözümleri sınırlamak için geometrik araçları birleştirerek, ILP'yi önemsiz ikili durumla hemen hemen aynı sürede çözmek için yeni, daha hızlı bir algoritma oluşturdular. Sonuç, 2023'te en iyi makale ödülünü aldı Bilgisayar Biliminin Temelleri konferans.

"Bu yeni algoritma son derece heyecan verici" dedi Noah Stephens-DavidowitzCornell Üniversitesi'nde matematikçi ve bilgisayar bilimcisi. “Bu, ILP çözümleyicileri için yaklaşık 40 yıldaki ilk [büyük] gelişmeyi temsil ediyor.”

ILP, belirli bir problemi bazı eşitsizlikleri karşılaması gereken bir dizi doğrusal denklem haline dönüştürerek çalışır. Özel denklemler orijinal problemin ayrıntılarına dayanmaktadır. Ancak bu ayrıntılar farklılık gösterse de, ILP sorunlarının temel yapısı aynı kalıyor ve araştırmacılara çok sayıda sorunu çözmenin tek bir yolunu sunuyor.

Bu kolay bir iş olduğu anlamına gelmiyor. 1983 yılına kadar matematikçi hendrik lenstra kanıtladı Bunu başarabilecek ilk algoritmayı sağlayarak genel sorunun çözülebilir olduğunu bile gösterdik. Lenstra ILP'yi geometrik olarak düşündü. İlk olarak, ILP'nin kalbindeki eşitsizlikleri herhangi bir normal çokgen gibi dışbükey bir şekle dönüştürdü. Bu şekil, ister koltuk üretimi ister havayolu planlama olsun, çözmekte olduğunuz bireysel problemin kısıtlamalarını temsil eder, böylece şeklin içi eşitsizlikleri ve dolayısıyla problemi çözebilecek tüm olası değerlere karşılık gelir. Lenstra bu şekle dışbükey gövde adını verdi. Sorunun boyutu bu şeklin boyutunu etkiler: İki değişkenli olarak düz bir çokgen şeklini alır; üç boyutlu olarak bu bir Platonik katıVe benzeri.

Lenstra daha sonra tüm tamsayıları matematikte kafes olarak bilinen sonsuz bir ızgara noktaları kümesi olarak hayal etti. İki boyutlu versiyonu bir nokta denizine benziyor, üç boyutlu versiyonu ise bir binadaki çelik kirişlerin birleştiği noktalara benziyor. Kafesin boyutu aynı zamanda belirli bir problemin boyutuna da bağlıdır.

Belirli bir ILP problemini çözmek için Lenstra, olası çözümlerin tamsayılar kümesiyle buluştuğu yere bakmanız gerektiğini gösterdi: dışbükey gövde ile kafesin kesişiminde. Ve bu alanı kapsamlı bir şekilde araştırabilecek bir algoritma buldu; ancak etkili olabilmesi için bazen sorunu daha küçük boyutlara ayırması ve çalışma zamanına birçok adım eklemesi gerekiyordu.

Sonraki yıllarda birçok araştırmacı bu algoritmanın nasıl daha hızlı çalışabileceğini araştırdı. 1988'de Ravi Kannan ve László Lovász, kaplama yarıçapı adı verilen bir kavramı tanıttılar. ödünç çalışmasından hata düzeltme kodlarıdışbükey gövdenin ve kafesin daha verimli bir şekilde kesişmesine yardımcı olmak için. Kabaca, kaplama yarıçapı, kafesin neresine yerleştirirseniz yerleştirin, dışbükey gövdenin her zaman en az bir tamsayı noktası içermesini sağlar. Sonuç olarak kaplama yarıçapının boyutu aynı zamanda ILP problemini ne kadar verimli çözebileceğinizi de belirler.

Yani her şey ideal kapsama yarıçapının boyutunun belirlenmesine bağlıydı. Maalesef bunun başlı başına zor bir problem olduğu ortaya çıktı ve Kannan ile Lovász'ın yapabileceği en iyi şey, üst ve alt sınırları arayarak olası bir değeri daraltmaktı. Üst sınırın (örtme yarıçapının maksimum boyutu) boyutla doğrusal olarak arttığını gösterdiler.. Bu oldukça hızlıydı ancak ILP çalışma süresini önemli ölçüde hızlandırmaya yetmedi. Sonraki 30 yıl boyunca diğer araştırmacılar biraz daha iyisini yapabildiler.

Nihayetinde Reis ve Rothvoss'un başarılı olmasına yardımcı olan şey, yalnızca kafeslere odaklanan ilgisiz bir matematiksel sonuçtu. 2016'da Oded Regev ve Stephens-Davidowitz gösterdiaslında belirli bir şekle kaç tane kafes noktasının sığabileceğidir. Reis ve Rothvoss bunu diğer şekillere de uyguladılar; bu da onların bir ILP kaplama yarıçapında bulunan kafes noktalarının sayısını daha iyi tahmin etmelerine olanak tanıyarak üst sınırı düşürdü. Regev, "En son atılım, aslında başka tür şekiller de yapabileceğinizin farkına varılmasıyla geldi" dedi.

Bu yeni sıkılaştırılmış üst sınır, Reis ve Rothvoss'un genel ILP algoritmasında çarpıcı bir hızlanma elde etmesine olanak tanıyan büyük bir gelişmeydi. Çalışmaları çalışma zamanını (log n)^O(n), Burada n değişkenlerin sayısı ve O (n)ile doğrusal olarak ölçeklendiği anlamına gelir n. (Bu ifade, ikili problemin çalışma süresiyle "neredeyse" aynı kabul edilir.)

"Bu, matematik, bilgisayar bilimi ve geometrinin kesişiminde elde edilen bir zafer" dedi Daniel Daduş Reis ve Rothvoss'un ILP çalışma süresini ölçmek için kullandığı algoritmanın öncülüğünü yapan Hollanda'daki ulusal araştırma enstitüsü CWI'dan Dr.

Şimdilik, yeni algoritma herhangi bir lojistik sorunu çözmek için kullanılmadı çünkü bundan faydalanmak için günümüz programlarını güncellemek çok fazla iş gerektirecektir. Fakat Rothvoss için bu konunun dışındadır. "Bu, temel uygulamaları olan bir problemin teorik olarak anlaşılmasıyla ilgilidir" dedi.

ILP'nin hesaplama verimliliğinin daha da artırılıp artırılamayacağına gelince, araştırmacılar ideal çalışma zamanına yaklaşmaya devam edeceklerinden hala umutlular - ancak bu yakın zamanda değil. Vempala, "Bu, temelde yeni bir fikir gerektirecektir" dedi.