Tamsayılı programlama - Integer programming - Wikipedia

Bir Tamsayılı programlama sorun bir matematiksel optimizasyon veya fizibilite değişkenlerin bazılarının veya tamamının sınırlı olduğu program tamsayılar. Birçok ortamda terim, tamsayı doğrusal programlama (ILP), burada amaç fonksiyonu ve kısıtlamalar (tamsayı kısıtlamaları dışında) doğrusal.

Tamsayı programlama NP tamamlandı. Özellikle, bilinmeyenlerin ikili olduğu ve yalnızca kısıtlamaların karşılanması gereken 0-1 tamsayılı doğrusal programlamanın özel durumu aşağıdakilerden biridir: Karp'ın 21 NP-tam problemi.

Bazı karar değişkenleri birbirinden ayrı değilse, sorun olarak bilinir karma tamsayı programlama sorun.^[1]

ILP'ler için kanonik ve standart form

Kanonik formda bir tamsayı doğrusal program şu şekilde ifade edilir:^[2]

{ displaystyle { begin {align} & { text {maximize}} && mathbf {c} ^ { mathrm {T}} mathbf {x} & { text {subject to}} && A mathbf {x} leq mathbf {b}, &&& mathbf {x} geq mathbf {0}, & { text {ve}} && mathbf {x} in mathbb {Z} ^ {n}, end {hizalı}}}

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

{ displaystyle { begin {align} & { text {maximize}} && mathbf {c} ^ { mathrm {T}} mathbf {x} & { text {subject to}} && A mathbf {x} + mathbf {s} = mathbf {b}, &&& mathbf {s} geq mathbf {0}, &&& mathbf {x} geq mathbf {0}, & { text {ve}} && mathbf {x} in mathbb {Z} ^ {n}, end {hizalı}}}

nerede ${ displaystyle mathbf {c}, mathbf {b}}$ vektörler ve ${ displaystyle A}$ tüm girişlerin tam sayı olduğu bir matristir. Doğrusal programlarda olduğu gibi, standart formda olmayan ILP'ler de standart forma dönüştürüldü eşitsizlikleri ortadan kaldırarak, gevşek değişkenler getirerek ( ${ displaystyle mathbf {s}}$ ) ve işaret kısıtlamasına sahip olmayan değişkenleri işaret kısıtlamalı iki değişkenin farkı ile değiştirme

Misal

LP gevşemeli IP politop

Sağdaki grafik aşağıdaki sorunu göstermektedir.

{ displaystyle { başla {hizalı} max & { text {}} y - x + y & leq 1 3x + 2y & leq 12 2x + 3y & leq 12 x, y & geq 0 x, y & in mathbb {Z} end {hizalı}}}

Uygulanabilir tam sayı noktaları kırmızı ile gösterilir ve kırmızı kesik ç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, integralite kısıtlaması olmaksızın eşitsizlikler tarafından verilen LP gevşemesinin polihedronunu tanımlar. Optimizasyonun amacı, siyah noktalı çizgiyi hala çokyüzlüye dokunurken yukarı doğru hareket ettirmektir. Tamsayı probleminin optimal çözümleri noktalardır ${ displaystyle (1,2)}$ ve ${ displaystyle (2, 2)}$ her ikisinin de objektif değeri 2'dir. Gevşemenin benzersiz optimum değeri ${ displaystyle (1,8,2,8)}$ 2.8 objektif değeri ile. Gevşeme çözümü en yakın tam sayılara yuvarlanırsa, ILP için bu mümkün değildir.

NP sertliğinin kanıtı

Aşağıdakiler minimumdan bir indirmedir köşe kapağı NP sertliğinin kanıtı olarak hizmet edecek tamsayı programlamaya.

İzin Vermek ${ displaystyle G = (V, E)}$ yönsüz bir grafik olabilir. Doğrusal bir programı aşağıdaki gibi tanımlayın:

{ displaystyle { begin {align} min sum _ {v in V} y_ {v} y_ {v} + y_ {u} & geq 1 && forall uv in E y_ {v } & geq 0 && forall v in V y_ {v} & in mathbb {Z} && forall v in V end {hizalı}}}

