OptMod-2017/Gyakorlat9
(egy szerkesztő 2 közbeeső változata nincs mutatva) | |||
16. sor: | 16. sor: | ||
Egyébként vegyük hozzá a kör csúcshalmazához tartozó feltételt a feladathoz | Egyébként vegyük hozzá a kör csúcshalmazához tartozó feltételt a feladathoz | ||
Jó esetben a feltételek száma jóval 2^n alatt marad, illetve a megoldó megfelelő beállításával a jelenlegi feladatot elindíthatjuk az előző feladat optimális megoldásából, így a részfeladatok megoldása sem tart olyan sokáig, mintha a nulláról oldanánk meg újra a feladatot. | Jó esetben a feltételek száma jóval 2^n alatt marad, illetve a megoldó megfelelő beállításával a jelenlegi feladatot elindíthatjuk az előző feladat optimális megoldásából, így a részfeladatok megoldása sem tart olyan sokáig, mintha a nulláról oldanánk meg újra a feladatot. | ||
− | AMPL-ben ezt a run fájlban lehet implementálni. Nézzük meg a [ tsp.mod], és tsp.run fájlokat, majd próbáljuk ki a tsp.dat, tspusa15/ | + | AMPL-ben ezt a run fájlban lehet implementálni. Nézzük meg a [http://math.bme.hu/~kkovacs/optmod/tsp.mod tsp.mod], és [http://math.bme.hu/~kkovacs/optmod/tsp.run tsp.run] fájlokat, majd próbáljuk ki a [http://math.bme.hu/~kkovacs/optmod/tsp.dat tsp.dat], [http://math.bme.hu/~kkovacs/optmod/tspusa15.dat tspusa15.dat], [http://math.bme.hu/~kkovacs/optmod/tspusa20.dat tspusa20.dat] bemenetekkel. ([http://math.bme.hu/~kkovacs/optmod/tsp.zip Egy zip-ben]) |
=== Egészértékű LP felírás === | === Egészértékű LP felírás === | ||
A feladat még egy pár egészértékű változó segítségével felírható polinomiális méretű feladatként is. Olvassuk el a [https://en.wikipedia.org/wiki/Travelling_salesman_problem#Integer_linear_programming_formulation Wikipédia leírást], és gondoljuk végig, hogy miért működik. Ezután programozzuk le ezt a modellt, és próbáljuk ki a fenti bemeneteken. | A feladat még egy pár egészértékű változó segítségével felírható polinomiális méretű feladatként is. Olvassuk el a [https://en.wikipedia.org/wiki/Travelling_salesman_problem#Integer_linear_programming_formulation Wikipédia leírást], és gondoljuk végig, hogy miért működik. Ezután programozzuk le ezt a modellt, és próbáljuk ki a fenti bemeneteken. |
A lap jelenlegi, 2017. november 7., 12:13-kori változata
Utazóügynök probléma (Travelling Salesman Problem - TSP)
A TSP feladatnál adva van n város, illetve a városok közti utazási költség. Feladatunk az első városból indulva mindegyik várost pontosan egyszer bejárva visszatérni az első városba, és ezt a lehető legolcsóbban tenni. Matematikailag precízebben az n csúcsú teljes gráfon keresünk minimális költségű Hamilton-kört.
Feltétel generálós megoldás
Az első megközelítésünk a modellezésre az lehet, hogy felveszünk X[i,j] bináris változókat, melyek az 1 értéket veszik fel, ha i után j következik, és 0-t egyébként. Ekkor értelemszerűen egy város után pontosan egy város következik, és minden város pontosan egy másik város után jön. Tehát a sor- és oszlopösszegek 1-gyel egyenlőek (X permutációs mátrix). A probléma az, hogy a modell így megenged olyan megoldást, ami több, kisebb kör uniójából áll.
A kisebb körök persze azt jelenti, hogy a csúcshalmazából nem lép ki egy megoldásbeli él sem. Tehát ha a városok minden valódi részhalmazára előírjuk, hogy legalább 1 él menjen ki belőle, akkor a kapott megoldás Hamilton-kör kell, hogy legyen. Evvel persze az a baj, hogy exponenciálisan sok részhalmaz van, exponenciálisan sok feltételt kéne felírnunk. Az egyenlőtlenségek nagy része persze felesleges valamilyen értelemben, úgyhogy legalább is egy heurisztikát lehet ebből készíteni:
Az első feladatunk legyen az eredeti, kis körök kizárása nélküli feladat. Amíg nem találtunk Hamilton-kört Oldjuk meg a jelenlegi feladatot. Olvassuk le a jelenlegi megoldás 1. csúcsot tartalmazó körét. Ha ez Hamilton-kör, akkor készen vagyunk. Egyébként vegyük hozzá a kör csúcshalmazához tartozó feltételt a feladathoz Jó esetben a feltételek száma jóval 2^n alatt marad, illetve a megoldó megfelelő beállításával a jelenlegi feladatot elindíthatjuk az előző feladat optimális megoldásából, így a részfeladatok megoldása sem tart olyan sokáig, mintha a nulláról oldanánk meg újra a feladatot. AMPL-ben ezt a run fájlban lehet implementálni. Nézzük meg a tsp.mod, és tsp.run fájlokat, majd próbáljuk ki a tsp.dat, tspusa15.dat, tspusa20.dat bemenetekkel. (Egy zip-ben)
Egészértékű LP felírás
A feladat még egy pár egészértékű változó segítségével felírható polinomiális méretű feladatként is. Olvassuk el a Wikipédia leírást, és gondoljuk végig, hogy miért működik. Ezután programozzuk le ezt a modellt, és próbáljuk ki a fenti bemeneteken.