Tamsayılı programlama - Integer programming

Bir tamsayı programlama problemi olan matematiksel optimizasyon veya fizibilite değişkenlerin bazıları veya tamamı olmak sınırlandırıldığı programı tamsayılar . Birçok ayarları terimi anlamına gelir tamsayı programlama doğrusal amaç fonksiyonu ve kısıtlamalar (tamsayıdır kısıtlamaları dışında) olduğu ve, (İLP), lineer .

Tamsayı programlama NP-tamamlanmıştır . Bilhassa, bilinmeyenlerin ikili olduğu ve sadece kısıtlamaların yerine getirilmesi gereken 0-1 tamsayılı doğrusal programlamanın özel durumu, Karp'ın 21 NP-tamamlanmış problemlerinden biridir .

Bazı karar değişkenleri ayrık değilse, problem karma tamsayılı programlama problemi olarak bilinir .

ILP'ler için kanonik ve standart form

Tamsayılı doğrusal programlamada, kanonik biçim standart biçimden farklıdır . Kanonik biçimde bir tamsayılı doğrusal program şu şekilde ifade edilir ( karar verilmesi gerekenin vektör olduğuna dikkat edin ):

ve standart formdaki bir ILP şu şekilde ifade edilir:

nerede vektörler ve bir matristir, burada tüm girişler tam sayıdır. Doğrusal programlarda olduğu gibi, standart formda olmayan ILP'ler, eşitsizlikleri ortadan kaldırarak, gevşek değişkenleri ( ) tanıtarak ve işaret kısıtlamalı olmayan değişkenleri iki işaret kısıtlamalı değişkenin farkıyla değiştirerek standart forma dönüştürülebilir.

Misal

LP gevşemeli IP politop

Sağdaki çizim aşağıdaki sorunu göstermektedir.

Uygulanabilir tamsayı noktaları kırmızı ile gösterilir ve kırmızı kesikli çizgiler, tüm bu noktaları içeren en küçük dışbükey çokyüzlü olan dışbükey gövdelerini gösterir. Mavi çizgiler, koordinat eksenleri ile birlikte, bütünlük kısıtlaması olmaksızın eşitsizlikler tarafından verilen LP gevşemesinin polihedronunu tanımlar. Optimizasyonun amacı, siyah noktalı çizgiyi çokyüzlüye dokunmaya devam ederken yukarı doğru hareket ettirmektir. Tam sayı sorunun en iyi çözüm noktalarıdır ve her iki gevşeme benzersiz optimumdur 2. objektif değerine sahip olan 2.8 amacı değeri ile. Gevşetmenin çözümü en yakın tamsayılara yuvarlanırsa, ILP için uygun değildir.

NP-sertliğinin kanıtı

Aşağıdakiler, NP-sertliğinin kanıtı olarak hizmet edecek olan minimum tepe örtüsünden tamsayılı programlamaya bir azalmadır .

Let bir yönsüz çizge. Doğrusal bir programı aşağıdaki gibi tanımlayın:

Kısıtlamaların 0 veya 1 ile sınırlandığı göz önüne alındığında , tamsayı programına yönelik herhangi bir uygun çözüm, bir köşe alt kümesidir. İlk kısıtlama, her kenarın en az bir bitiş noktasının bu alt kümeye dahil edildiğini ima eder. Bu nedenle, çözüm bir tepe örtüsünü tanımlar. Ek olarak, bazı köşe kapağı C verildiğinde, herhangi biri için 1'e ve herhangi biri için 0'a ayarlanabilir, böylece bize tamsayı programına uygun bir çözüm sunar. Böylece, toplamını en aza indirirsek, minimum tepe örtüsünü de bulduğumuz sonucuna varabiliriz .

Varyantlar

Karma tamsayılı doğrusal programlama ( MILP ), değişkenlerden yalnızca bazılarının tamsayı olarak sınırlandırıldığı, diğer değişkenlerin tamsayı olmamasına izin verildiği problemleri içerir .

Sıfır-bir doğrusal programlama (veya ikili tamsayı programlama ), değişkenlerin 0 veya 1 olarak sınırlandırıldığı problemleri içerir. Herhangi bir sınırlı tamsayı değişkeni, ikili değişkenlerin bir kombinasyonu olarak ifade edilebilir. Örneğin, bir tamsayı değişkeni verildiğinde , değişken ikili değişkenler kullanılarak ifade edilebilir :