Kısıtlamaların sınırladığı göz önüne alındığında ${ displaystyle y_ {v}}$ 0 veya 1 olarak, tamsayı programına yönelik herhangi bir uygun çözüm, köşelerin bir alt kümesidir. İlk kısıtlama, her kenarın en az bir uç noktasının bu alt kümeye dahil edildiğini belirtir. Bu nedenle, çözüm bir köşe kaplamasını tanımlar. Ek olarak, bazı köşe kapağı C verildiğinde, ${ displaystyle y_ {v}}$ herhangi biri için 1'e ayarlanabilir ${ displaystyle v C}$ ve herhangi biri için 0'a ${ displaystyle v C’de değil}$ bu da bize tamsayı programına uygun bir çözüm sunuyor. Böylece, toplamını en aza indirirsek şu sonuca varabiliriz: ${ displaystyle y_ {v}}$ minimum köşe kapağını da bulduk.^[3]

Varyantlar

Karışık tamsayı doğrusal programlama (MILP) sadece bazı değişkenlerin olduğu problemleri içerir, ${ displaystyle x_ {i}}$ , tamsayı olarak sınırlanırken, diğer değişkenlerin tamsayı olmamasına izin verilir.

Sıfır bir doğrusal programlama (veya ikili tamsayı programlama), değişkenlerin 0 veya 1 ile 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.^[4] Örneğin, bir tamsayı değişkeni verildiğinde, ${ displaystyle 0 leq x leq U}$ değişken kullanılarak ifade edilebilir ${ displaystyle lfloor log _ {2} U rfloor +1}$ ikili değişkenler:

{ displaystyle x = x_ {1} + 2x_ {2} + 4x_ {3} + cdots +2 ^ { lfloor log _ {2} U rfloor} x _ { lfloor log _ {2} U rfloor +1}.}

Başvurular

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

Tam sayı değişkenleri, yalnızca tamsayı olabilen miktarları temsil eder. Örneğin 3,7 araba yapmak mümkün değil.
Tamsayı değişkenleri kararları temsil eder (ör. grafik ) ve bu nedenle yalnızca 0 veya 1 değerini almalıdır.

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

Üretim planlaması

Karışık tamsayı programlamanın endüstriyel üretimlerde iş atölyesi modellemesi dahil birçok uygulaması vardır. Tarımda önemli bir örnek olur üretim planlaması Kaynakları paylaşabilen çeşitli mahsuller için üretim veriminin belirlenmesini içerir (örneğin, Toprak, emek, sermaye, tohumlar, gübre vb.). Olası bir hedef, 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.

Planlama

Bu sorunlar, ulaşım ağlarında servis ve araç planlamasını içerir. Örneğin, bir zaman çizelgesine uyulabilmesi için otobüslerin veya metroların münferit rotalara atanması ve ayrıca sürücülerle donatılması sorunu olabilir. Burada ikili karar değişkenleri, bir rotaya bir otobüs 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ışladığı bir proje seçim problemini çözmek için başarıyla uygulanmıştır ve / veya teknolojik olarak birbirine bağımlı. 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 kabul edebilir.

Bölgesel bölümleme

Bölgesel bölümleme veya bölgelere ayırma sorunu, farklı kriterleri veya kısıtlamaları göz önünde bulundurarak bazı operasyonları planlamak için bir coğrafi bölgeyi bölgelere ayırmayı içerir. Bu problem için bazı gereksinimler şunlardır: yakınlık, kompaktlık, denge veya eşitlik, doğal sınırlara saygı ve sosyo-ekonomik homojenlik. Bu tür problemler için bazı uygulamalar şunları içerir: siyasi bölge belirleme, okul bölgeleri belirleme, sağlık hizmetleri bölgeleri ve atık yönetimi bölgeleri.^[5]

Telekomünikasyon ağları

Bu sorunların amacı, önceden tanımlanmış bir dizi iletişim gereksiniminin karşılanması ve ağın toplam maliyetinin minimum olması için kurulacak bir hat ağı tasarlamaktır.^[6] Bu, çeşitli hatların kapasitelerinin ayarlanmasının yanı sıra ağın hem topolojisinin optimize edilmesini gerektirir. Çoğu durumda, kapasiteler tamsayı miktarlarla sınırlandırılmıştır. Genellikle, kullanılan teknolojiye bağlı olarak, tamsayı veya ikili değişkenlerle doğrusal eşitsizlikler olarak modellenebilecek ek kısıtlamalar vardır.

