OptMod-2017/Gyakorlat9

A MathWikiből
(Változatok közti eltérés)
 
(egy szerkesztő egy 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 [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.
+
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., 11: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.

Személyes eszközök