Back to site
Since 2004, our University project has become the Internet's most widespread web hosting directory. Here we like to talk a lot about web development, networking and server security. It is, after all, our expertise. To make things better we've launched this science section with the free access to educational resources and important scientific material translated to different languages.

David Pisinger-ovi optimizacioni kodovi

Ova strana sadrži nekoliko optimizacionih kodova, napisanih u C-u. Kodovi se mogu besplatno koristiti u akademske namene. Svaki algoritam je ukratko opisan i njegove reference su date, u dokumentu u kome je predstavljen.

__________________________________________________________________________________________________________________________

Problemi ranca(knapsack-a)

Generacija test instanci

Generator konstruiše test instance, za 0-1 problem ranca, onako, kako je to opisano u dokumentu "Suštinski problemi ranac algoritama". Instance su generisane sa različitim kapacitetom za testiranje kodova, u realističnijim uslovima.

Napredniji generator, za 0-1 problem ranca, je opisan u "Dinamično programiranje i tesni okviri za 0-1 problem ranca" (ko-autora: S. Martello, P. Toth) gde je uzeto u obzir, 14 različitih tipova instanci.

Expknap algoritam

Expknap algoritam je predstavljen u dokumentu "prošireno jezgro algoritma za 0-1 problem ranca ". Algoritam je baziran na grananju i vezama, gde se jednostavne LP-veze koriste za proces vezivanja. Njegova glavna osobina je da se veličina jezgra prilagođuje zahtevnosti instance. Kod je veoma kratak može se koristiti za učenje.

Minknap algoritam

Minknap algoritam je predstavljen u dokumentu "minimalni algoritam za 0-1 problem ranca". Kod se zasniva na dinamičkom programiranju, gde se nabrajaju veze koje se koriste za dokučivanje stanja koja ne obećavaju. Omogućeno je da algoritam odredi najmanje moguće jezgro, koje zadovoljava neko zadato svojstvo.

Combo algoritam

Combo algoritam je opisan u "Dinamičko programiranje i snažne veze za 0-1 problem ranca ", od strane S.Martello-a, D.Pisinger-a, P.Toth-a. Algoritam kombinuje generisanje važećih nejednakosti iz MTH algoritma, sa rekurzijom dinamičkog programiranja, iz minknap-a. Važeće nejednakosti su surogat relaksacije originalnog problema, pa se tako dobija, novi (lakši) problem ranca. Inicijalno jezgro je konstruisano prema nekim pohlepnim pravilima, što osigurava veoma stabilno ponašanje.

Trebalo bi koristiti odgovarajuće zaglavlje datoteke , za definisanje prikladnih struktura podataka.

Mcknap algoritam

U "Minimalni algoritam za problem ranca sa višestrukim izborom ", predstavljen je tačan algoritam za problem ranca sa višestrukim izborom. Mcknap algoritam je prvi koji koristi ideju "jezgra" za rešavanje problema ranca sa višestrukim izborom. Na početku, medijana algoritam za pretragu je korišćen za rešavanje LP-relaksiranog problema. Gonje i donje veze su izvedene iz rešenja LP-relaksacije, i ako se one ne podudaraju, koristi se dinamčko programiranje za određivanje proširivanja jezgra.

Bouknap algoritam

Algoritam za probleme vezanog ranca (Bounded Knapsack Problems) je predstavljen u dokumentu "minimalni algoritam za probleme vezanog ranca". Bouknap algoritam se zasniva na postepenoj transformaciji vezanog problema, u 0-1 problem, kao dela širenja jezgra. Nove gornje veze su predstavljene, što čini mogućim učvršćivanje veza sa svakim tipom predmeta.

Mulknap algoritam

Mulknap algoritam, za rešavanje većeg broja problema ranca, predstavljen je u dokumentu "Konkretan algoritam za krupne multi- probleme ranca ". Kod je čak sposoban da reši i veoma velike instance, za razumno vreme. Algoritam je zasnovan na istom okviru, kao i MTM algoritam, napisan od strane Martello-a i Toth-a (1990-e), ali sadrži nekoliko novih elemenata: Niže veze su determinisane podelom surogat rešenja. Ograničenja kapaciteta su učvršćena, rešavanjem problema podset-sume, koji određuje veći deo sadržane sume, bez prekoračenja kapaciteta. i konačno, uveden je redukcioni algoritam, za fiksiranje promenljivih. Test program, generisane instance, kao i kod Martello-a i Toth-a (1990-e) je takođe dostupan, uz odgovarajuće poglavlje datoteke .

Decomp algoritam

Decomp algoritam rešava problem podset-sume putem jedne vrste Horowitz-Sahni dekomponovanja. Prvo je predstavljen, kao deo prethodnog algoritma, za rešavanje multi- problema ranca, gde je korišćen za učvršćivanje ograničenja kapaciteta i izvođenje nižih veza, podelom rešenja surogata relaksacije problema. Kod je, međutim, ekstremno efikasan za rešavanje najčešćih podset-suma problema, iz realnog života, pa tako i samo-sadržane procedure, koja je ovde data.

Scknap algoritam