Uygulamalar

Problemleri doğrusal bir program olarak modellerken tamsayı değişkenlerini kullanmanın iki ana nedeni vardır:

  1. Tamsayı değişkenleri, yalnızca tamsayı olabilen miktarları temsil eder. Örneğin, 3.7 araba yapmak mümkün değildir.
  2. Tamsayı değişkenleri kararları temsil eder (örneğin, bir grafiğe bir kenarın dahil edilip edilmeyeceği ) ve bu nedenle yalnızca 0 veya 1 değerini almalıdır.

Bu hususlar pratikte sıklıkla meydana gelir ve bu nedenle tamsayılı doğrusal programlama, bazıları aşağıda kısaca açıklanan birçok uygulama alanında kullanılabilir.

Üretim planlaması

Karma tamsayılı programlama, atölye modellemesi de dahil olmak üzere endüstriyel üretimlerde birçok uygulamaya sahiptir. Tarımsal üretim planlamasında önemli bir örnek , kaynakları paylaşabilen çeşitli mahsuller için üretim veriminin belirlenmesini içerir (örn. Toprak, emek, sermaye, tohum, gübre, vb.). Olası bir amaç, mevcut kaynakları aşmadan toplam üretimi maksimize etmektir. Bazı durumlarda, bu doğrusal bir program olarak ifade edilebilir, ancak değişkenler tamsayı olarak sınırlandırılmalıdır.

zamanlama

Bu problemler, ulaşım ağlarında servis ve araç çizelgelemelerini içermektedir. Örneğin, bir sorun, bir zaman çizelgesinin karşılanabilmesi için otobüslerin veya metroların ayrı güzergahlara atanmasını ve ayrıca bunları sürücülerle donatmayı içerebilir. Burada ikili karar değişkenleri, bir rotaya bir otobüsün veya metronun atanıp atanmadığını ve bir sürücünün belirli bir trene veya metroya atanıp atanmadığını gösterir. Sıfır-bir programlama tekniği, projelerin birbirini dışlayan ve/veya teknolojik olarak birbirine bağımlı olduğu bir proje seçim problemini çözmek için başarıyla uygulanmıştır. Tüm karar değişkenlerinin tamsayı olduğu özel bir tamsayı programlama durumunda kullanılır. Değerleri sıfır veya bir olarak alabilir.

Bölgesel bölümleme

Bölgesel bölümleme veya bölgeleme problemi, farklı kriterler veya kısıtlamalar göz önünde bulundurularak bazı işlemleri planlamak için bir coğrafi bölgeyi ilçelere bölmekten ibarettir. Bu problem için bazı gereklilikler şunlardır: bitişiklik, kompaktlık, denge veya eşitlik, doğal sınırlara saygı ve sosyo-ekonomik homojenlik. Bu tür bir sorun için bazı uygulamalar şunları içerir: siyasi yönetim, okul yönetimi, sağlık hizmetleri yönetimi ve atık yönetimi yönetimi.

Telekomünikasyon ağları

Bu problemlerin amacı, önceden tanımlanmış bir dizi iletişim gereksinimlerinin karşılanması ve ağın toplam maliyetinin minimum olması için kurulacak bir hat ağı tasarlamaktır. Bu, çeşitli hatların kapasitelerinin ayarlanması ile birlikte hem ağın topolojisinin optimize edilmesini gerektirir. Çoğu durumda, kapasiteler tamsayı miktarları olarak sınırlandırılır. Genellikle, kullanılan teknolojiye bağlı olarak, tamsayı veya ikili değişkenlerle doğrusal eşitsizlikler olarak modellenebilen ek kısıtlamalar vardır.

Hücresel ağlar

GSM mobil ağlarında frekans planlamasının görevi, kullanıcılara hizmet verilebilmesi ve antenler arasındaki parazitin en aza indirilmesi için mevcut frekansların antenler arasında dağıtılmasını içerir. Bu problem, ikili değişkenlerin bir antene bir frekansın atanıp atanmadığını gösterdiği bir tamsayılı doğrusal program olarak formüle edilebilir.

Diğer uygulamalar

algoritmalar