Hücresel ağlar

Frekans planlamasının görevi GSM mobil ağlar, mevcut frekansların antenler boyunca dağıtılmasını içerir, böylece kullanıcılara hizmet verilebilir ve antenler arasında parazit en aza indirilir.^[7] Bu problem, ikili değişkenlerin bir antene bir frekansın atanıp atanmadığını gösteren tamsayı doğrusal bir program olarak formüle edilebilir.

Diğer uygulamalar

Algoritmalar

Bir ILP'yi çözmenin saf yolu, basitçe şu kısıtlamayı kaldırmaktır: x tam sayıdır, karşılık gelen DP'yi çözün ( LP gevşemesi ILP) ve ardından çözümün girişlerini LP gevşemesine yuvarlayın. Ancak, bu çözüm sadece optimal olmayabilir, hatta uygulanabilir bile olmayabilir; yani, bazı kısıtlamaları ihlal edebilir.

Toplam tek modsuzluğu kullanma

Genel olarak LP gevşemesine yönelik çözümün bütünleyici olduğu garanti edilmezken, ILP bu biçime sahipse ${ displaystyle max mathbf {c} ^ { mathrm {T}} mathbf {x}}$ öyle ki ${ displaystyle A mathbf {x} = mathbf {b}}$ nerede ${ displaystyle A}$ ve ${ displaystyle mathbf {b}}$ tüm tamsayı girişlerine sahip ve ${ displaystyle A}$ dır-dir tamamen modüler olmayan o zaman her temel uygulanabilir çözüm bir bütündür. Sonuç olarak, çözüm tarafından döndürülen simpleks algoritması integral olması garantilidir. Her temel uygulanabilir çözümün ayrılmaz olduğunu göstermek için ${ displaystyle mathbf {x}}$ keyfi bir temel uygulanabilir çözüm olabilir. Dan beri ${ displaystyle mathbf {x}}$ uygulanabilir, bunu biliyoruz ${ displaystyle A mathbf {x} = mathbf {b}}$ . İzin Vermek ${ displaystyle mathbf {x} _ {0} = [x_ {n_ {1}}, x_ {n_ {2}}, cdots, x_ {n_ {j}}]}$ temel çözüm için temel sütunlara karşılık gelen öğeler olmak ${ displaystyle mathbf {x}}$ . Bir temele göre, bazı kare alt matrisler var ${ displaystyle B}$ nın-nin ${ displaystyle A}$ doğrusal olarak bağımsız sütunlarla ${ displaystyle B mathbf {x} _ {0} = mathbf {b}}$ .

Sütunlarından beri ${ displaystyle B}$ doğrusal olarak bağımsızdır ve ${ displaystyle B}$ kare ${ displaystyle B}$ tekil değildir ve bu nedenle varsayım gereği, ${ displaystyle B}$ dır-dir modüler olmayan ve bu yüzden ${ displaystyle det (B) = pm 1}$ . Ayrıca, o zamandan beri ${ displaystyle B}$ tekil değildir, tersinirdir ve bu nedenle ${ displaystyle mathbf {x} _ {0} = B ^ {- 1} mathbf {b}}$ . Tanım olarak, ${ displaystyle B ^ {- 1} = { frac {B ^ {adj}} { det (B)}} = pm B ^ {adj}}$ . Buraya ${ displaystyle B ^ {adj}}$ gösterir tamamlayıcı nın-nin ${ displaystyle B}$ ve ayrılmaz çünkü ${ displaystyle B}$ integraldir. Bu nedenle,

{ displaystyle { begin {align} & Rightarrow B ^ {- 1} = pm B ^ {adj} { text {integraldir.}} & Rightarrow x_ {0} = B ^ {- 1 } b { text {integraldir.}} & Rightarrow { text {Her temel uygulanabilir çözüm integraldir.}} end {hizalı}}}

