David Pisinger optimalizácia kódov

Link: http://hjemmesider.diku.dk/~pisinger/codes.html

Táto stránka obsahuje niekoľko optimalizácia kódov napísaný v C. kódy môžu byť použité zdarma pre akademický účely. Každý algoritmus je stručne opísaná a odkaz je uvedené na papier, kde to bolo prezentované.

Batohu Problémy

Generovanie testovacích prípadov

generator postaviť testovacie prípady pre 0-1 Batohu Problém, ako je opísané v knihe “Core problémy v Batohu Algoritmov”. Inštancie sú generované s rôznej kapacity na test kódov, v ponuke viac reálnych podmienkach.

Viac rozšírené generator pre 0-1 Batohu Problémy, je popísaný v “Dynamické programovanie a tesné hranice pre 0-1 Batohu Problém” (co-autori: S. veži martello, P. Tóth), kde je 14 rôznych stupňa druhy sú považované za.

Generátor pre ťažké prípady je tiež k dispozícii. V prípadoch sú opísané v časti “Kde sú ťažké batohu problémy”, ktorý sa objavil v Počítačoch a operačný Výskum (2005). Môžete si tiež stiahnuť všetky inštancie (a ich riešenia) tu: malé koeficienty, veľké koeficienty, ťažké prípady.

Expknap algoritmus

expknap algoritmu bola prezentovaná v knihe “rozširujúceho core algoritmus pre 0-1 batohu problém”. Algoritmus je založený na branch-and-bound, kde jednoduché LP-hranica sa používajú na ohraničenie procesu. Jeho hlavná vlastnosť je, že veľkosť core prispôsobí tvrdosť stupňa. Kód je veľmi krátka, a môže byť použitý pre vyučovacie účely.

Minknap algoritmus

minknap algoritmu bola prezentovaná v knihe “minimálne algoritmus pre 0-1 batohu problém”. Kód je založené na dynamické programovanie, kde enumerative hranice sú použité pochopiť unpromising štátov. Je dokázané, že algoritmus obsahuje najmenšie možné core uspokojovaní niektorých danej vlastnosti.

Combo algoritmus

combo algoritmus je popísaný v “Dynamické Programovanie a Silné Puto pre 0-1 Batohu Problém” S. veži martello, D. Pisinger, P. Tóth. Algoritmus spája generácie platné nerovnosti z MTH algoritmus s dynamické programovanie rekurzie z minknap. Platné nerovnosti sú náhradný uvoľnený na pôvodný problém, tak získať nový (jednoduchšie) batohu problém. Počiatočné jadro je zhotovený podľa niektorých chamtivých pravidlá, ktoré zabezpečujú veľmi stabilné správanie.

Zodpovedajúce hlavička súboru by mali byť použité na definovanie vhodných dátových štruktúr.

Mcknap algoritmus

V “minimálne algoritmus pre viaceré možnosti batohu problém”, presný algoritmus pre viaceré možnosti batohu problém je prezentované. mcknap algoritmus je prvý algoritmus, ktorý používa idea “core” riešiť viaceré možnosti batohu problém. Po prvé, medián vyhľadávací algoritmus sa používa na riešenie LP-uvoľnene poblem. Horné a dolné hranice sú odvodené z LP-uvoľnene riešenie, a ak sa tieto nemusia zhodovať, dynamické programovanie sa používa na enumeráciu rozširujúceho core.

Bouknap algoritmus

Algoritmus na Ohraničenej Batohu Problémov bola prezentovaná v knihe “minimálne algoritmus na ohraničenej batohu problém”. bouknap algoritmus je založený na postupnej premene ohraničenej problém na 0-1 problém ako súčasť rozširujúceho core. Nová horná hranica sú uvedené, na základe ktorých bude možné utiahnuť hranice na každý typ položky.

Mulknap algoritmus

mulknap algoritmus pre riešenie viacerých batohu problémov bola prezentovaná v knihe “presný algoritmus pre veľké viacerých batohu problémy”. Kód je schopný riešiť aj veľmi veľké prípady, v primeranom čase. Algoritmus je založený na rovnakom rámci ako MTM algoritmus podľa veži martello a Tóth (1990), ale obsahuje aj niekoľko nových prvkov: Dolné hranice sú určené rozdelenie náhradné riešenie. Kapacitné obmedzenia sú dotiahnuté pri riešení podmnožinu-súčet problém, ktorý určuje najväčšiu hmotnosť sumy, ktorú možno dosiahnuť bez prekročenia kapacity. A napokon zníženie algoritmus pre fixáciu premenných je realizovaný. testovací program, generovanie prípadoch ako vo veži martello a Tóth (1990) je tiež k dispozícii s príslušnými hlavička súboru.

Decomp algoritmus

decomp algoritmus rieši Podmnožinu-súčet Problém prostredníctvom druh Horowitz-Sahni decompoition. To bolo pôvodne prezentované ako súčasť vyššie algoritmus pre viaceré batohu problémy, ak bolo použité na utiahnite kapacitné obmedzenia a na získanie dolnej hranice rozdelením riešenie náhradného uvoľnene problém. Kód je však veľmi efektívne riešenia väčšina z reálneho života Podmnožinu-súčet Problémy, tak vstavaným postup je uvedený tu.