Bir ILP'yi çözmenin naif yolu, x'in tamsayı olduğu kısıtlamasını kaldırmak, karşılık gelen LP'yi ( ILP'nin LP gevşemesi olarak adlandırılır) çözmek ve ardından çözümün girişlerini LP gevşemesine yuvarlamaktır. Ancak bu çözüm optimal olmadığı gibi uygulanabilir bile olmayabilir; yani, bazı kısıtlamaları ihlal edebilir.

Toplam unimodülerliği kullanma

Genel olarak LP gevşeme çözüm TDP formu varsa, ayrılmaz olması garanti etmeyecek olsa böyle nereye ve tüm tamsayı girdilerine sahip ve olduğu tamamen unimodular sonra her temel olurlu çözüm ayrılmaz bir parçasıdır. Sonuç olarak, simpleks algoritması tarafından döndürülen çözümün integral olduğu garanti edilir. Her temel uygun çözümün integral olduğunu göstermek için, keyfi bir temel uygun çözüm olsun. Yana uygulanabilir, bunu biliyoruz . Temel çözüm için temel sütunlara karşılık gelen elemanlar olsun . Esas tanımı gereği, bir kare submatrix vardır arasında lineer bağımsız sütun bu şekilde birlikte .

Sütunları lineer olarak bağımsız ve kare olduğundan , tekil olmadığından ve dolayısıyla varsayıma göre tek modüllüdür ve böylece . Ayrıca, tekil olmadığı için tersinirdir ve dolayısıyla . Tanım olarak, . İşte gösterir adjugate ait ve ayrılmaz çünkü ayrılmaz bir parçasıdır. Bu nedenle,

Bu nedenle, bir ILP'nin matrisi , bir ILP algoritması kullanmak yerine tamamen unimodüler ise, LP gevşemesini çözmek için simpleks yöntemi kullanılabilir ve çözüm tamsayı olacaktır.

Kesin algoritmalar

Matris tamamen unimodüler olmadığında, tamsayılı doğrusal programları tam olarak çözmek için kullanılabilecek çeşitli algoritmalar vardır. Algoritmaların bir sınıfı , LP gevşemesini çözerek ve ardından herhangi bir tamsayı uygulanabilir noktayı dışlamadan çözümü tamsayı olmaya yönlendiren lineer kısıtlamalar ekleyerek çalışan kesme düzlemi yöntemleridir .

Algoritmaların başka bir sınıfı, dal ve sınır yönteminin çeşitleridir . Örneğin, dal ve kesme yöntemi birleştiren dal hem de bağlanmış ve kesme düzlemi yöntemleri bu. Dal ve sınır algoritmalarının, yalnızca kesme düzlemlerini kullanan algoritmalara göre bir takım avantajları vardır. Bir avantajı, algoritmaların erken sonlandırılabilmesi ve en az bir integral çözüm bulunduğu sürece, optimal olmasa da uygulanabilir bir çözüme geri dönülebilmesidir. Ayrıca, LP gevşemelerinin çözümleri, döndürülen çözümün optimallikten ne kadar uzak olduğuna dair en kötü durum tahminini sağlamak için kullanılabilir. Son olarak, birden çok optimal çözümü döndürmek için dal ve sınır yöntemleri kullanılabilir.

Az sayıda değişken için kesin algoritmalar

Varsayalım bir olduğunu m -by- n tam sayı matrisi ve bir olduğunu m -by-1 tam sayı vektörü. Biz orada olup olmadığını karar verecek fizibilite sorunu üzerinde odaklanacak n vektörü -by-1 tatmin .

V , ve içindeki katsayıların maksimum mutlak değeri olsun . Eğer n (değişken sayısı) sabit bir sabit ise, fizibilite problemi m ve log V cinsinden zaman polinomunda çözülebilir . Bu, n =1 durumu için önemsizdir . n =2 olayı 1981'de Herbert Scarf tarafından çözüldü . Genel dava 1983'te Hendrik Lenstra tarafından Laszlo Lovasz ve Peter van Emde Boas'ın fikirlerini birleştirerek çözüldü .