Böylece, matris ${ displaystyle A}$ ILP'nin bir ILP algoritması kullanmak yerine tamamen tek modlu değildir, simpleks yöntemi LP gevşemesini çözmek için kullanılabilir ve çözüm tamsayı olacaktır.

Kesin algoritmalar

Matris ${ displaystyle A}$ tamamen tek modlu değildir, tamsayı doğrusal programları tam olarak çözmek için kullanılabilecek çeşitli algoritmalar vardır. Bir algoritma sınıfı kesme düzlemi yöntemleri LP gevşemesini çözerek ve ardından çözümü tam sayı olabilecek herhangi bir noktayı hariç tutmadan tam sayı olmaya yönlendiren doğrusal kısıtlamalar ekleyerek çalışır.

Başka bir algoritma sınıfı, dal ve sınır yöntem. Örneğin, dal ve kesim hem dallanma hem de sınır ve kesme düzlemi yöntemlerini birleştiren yöntem. Dal ve sınır algoritmalarının, yalnızca kesme düzlemlerini kullanan algoritmalara göre birçok avantajı vardır. Bir avantaj, algoritmaların erken sonlandırılabilmesi ve en az bir integral çözüm bulunduğu sürece, zorunlu olarak optimal olmasa da, uygulanabilir bir çözümün geri döndürülebilmesidir. Ayrıca, LP gevşemelerinin çözümleri, geri dönen çözümün optimallikten ne kadar uzakta 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 dallanma ve sınır yöntemleri kullanılabilir.

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

Varsayalım ${ displaystyle A}$ bir m-tarafından-n tamsayı matrisi ve ${ displaystyle mathbf {b}}$ bir m-by-1 tamsayı vektörü. Fizibilite sorununa odaklanıyoruz, bu da var olup olmadığına karar vermektir. n-by-1 vektör ${ displaystyle mathbf {x}}$ doyurucu ${ displaystyle A mathbf {x} leq mathbf {b}}$ .

İzin Vermek V katsayıların maksimum mutlak değeri ${ displaystyle A}$ ve ${ displaystyle mathbf {b}}$ . Eğer n (değişken sayısı) sabit bir sabittir, bu durumda fizibilite problemi zaman polinomunda çözülebilir. m ve günlük V. Bu durum için önemsiz n= 1. Dava n= 2 1981'de şu şekilde çözüldü: Herbert Eşarp.^[12] Genel dava 1983 yılında Hendrik Lenstra, fikirleri birleştirerek Laszlo Lovasz ve Peter van Emde Boas.^[13]

0-1 ILP özel durumunda, Lenstra'nın algoritması tam numaralandırmaya eşdeğerdir: olası tüm çözümlerin sayısı sabittir (2ⁿ) ve her bir çözümün fizibilitesini kontrol etmek zaman poli (m, günlük V). Her değişkenin keyfi bir tam sayı olabileceği genel durumda, tam numaralandırma imkansızdır. Burada Lenstra'nın algoritması, Sayıların geometrisi. Orijinal problemi şu özelliğe sahip eşdeğer bir soruna dönüştürür: ya bir çözümün varlığı ${ displaystyle mathbf {x}}$ bariz veya değeri ${ displaystyle x_ {n}}$ ( ndeğişken), uzunluğu bir fonksiyonla sınırlanan bir aralığa aittir. n. İkinci durumda, sorun sınırlı sayıda düşük boyutlu soruna indirgenir.

Lenstra'nın algoritması, ILP'nin, ikili durumda da polinom zamanlı çözülebilir olduğunu ima eder. n değişken ama m (kısıtlamaların sayısı) sabittir.

Lenstra'nın algoritması daha sonra Kannan tarafından geliştirildi^[14] ve Frank ve Tardos.^[15] İyileştirilmiş çalışma zamanı ${ displaystyle n ^ {2.5n} cdot ell}$ , nerede ${ displaystyle ell}$ giriş bitlerinin sayısıdır,^[16] hangisi içinde ${ displaystyle { text {poli}} (m, log {V})}$ .^[17]^:Prop.8\

Sezgisel yöntemler

