Határidő: 2022-04-16 24:00

• Az NP-teljes problémák megoldásának egy másik ismert módszere az, hogy a problémát visszavezetjük egy másik, jól ismert NP-teljes problémára. Ha a jól ismert problémára rendelkezésünkre áll egy hatékony heurisztikus megoldó, akkor általában jobb eredményt tudunk elérni, mint a nyers erővel.
• A feladatban egészértékű lineáris programozás (EP) segítségével oldjuk meg az előző hétről ismerős CLIQUE problémánál kicsit általánosabb MAXCLIQUE problémát. Ebben nem egy adott \(k\) méretű, hanem egy maximális méretű klikket keresünk. Az egészértékű lineáris programot a PuLP Python csomag segítségével oldjuk meg. A csomag a Python beépített pip, illetve pip3 csomagkezelőjével a

  pip install pulp
  

  paranccsal telepíthető.
• A pulppelda.py fájlban megadtunk egy egyszerű példaprogramot, ami a \begin{align*} \max\, x_0 + x_1,\\ \text{ahol } x_0, x_1 \in \mathbb{Z},\\ x_0 \ge 0, \\ x_1 \ge 0, \\ 2 x_0 + x_1 \le 10, \\ x_0 + 2 x_1 \le 10 \end{align*} egészértékű programozási feladat egy megoldását a standard kimenetre írja. Tanulmányozzuk a programot! A megértéshez segítséget nyújthat a PuLP csomag dokumentációja.
• Készítsünk programot a MAXCLIQUE probléma megoldására!
  1. Olvassuk be a probléma bemenetét, azaz a \(G\) irányítatlan gráfot és a \(k\) számot az előző feladatból megismert formátumú fájlból, bár \(k\) értékét itt nem fogjuk használni. A program az előző feladathoz hasonlóan a fájl nevét parancssori argumentumként fogja megkapni.
  2. Fogalmazzuk meg a MAXCLIQUE problémát egészértékű programozási feladatként.
  3. Programozzuk le az egészértékű programozási feladatot a PuLP csomaggal, és hívjuk meg rá a megoldót.
  4. Írjuk ki a standard kimenetre a maximális méretű klikk méretét a „Maximális klikk mérete:” és egy ilyen halmaz elemeit az „egy ilyen klikk csúcsai:” szöveg után. A PuLP a célfüggvény értékét nem egész, hanem lebegőpontos számként adja vissza. Mivel az egész szám, kiírás előtt kerekítsük!

       Maximális klikk mérete: 4
       egy ilyen klikk csúcsai: 2, 4, 5, 8
     	

  5. A print(prob.solver) függvényhívás kiírja a solver nevét. A megoldáshoz a prob.solve() függvényhívás helyett annak argumentumában adjuk meg e nevet az alábbi módon, hogy a futás üzenetei ne jelenjenek meg a terminálon: prob.solve(pulp.apis.coin_api.PULP_CBC_CMD(msg=0))
• Futtassuk le a programot az előző feladatban kiadott bemenetekkel! Bár most többet követelő feladatot oldunk meg, látható hogy gyorsabb az egészértékű programozás, mint a nyers erő.