0-1 ILP özel durumunda, Lenstra'nın algoritması tam numaralandırmaya eşdeğerdir: olası tüm çözümlerin sayısı sabittir (2 n ) ve her bir çözümün fizibilitesinin kontrolü zamanında yapılabilir poly( m , log V ) . Her değişkenin keyfi bir tamsayı olabileceği genel durumda, tam numaralandırma imkansızdır. Burada, Lenstra'nın algoritması , Sayıların Geometrisinden gelen fikirleri kullanır . Orijinal problemi şu özelliğe sahip eşdeğer bir probleme dönüştürür: ya bir çözümün varlığı açıktır ya da ( n -inci değişken) değeri , uzunluğu n'nin bir fonksiyonu ile sınırlanmış bir aralığa aittir . İkinci durumda, problem sınırlı sayıda daha düşük boyutlu problemlere indirgenir.

Lenstra'nın algoritması, n'nin değiştiği ancak m'nin (kısıtlama sayısı) sabit olduğu ikili durumda da ILP'nin polinom-zamanında çözülebilir olduğunu ima eder .

Lenstra'nın algoritması daha sonra Kannan ve Frank ve Tardos tarafından geliştirildi. Geliştirilmiş çalışma zamanı burada, içinde giriş bit sayısı, bir .

sezgisel yöntemler

Tamsayılı doğrusal programlama NP-zor olduğundan , birçok problem örneği inatçıdır ve bu nedenle bunun yerine buluşsal yöntemler kullanılmalıdır. Örneğin, tabu arama , ILP'lere çözüm aramak için kullanılabilir. ILP'leri çözmek için tabu aramayı kullanmak için, hareketler, diğer tüm tamsayı kısıtlamalı değişkenleri sabit tutarken, uygulanabilir bir çözümün tamsayı kısıtlamalı bir değişkenini artırma veya azaltma olarak tanımlanabilir. Daha sonra kısıtlanmamış değişkenler için çözülür. Kısa süreli bellek daha önce denenmiş çözümlerden oluşabilirken orta süreli bellek, yüksek nesnel değerlerle sonuçlanan tamsayı kısıtlı değişkenlerin değerlerinden oluşabilir (ILP'nin bir maksimizasyon problemi olduğu varsayılırsa). Son olarak, uzun süreli bellek, aramayı daha önce denenmemiş tamsayı değerlerine yönlendirebilir.

ILP'lere uygulanabilecek diğer buluşsal yöntemler şunları içerir:

Ayrıca , gezgin satıcı problemi için k-opt buluşsal yöntemi gibi çeşitli probleme özgü buluşsal yöntemler de vardır. Sezgisel yöntemlerin bir dezavantajı, bir çözüm bulamazlarsa, bunun uygun bir çözüm olmadığından mı yoksa algoritmanın basitçe bir çözüm bulamadığından mı belirlenememesidir. Ayrıca, bu yöntemlerle döndürülen bir çözümün optimale ne kadar yakın olduğunu ölçmek genellikle imkansızdır.

Seyrek Tamsayılı Programlama

Tamsayılı programı tanımlayan matrisin seyrek olması genellikle bir durumdur . Özellikle bu, matrisin bir blok yapısına sahip olması durumunda meydana gelir, bu birçok uygulamada durum böyledir. Matrisin seyrekliği aşağıdaki gibi ölçülebilir. Grafik ait olan kolonlar için karşılık gelen köşe bulunmaktadır , ve, eğer, iki sütun, bir kenar meydana iki sütun sıfır olmayan girişine sahip bir sıra vardır. Eşdeğer olarak, köşeler değişkenlere karşılık gelir ve iki değişken bir eşitsizliği paylaşıyorlarsa bir kenar oluştururlar. Kıtlık ölçü arasında arasındaki minimum ağaç derinlemesine grafiğinin ve ağaç derinlemesine bir devrik grafiğinin . Izin olmak sayısal ölçü arasında herhangi bir giriş maksimum mutlak değer olarak tanımlanır . Tamsayılı programın değişken sayısı olsun . Sonra tamsayı programlama içinde çözülebileceğini 2018 gösterildi kuvvetle polinom ve sabit parametreli uysal zaman parametreli ve . Yani, bazı hesaplanabilir fonksiyonlar ve bazı sabitler için tamsayılı programlama zamanında çözülebilir . Özellikle zaman, sağ taraf ve amaç fonksiyonundan bağımsızdır . Ayrıca, Lenstra'nın değişken sayısının bir parametre olduğu klasik sonucunun aksine, burada değişken sayısı girdinin değişken bir parçasıdır.

Ayrıca bakınız

Referanslar

daha fazla okuma

Dış bağlantılar