Tamsayı doğrusal programlama NP-zor, birçok sorun örneği inatçıdır ve bu nedenle bunun yerine sezgisel yöntemler kullanılmalıdır. Örneğin, tabu araması ILP'lere çözüm aramak için kullanılabilir.^[18] ILP'leri çözmek için tabu aramasını 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ıtlı değişkenini artırmak veya azaltmak olarak tanımlanabilir. Kısıtlanmamış değişkenler daha sonra çözülür. Kısa süreli bellek önceden denenmiş çözümlerden oluşabilirken, orta süreli bellek, yüksek objektif değerlerle sonuçlanan tamsayı kısıtlı değişkenler için değerlerden oluşabilir (ILP'nin bir maksimizasyon problemi olduğu varsayılarak). Son olarak, uzun süreli bellek, daha önce denenmemiş tam sayı değerlerine doğru aramayı yönlendirebilir.

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

Ayrıca, soruna özgü çeşitli başka buluşsal yöntemler de vardır. k-opt sezgisel seyyar satıcı sorunu için. Sezgisel yöntemlerin bir dezavantajı, bir çözüm bulamazlarsa, bunun uygulanabilir bir çözüm olmadığından mı yoksa algoritmanın basitçe bir çözüm bulamadığından mı olduğunun belirlenememesidir. Ayrıca, bu yöntemlerle döndürülen bir çözümün optimuma ne kadar yakın olduğunu ölçmek genellikle imkansızdır.

Seyrek Tamsayı Programlama

Genellikle matrisin ${ displaystyle A}$ tamsayı programını tanımlayan seyrek. Bu özellikle, birçok uygulamada olduğu gibi, matris bir blok yapısına sahip olduğunda meydana gelir. Matrisin seyrekliği aşağıdaki gibi ölçülebilir. grafik nın-nin ${ displaystyle A}$ sütunlarına karşılık gelen köşelere sahiptir ${ displaystyle A}$ ve iki sütun bir kenar oluşturur ${ displaystyle A}$ her iki sütunda da sıfır olmayan girişlerin olduğu bir satıra sahiptir. Benzer şekilde, köşeler değişkenlere karşılık gelir ve iki değişken bir eşitsizliği paylaşıyorlarsa bir kenar oluşturur. seyreklik ölçüsü ${ displaystyle d}$ nın-nin ${ displaystyle A}$ arasındaki minimumdur ağaç derinliği grafiğinin ${ displaystyle A}$ ve ağaç derinliği devrik grafiğinin ${ displaystyle A}$ . İzin Vermek ${ displaystyle a}$ ol sayısal ölçü nın-nin ${ displaystyle A}$ herhangi bir girişin maksimum mutlak değeri olarak tanımlanır ${ displaystyle A}$ . İzin Vermek ${ displaystyle n}$ tamsayı programının değişken sayısı olabilir. Sonra 2018'de gösterildi^[19] tamsayı programlama şu şekilde çözülebilir: kuvvetli polinom ve sabit parametreli izlenebilir tarafından parametrelendirilen zaman ${ displaystyle a}$ ve ${ displaystyle d}$ . Yani, bazı hesaplanabilir işlevler için ${ displaystyle f}$ ve biraz daimi ${ displaystyle k}$ tamsayı programlama zaman içinde çözülebilir ${ displaystyle f (a, d) n ^ {k}}$ . Özellikle, zaman sağ taraftan bağımsızdır ${ displaystyle b}$ ve amaç işlevi ${ displaystyle c}$ . Dahası, Lenstra'nın klasik sonucunun aksine, sayı ${ displaystyle n}$ değişken sayısı bir parametredir, burada sayı ${ displaystyle n}$ değişkenler, girdinin değişken bir parçasıdır.

Ayrıca bakınız

Kısıtlanmış en küçük kareler

Referanslar

^ "Karışık Tamsayılı Doğrusal Programlama (MILP): Model Formülasyonu" (PDF). Alındı 16 Nisan 2018.
^ Papadimitriou, C.H.; Steiglitz, K. (1998). Kombinatoryal optimizasyon: algoritmalar ve karmaşıklık. Mineola, NY: Dover. ISBN 0486402584.
^ Erickson, J. (2015). "Tamsayı Programlama Azaltma" (PDF). Arşivlenen orijinal (PDF) 18 Mayıs 2015.
^ Williams, H.P. (2009). Mantık ve tamsayı programlama. Uluslararası Yöneylem Araştırması ve Yönetim Bilimi Serisi. 130. ISBN 978-0-387-92280-5.
^ Franco, D.G.B .; Steiner, M. T. A .; Assef, F.M. (2020). "Brezilya, Paraná Eyaleti'nde atık depolama bölümlemesinde optimizasyon". Temiz Üretim Dergisi. 283. doi:10.1016 / j.jclepro.2020.125353.
^ Borndörfer, R .; Grötschel, M. (2012). "Tamsayı programlamayla telekomünikasyon ağlarının tasarlanması" (PDF).
^ Sharma, Deepak (2010). "Frekans Planlaması".
^ Morais, Hugo; Kádár, Péter; Faria, Pedro; Vale, Zita A .; Khodr, H.M. (2010-01-01). "Karma tamsayı doğrusal programlama kullanılarak izole edilmiş bir yük alanında yenilenebilir bir mikro şebekenin optimum zamanlaması". Yenilenebilir enerji. 35 (1): 151–156. doi:10.1016 / j.renene.2009.02.031. hdl:10400.22/1585. ISSN 0960-1481.
^ Omu, Akomeno; Choudhary, Ruchi; Boies, Adam (2013-10-01). "Karma tam sayı doğrusal programlama kullanarak dağıtılmış enerji kaynağı sistemi optimizasyonu". Enerji politikası. 61: 249–266. doi:10.1016 / j.enpol.2013.05.009. ISSN 0301-4215.
^ Schouwenaars, T .; Valenti, M .; Feron, E .; Nasıl, J. (2005). "MILP Tabanlı İHA Rehberliğinin Uygulama ve Uçuş Test Sonuçları". 2005 IEEE Havacılık Konferansı: 1–13. doi:10.1109 / AERO.2005.1559600. ISBN 0-7803-8870-4. S2CID 13447718.
^ Radmanesh, Mohammadreza; Kumar, Manish (2016/03/01). "Hızlı-dinamik karışık tamsayı doğrusal programlama kullanarak hareketli engellerin varlığında İHA'ların uçuş oluşumu". Havacılık Bilimi ve Teknolojisi. 50: 149–160. doi:10.1016 / j.ast.2015.12.021. ISSN 1270-9638.
^ Eşarp, Herbert E. (1981). "Ayrılmazlık İçeren Üretim Setleri, Bölüm I: Genellikler". Ekonometrik. 49 (1): 1–32. doi:10.2307/1911124. ISSN 0012-9682. JSTOR 1911124.
^ Lenstra, H.W. (1983-11-01). "Sabit Sayıda Değişkenle Tamsayı Programlama". Yöneylem Araştırması Matematiği. 8 (4): 538–548. doi:10.1287 / bağlama.8.4.538. ISSN 0364-765X.
^ Kannan, Ravi (1987-08-01). "Minkowski'nin Dışbükey Gövde Teoremi ve Tam Sayı Programlama". Yöneylem Araştırması Matematiği. 12 (3): 415–440. doi:10.1287 / demir.12.3.415. ISSN 0364-765X.
^ Frank, András; Tardos, Éva (1987-03-01). "Kombinasyonel optimizasyonda eşzamanlı diyofant yaklaşımının bir uygulaması". Kombinatorik. 7 (1): 49–65. doi:10.1007 / BF02579200. ISSN 1439-6912. S2CID 45585308.
^ Bliem, Bernhard; Bredereck, Robert; Niedermeier, Rolf (2016-07-09). "Verimli ve kıskanç kaynak tahsisinin karmaşıklığı: az sayıda aracı, kaynak veya yardımcı program düzeyi". Yirmi Beşinci Uluslararası Yapay Zeka Ortak Konferansı Bildirileri. IJCAI'16. New York, New York, ABD: AAAI Press: 102–108. ISBN 978-1-57735-770-4.
^ Bredereck, Robert; Kaczmarczyk, Andrzej; Knop, Dušan; Niedermeier, Rolf (2019-06-17). "Yüksek Çokluklu Adil Tahsis: Lenstra, N-kat Tamsayılı Programlama ile Güçlendirildi". 2019 ACM Ekonomi ve Hesaplama Konferansı Bildirileri. EC '19. Phoenix, AZ, ABD: Bilgisayar Makineleri Derneği: 505–523. doi:10.1145/3328526.3329649. ISBN 978-1-4503-6792-9. S2CID 195298520.
^ Glover, F. (1989). "Tabu arama-Bölüm II". ORSA Hesaplama Dergisi. 1 (3): 4–32. doi:10.1287 / ijoc.2.1.4. S2CID 207225435.
^ Koutecký, Martin; Levin, Asaf; Onn, Shmuel (2018). "Blok Yapılandırılmış Tamsayı Programları için Parametrelenmiş Güçlü Polinom Algoritması". Michael Wagner: 14 sayfa. arXiv:1802.05859. doi:10.4230 / LIPICS.ICALP.2018.85. S2CID 3336201. Alıntı dergisi gerektirir | günlük = (Yardım)

daha fazla okuma

George L. Nemhauser; Laurence A. Wolsey (1988). Tamsayı ve kombinatoryal optimizasyon. Wiley. ISBN 978-0-471-82819-8.
Alexander Schrijver (1998). Doğrusal ve tamsayı programlama teorisi. John Wiley and Sons. ISBN 978-0-471-98232-6.
Laurence A. Wolsey (1998). Tamsayılı programlama. Wiley. ISBN 978-0-471-28366-9.
Dimitris Bertsimas; Robert Weismantel (2005). Tam sayılar üzerinde optimizasyon. Dinamik Fikirler. ISBN 978-0-9759146-2-5.
John K. Karlof (2006). Tamsayı programlama: teori ve pratik. CRC Basın. ISBN 978-0-8493-1914-3.
H. Paul Williams (2009). Mantık ve Tamsayı Programlama. Springer. ISBN 978-0-387-92279-9.
Michael Jünger; Thomas M. Liebling; Denis Naddef; George Nemhauser; William R. Pulleyblank; Gerhard Reinelt; Giovanni Rinaldi; Laurence A. Wolsey, eds. (2009). 50 Yıllık Tamsayı Programlama 1958-2008: İlk Yıllardan Sanatın Son Durumuna. Springer. ISBN 978-3-540-68274-5.
Der-San Chen; Robert G. Batson; Yu Dang (2010). Uygulamalı Tamsayı Programlama: Modelleme ve Çözüm. John Wiley and Sons. ISBN 978-0-470-37306-4.
Gerard Sierksma; Yori Zwols (2015). Doğrusal ve Tamsayı Optimizasyonu: Teori ve Uygulama. CRC Basın. ISBN 978-1-498-71016-9.

Dış bağlantılar

[1] "Karışık Tamsayılı Doğrusal Programlama (MILP): Model Formülasyonu" (PDF). Alındı 16 Nisan 2018.

[optBook-2] Papadimitriou, C.H.; Steiglitz, K. (1998). Kombinatoryal optimizasyon: algoritmalar ve karmaşıklık. Mineola, NY: Dover. ISBN 0486402584.

[3] Erickson, J. (2015). "Tamsayı Programlama Azaltma" (PDF). Arşivlenen orijinal (PDF) 18 Mayıs 2015.

[4] Williams, H.P. (2009). Mantık ve tamsayı programlama. Uluslararası Yöneylem Araştırması ve Yönetim Bilimi Serisi. 130. ISBN 978-0-387-92280-5.

[5] Franco, D.G.B .; Steiner, M. T. A .; Assef, F.M. (2020). "Brezilya, Paraná Eyaleti'nde atık depolama bölümlemesinde optimizasyon". Temiz Üretim Dergisi. 283. doi:10.1016 / j.jclepro.2020.125353.

[6] Borndörfer, R .; Grötschel, M. (2012). "Tamsayı programlamayla telekomünikasyon ağlarının tasarlanması" (PDF).

[7] Sharma, Deepak (2010). "Frekans Planlaması".

[8] Morais, Hugo; Kádár, Péter; Faria, Pedro; Vale, Zita A .; Khodr, H.M. (2010-01-01). "Karma tamsayı doğrusal programlama kullanılarak izole edilmiş bir yük alanında yenilenebilir bir mikro şebekenin optimum zamanlaması". Yenilenebilir enerji. 35 (1): 151–156. doi:10.1016 / j.renene.2009.02.031. hdl:10400.22/1585. ISSN 0960-1481.

[9] Omu, Akomeno; Choudhary, Ruchi; Boies, Adam (2013-10-01). "Karma tam sayı doğrusal programlama kullanarak dağıtılmış enerji kaynağı sistemi optimizasyonu". Enerji politikası. 61: 249–266. doi:10.1016 / j.enpol.2013.05.009. ISSN 0301-4215.

[10] Schouwenaars, T .; Valenti, M .; Feron, E .; Nasıl, J. (2005). "MILP Tabanlı İHA Rehberliğinin Uygulama ve Uçuş Test Sonuçları". 2005 IEEE Havacılık Konferansı: 1–13. doi:10.1109 / AERO.2005.1559600. ISBN 0-7803-8870-4. S2CID 13447718.

[11] Radmanesh, Mohammadreza; Kumar, Manish (2016/03/01). "Hızlı-dinamik karışık tamsayı doğrusal programlama kullanarak hareketli engellerin varlığında İHA'ların uçuş oluşumu". Havacılık Bilimi ve Teknolojisi. 50: 149–160. doi:10.1016 / j.ast.2015.12.021. ISSN 1270-9638.

[12] Eşarp, Herbert E. (1981). "Ayrılmazlık İçeren Üretim Setleri, Bölüm I: Genellikler". Ekonometrik. 49 (1): 1–32. doi:10.2307/1911124. ISSN 0012-9682. JSTOR 1911124.

[13] Lenstra, H.W. (1983-11-01). "Sabit Sayıda Değişkenle Tamsayı Programlama". Yöneylem Araştırması Matematiği. 8 (4): 538–548. doi:10.1287 / bağlama.8.4.538. ISSN 0364-765X.

[14] Kannan, Ravi (1987-08-01). "Minkowski'nin Dışbükey Gövde Teoremi ve Tam Sayı Programlama". Yöneylem Araştırması Matematiği. 12 (3): 415–440. doi:10.1287 / demir.12.3.415. ISSN 0364-765X.

[15] Frank, András; Tardos, Éva (1987-03-01). "Kombinasyonel optimizasyonda eşzamanlı diyofant yaklaşımının bir uygulaması". Kombinatorik. 7 (1): 49–65. doi:10.1007 / BF02579200. ISSN 1439-6912. S2CID 45585308.

[16] Bliem, Bernhard; Bredereck, Robert; Niedermeier, Rolf (2016-07-09). "Verimli ve kıskanç kaynak tahsisinin karmaşıklığı: az sayıda aracı, kaynak veya yardımcı program düzeyi". Yirmi Beşinci Uluslararası Yapay Zeka Ortak Konferansı Bildirileri. IJCAI'16. New York, New York, ABD: AAAI Press: 102–108. ISBN 978-1-57735-770-4.

[17] Bredereck, Robert; Kaczmarczyk, Andrzej; Knop, Dušan; Niedermeier, Rolf (2019-06-17). "Yüksek Çokluklu Adil Tahsis: Lenstra, N-kat Tamsayılı Programlama ile Güçlendirildi". 2019 ACM Ekonomi ve Hesaplama Konferansı Bildirileri. EC '19. Phoenix, AZ, ABD: Bilgisayar Makineleri Derneği: 505–523. doi:10.1145/3328526.3329649. ISBN 978-1-4503-6792-9. S2CID 195298520.

[18] Glover, F. (1989). "Tabu arama-Bölüm II". ORSA Hesaplama Dergisi. 1 (3): 4–32. doi:10.1287 / ijoc.2.1.4. S2CID 207225435.

[19] Koutecký, Martin; Levin, Asaf; Onn, Shmuel (2018). "Blok Yapılandırılmış Tamsayı Programları için Parametrelenmiş Güçlü Polinom Algoritması". Michael Wagner: 14 sayfa. arXiv:1802.05859. doi:10.4230 / LIPICS.ICALP.2018.85. S2CID 3336201. Alıntı dergisi gerektirir | günlük = (Yardım)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]