Snažno povezani (Strongly correlated knapsack) problemi ranca, smatraju se najtežim problemima ranca, imajući u vidu ogroman jaz između LP-rešenja i IP-rešenja. Algoritam scknap , međutim, demonstrira da čvrste veze mogu biti sadržane u surogatima, relaksirajući kardinalnost veza, originalnim kapacitetom veza. U cilju usklađivanja sa gornjim vezama, izgrađen je brz dvo-optimalan, istraživački, čto u mnogim slučajevima rešava problem, do optimalnosti. Ukoliko se optimalnost istraživačkog rešenja ne može dokazati, koristi se dinamičko programiranje, bazirano na izbalansiranim stanjima. Više detalja se može naći u dokumentu "Brz algoritam za snažno povezan problem ranca".

__________________________________________________________________________________________________________________________

Kvadratni problemi ranca

Kvadratni problemi ranca traže da se poveća do maksimuma objektivna kvadratna funkcija, koja je usmerena na jedno ograničenje kapaciteta. Dokument "konkretno rešenje kvadratnog problema ranca ", od strane Caprara-e, Pisinger-a i Toth-a (1999-e), predstavlja tačan algoritam ovih problema, koji je sposoban da reši zbijene probleme, uz pomoć skoro 400 binarnih promenljivih.

Guadknap algoritam je opoziva rutina za rešavanje kvadratnih problema ranca. Kao argument uzima matricu profita, značaj vektora(pravca), kapacitet ranca, i na kraju, boolean pravac rešenja, gde bi rešenje trebalo biti vraćeno.

Testqkp algoritam generiše instance, onakvim kakvim su opisane, u prethodno pomenutom dokumentu, i poziva quadknap kod. Prijavljuju se prosečna vremena rešavanja problema i pronađena rešenja.

__________________________________________________________________________________________________________________________

Problemi trodimenzionalnih Bin-paketa, prilagođenih za pakovanje od strane robota

Tačan algoritam za problem trodimenzionalnog paketa, prilagođenog za pakovanje od strane robota

Dokument "Algoritam za problem trodimenzionalnog Bin-pakovanja", od strane S.Martello-a, D.Pisinger-a, D.Vigo-a (iz 1998-e), predstavlja kod za rešavanje do optimuma, problema trodimenzionalnog Bin.paketa, prilagođenog za pakovanje od strane robota. Kod 3dbpp.c je opoziva C-procedura, koja se može koristiti kao istraživački, ili konkretan algoritam.

Test instance za problem trodimenzionalnog Bin-pakovanja

C-kod generiše test instance, za 3D BPP, onako kako je to opisano u dokumentu: S.Martello-a, D.Pisinger-a, D.Vigo-a "Problem trodimenzionalnog Bin-pakovanja" je sadržan u test3dbpp.c. Algoritam generiše instance i poziva 3dbpp, da reši probleme, do optimalnosti. Izlaz je napisan u fajlu, radi kasnijeg procesuiranja.

Instrukcije za kompilovanje

Pročitaj me fajl, sa instrukcijama za kompilovanje trodimenzionalnog Bin-pakovanje algoritma, je dostupan ovde.

__________________________________________________________________________________________________________________________

Tačan algoritam za problem trodimenzionalnog Bin-pakovanja

Opšta verzija problema je razmatrana u "Algoritmi za opšte, i prilagođene za pakovanje od strane robota, varijante problema trodimenzionalnih Bin-pakovanja", napisanom od strane Martello-a, Pisinger-a, Vigo-a, den Boef-a, Korst-a.

Kod 3dbpp.c .
Probni generator test3dbpp.c.
Instrukcije za kompilovanje pročitaj me .

__________________________________________________________________________________________________________________________

Problemi učitavanja sadržaja

Istraživanje u vezi problema učitavanja sadržaja

Dokument "Tree-pretraživačko istraživanje u vezi sa problemom učitavanja sadržaja ", napisan od strane D.Pisinger-a (1999-e), predstavlja kod za ranac učitavanje sadržaja. Kod container.c je opoziva C-procedura, koja se može upotrebiti za nekoliko aplikacija.

Test instance za problem učitavanja sadržaja

C-kod koji generiše test instance za problem učitavanja sadržaja, onako kako je to opisano u: D.Pisinger-ovom "Tree-pretraživačko istraživanje u vezi sa problemom učitavanja sadržaja", se nalazi u testcont.c . Algoritam generiše test instance i poziva "contload" radi rešavanja problema, do optimuma. Izlaz je napisan u fajlu, radi kasnijeg procesuiranja.

Instrukcije za kompilovanje

Pročitaj me fajl, sa instrukcijama za kompilovanje algoritma, je dostupan ovde.

__________________________________________________________________________________________________________________________

Istraživački pristupi za rešavanje ranac problema, dvo- i tro-dimenzionalnih pakovanja

Dokument "Istraživački pristupi za rešavanje ranac problema, dvo- i tro-dimenzionalih pakovanja" (Jens Egeblad, David Pisinger, računarsko i operativno istraživanje, 2009-a, vol 36, 1026-1049), predstavlja seriju, sistematski generisanih instance pakovanja. Sve instance se mogu preuzeti sa zip fajla, u produžetku, zip.

(Test instance za odgovarajući tehnički izveštaj, nalaze se u zip fajlu, u produžetku, zip).

__________________________________________________________________________________________________________________________

Problem rezervacije sedišta u vozu

Neformalna grupa problema, rezervacije sedišta u vozu, sadržana u Clausen et al. (2010.), može se sagledati, kao problem pakovanja kod koga su pravougaonici fiksirani u jednoj od dimenzija. Test instance, razmatrane u prethodnom dokumentu, mogu se naći u zip fajlu, u produžetku, zip.





Published (Last edited): 03-03-2013 , source: http://www.diku.dk/~pisinger/codes.html