Scknap algoritmus

Silne korelované batohu problémy boli považované za niektoré z najťažších batohu problémy, v dôsledku veľkých rozdielov medzi LP-riešenie a IP-riešenie. Algoritmus scknapvšak dokázali, že tesný hranice môžu byť získané náhradný relaxačné mohutnosť obmedzenia s pôvodnou kapacitou obmedzenia. Aby zápas horná hranica, rýchle dva-optimálne heuristickej bola postavená, ktoré v mnohých prípadoch vyriešiť problém na optimality. Ak optimality z heuristickej riešenie nemohlo byť dokázané, dynamické programovanie založený na vyváženom štátov bol použitý. Viac podrobností možno nájsť v knihe “rýchly algoritmus pre silne korelované batohu problém”.

Kvadratická Batohu Problémy

Na quadratick batohu problémy spýta, či chcete maximalizovať a kvadratická cieľ funkcia predmetom jedného kapacita obmedzenia. Papier “Presné Riešenie Kvadratických Batohu Problém” Caprara, Pisinger a Tóth (1999) uvádza presný algoritmus pre tieto problémy, ktoré je schopný riešiť husté problémy s až 400 binárnych premenných.

quadknap algoritmus je disponibilná rutina pre riešenie kvadratických batohu problémy. Ako argument to trvá zisk matice, hmotnosť vektor, kapacita batohu, a nakoniec boolean riešenie vektor, kde riešenie, ktoré by mali byť vrátené.

testqkp algoritmus generuje prípadoch, ako sú popísané vo vyššie uvedených papier a vyzýva quadknap kód. Priemerné riešenie krát a nájsť riešenia sú hlásené.

Robot packable troch-dimenzionální Bin-packing Problémy

presný algoritmus pre robota packable troch-dimenzionální Bin-packing Problému

Papier “algoritmus na troch-dimenzionální bin packing problém” S. veži martello, D. Pisinger, D. Vigo (1998), predstavuje kód pre riešenie robot packable troch-dimenzionální bin packing problémy optimality. Kód 3dbpp.c je disponibilná C-postup, ktorý môže byť použitý ako heuristickej alebo presný algoritmus.

Test inštancií pre Troch-dimenzionální Bin-packing Problému

C-kód, ktorý generuje testovacích prípadov pre 3D BPP, ako je popísané v knihe: S. veži martello, D. Pisinger, D. Vigo “troch-dimenzionální bin-packing problém” je nájsť v test3dbpp.c. Algoritmus generuje testovacích prípadov a hovory 3dbpp riešiť problémy, optimality. Výstup zapíše do súboru pre neskoršie spracovanie.

Pokyny pre zostavovanie

readme súbor s pokynmi pre zostavenie troch-dimenzionální bin-packing algoritmus je k dispozícii tu.

Všeobecné troch-dimenzionální Bin-packing Problémy

presný algoritmus pre Troch-dimenzionální Bin-packing Problému

Všeobecné verzia problém je považovaný za “Algoritmy pre Všeobecné a Robot-packable Variantov Troch-Dimenzionální Bin Packing Problém” veži martello, Pisinger, Vigo, den Boef, Korst.

Kód 3dbpp.c.
Test generátor test3dbpp.c.
Pokyny pre zostavovanie readme.

Kontajner Nakladanie ProblemsA heuristiky pre Kontajner Nakladanie Problému

Papier “strom-vyhľadávanie heuristiky pre Kontajner Nakladanie Problém”, D. Pisinger (1999), predstavuje kód pre batohu nakládka kontajnera. Kód kontajnera.c je disponibilná C-postup, ktorý môže byť použitý v niekoľkých aplikáciách.

Test inštancie pre Kontajner Nakladanie Problému

C-kód, ktorý generuje testovacích prípadov pre Kontajner Nakladanie Problém, ako je popísané v: D. Pisinger, “strom-vyhľadávanie heuristiky pre Kontajner Nakladanie Problém” je nájsť v testcont.c. Algoritmus generuje testovacích prípadov a hovory “contload” vyriešiť problémy na optimality. Výstup zapíše do súboru pre neskoršie spracovanie.

Pokyny pre zostavovanie

readme súbor s pokynmi pre zostavenie Kontajner algoritmus nakladania je k dispozícii tu.

Heuristickej prístupy pre dvoch – a troch-dimenzionální batohu balenie problému

Papier “Heuristickej prístupy pre dvoch – a troch-dimenzionální batohu balenie problém” (Jens Egeblad, David Pisinger, Počítače a operačného Výskumu, 2009, vol 36, 1026-1049) predstavuje súbor systematicky generované balenie prípadoch. Všetky prípadoch môže byť stiahnutý z nasledujúcich zip-súbor zip.

(Test inštancie pre zodpovedajúce technickej správe sa nachádzajú v nasledujúcich zip-súbor zip).

Vlak miestenka problému

Off-line skupiny miestenka problém, ktorý považuje v Clausen et al. (2010), možno považovať za balenie problém, kde obdĺžnikov sú stanovené v jednej z dimenzií. Test prípadoch považovaná za vyššie papier môžete nájsť v nasledujúcich zip-súbor zip.