Kevesebb átkapcsolás, jobb hálózati kihasználtság

Képzeljünk el egy kapcsolót, amelynek n bemenete és n kimenete van, és amely egy adott pillanatban minden bemenetet pontosan egy kimenettel köt össze. Minden ilyen beállítás egy permutáció. Ha a forgalmi igényt egy táblázatba írjuk, és úgy arányosítjuk, hogy minden sor és minden oszlop összege egy legyen, duplán sztochasztikus mátrixot kapunk. A kapcsoló ütemezése ekkor azt jelenti, hogy a mátrixot permutációmátrixok súlyozott átlagaként írjuk fel: a P_l beállítás az idő λ_l hányadában érvényes (1. ábra). Garrett Birkhoff (1946) és Neumann János (1953) tétele szerint ilyen felbontás mindig létezik. Egy mátrixnak azonban általában sok, eltérő tagszámú felbontása van, és a kérdés az, melyik közülük a legrövidebb. Ez a minimális Birkhoff-felbontás feladata, amely bizonyítottan NP-nehéz.

A cikk szerint a fő alkalmazás a kapcsolók ütemezése, ahol minden tag egy-egy kapcsolóbeállítás, és minden átkapcsolás időbe kerül. A felbontás azonban más területeken is előkerül.

A minimális Birkhoff-felbontás a Quantum Optimization Benchmarking Library (QOBLIB) tesztfeladatai között is szerepel. Ez a nemzetközi gyűjtemény egy 2023-ban az IBM Quantum és partnerei által indított munkacsoportban jött létre; a tárhelyét a berlini Zuse Intézet (ZIB) működteti, gondozását a ZIB, az IBM Research és a Purdue University kutatóiból álló irányítóbizottság végzi. A gyűjteményen kvantumos és klasszikus optimalizálási módszereket mérnek össze.

Magyar szálak

A tétel egyik névadója Neumann János, és a módszerben a magyar matematika két további klasszikus eredménye is megjelenik. Kőnig Dénes 1916-ban bizonyított, a páros gráfok élszínezéséről szóló tétele biztosítja, hogy egy nemnegatív egész elemű mátrix, amelynek minden sor- és oszlopösszege ugyanannyi, mindig felírható egész súlyú permutációmátrixok összegeként. A cikk ezzel indokolja, hogy a keresett felbontás, amelynek súlyai az adatokkal azonos pontosságúak, mindig létezik. A számítás során sokszor kell hozzárendelési feladatot megoldani. Az RCS ezt egymást követő legrövidebb utak keresésével teszi, holtverseny esetén azonban ugyanúgy választ, mint a magyar módszer. Ezt Harold Kuhn dolgozta ki 1955-ben Kőnig Dénes és Egerváry Jenő eredményeire építve, és az ő tiszteletükre nevezte el magyar módszernek.

Egy megfigyelés, két egymás felé haladó lánc

Az új módszer egyetlen megfigyelésre épül. Minden tag minden sorban és minden oszlopban pontosan egy pozíciót fed le. Ezért minden sor és minden oszlop ugyanazt a súlykészletet osztja csoportokra: az elemei a súlyok egy-egy csoportjának összegei. Az 1. ábrán az első sor az 5, 3, 2 súlyokat {5} és {3, 2} csoportra bontja, a harmadik sor {5, 3} és {2} csoportra. A sorok és az oszlopok tehát ugyanazokon a súlyokon „osztoznak”, csak másként csoportosítják őket.

Erre a megfigyelésre épül az RCS. A név a módszer három részének, a Recover (visszanyerés), a Certify (tanúsítás) és a Search (keresés) lépésnek a kezdőbetűiből áll. A részek két, párhuzamosan futó láncot alkotnak. A megoldási lánc egyre rövidebb felbontásokat épít, így a legjobb ismert hossz csökken. A korlátlánc azt bizonyítja, hogy legalább hány tag szükséges, így az alsó korlát nő. Amikor a két szám találkozik, a felbontás bizonyítottan optimális. Minden számítás egész számokkal, kerekítés nélkül folyik, és a módszer minden felbontást ellenőriz, mielőtt elfogadná.

A ritka mátrixokban, amelyek kevés permutációból épülnek fel, a legtöbb elem maga is egy-egy súly, ezért a súlyok a mátrix leggyakoribb értékei (2. ábra). A módszer ezeket kiolvassa, majd olyan szabállyal helyezi el őket, amely helyes súlyok esetén bizonyítottan egyetlen pozíciót sem rögzít tévesen. Egy pozíciót csak akkor rögzít, ha a sorában és az oszlopában még el nem helyezett súlyok közül pontosan egy csoport adja ki az ott álló értéket. A sűrű mátrixokban, amelyek sok permutációból épülnek fel, egyetlen súly sem olvasható ki közvetlenül. Itt a módszer lépésenként épít: minden lépésben akkora súllyal von le egy permutációt, hogy legalább egy elem nullává váljon, és nyalábkereséssel (beam search) a legígéretesebb részmegoldásokat viszi tovább.

Az alsó korlátok legfontosabb új eleme a kétsoros korlát, amely két sor (vagy két oszlop) elemeire épül. Minden tag a két sor egy-egy elemét kapcsolja össze, és az így összekapcsolt elemek minden csoportjában a két sor összege megegyezik. Minél kevesebb ilyen csoportra bontható a két sor, annál több tag kell. Ez a korlát csak a mátrix elemeit használja, és a cikk bizonyítása szerint valós súlyokra is érvényes. Kis méretű sűrű mátrixokon a módszer SAT-megoldóval, vagyis a Boole-féle kielégíthetőségi probléma megoldóprogramjával is bizonyít alsó korlátot; az ilyen SAT-alapú bizonyítás azonban csak az adatokkal azonos pontosságú súlyokra érvényes.

Eredmények

A 375 feladatból 197-nél bizonyított, hogy a felbontás a lehető legrövidebb, és ez a bizonyítás tetszőleges valós súlyokra is érvényes. További 11 sűrű feladatnál SAT-alapú bizonyítás igazolja az optimumot, ez azonban csak az adatokkal azonos pontosságú súlyokra érvényes (3. ábra).

A ritka mátrixok feladata a cikk szerint a gyakorlatban megoldott: a 190 ritka feladatból 187 bizonyítottan optimális, és a maradék háromnál is csak egyetlen tag a különbség a felbontás és az alsó korlát között. A legjobb felbontás minden ritka feladaton legfeljebb 0,07 másodperc alatt megszületett. A sűrű mátrixok jóval nehezebbek. Itt a bizonyítás csak n ≤ 5 méretig sikerült, és n ≥ 4 esetén csak az adatokkal azonos pontosságú súlyokra érvényes. A sűrű mátrixok n² permutációból készültek, az RCS felbontásai mégis ennek csak kis töredékét használják: a 12 soros és nagyobb méreteknél átlagosan 3,8n–4,7n tagot (4. ábra). A nagy (legalább 24 soros) sűrű mátrixok felbontásai azonban mintegy 2,6-szor olyan hosszúak, mint az alsó korlát, és egyelőre nyitott kérdés, hogy a felbontások vagy a korlátok vannak-e messzebb az optimumtól.

A gyűjteménybe korábban más kutatócsoportok is beküldtek megoldásokat. A cikk minden beküldött felbontást egész számokkal ellenőriz, és csak azokat veszi figyelembe, amelyek pontosan visszaadják a mátrixot. Ezek legjobbjánál az RCS felbontása 278 feladaton rövidebb, 79 feladaton azonos hosszúságú, és egyetlen feladaton sem hosszabb; 18 feladatra pedig az RCS adja az első pontos felbontást (5. ábra). A Birkhoff+ nevű módszer gyors, de felbontásai átlagosan 2,1-szer olyan hosszúak, mint az RCS-éi. Egy vegyes egészértékű programozási modell a legkisebb, legfeljebb hatsoros feladatokon öt feladattal többre bizonyít optimumot, mint az RCS, bár ezeken a felbontások hossza azonos. A hatsoros sűrű feladatokon viszont ez a modell két óra után is 1–3 taggal hosszabb megoldásnál áll meg. A kvantumos összetevőt is használó módszerek, például a Frank és Wolfe algoritmusára épülő, QAOA-mintavétellel dolgozó módszer, többnyire csak legfeljebb nyolcsoros feladatokon adtak pontos felbontást. Kivétel egy 16 soros feladat 66 tagú felbontása; erre az RCS 16 tagú felbontást talált. Az RCS-énél rövidebbet ezek a módszerek sem adtak.

Ami még nyitott

A cikk a módszer korlátait is megnevezi. A nagy sűrű mátrixoknál a rés bezárásához a kétsoros korlát önmagában nem elég, mert egy sűrű mátrix két sora sok csoportra bontható; erősebb korláthoz a cikk szerint olyan érvelés kell, amely egyszerre több sort vesz figyelembe. A SAT-alapú bizonyítások csak az adatok pontosságára érvényesek, és nyitott kérdés, hogy tetszőleges valós súlyokkal adódhat-e rövidebb felbontás. A nagy sűrű mátrixoknál a futásidő is gyakorlati gondot jelent.

A teljes tudományos cikk a definíciókkal, a bizonyításokkal, a megvalósítás részleteivel és az összes feladat eredményével együtt az arXiv-on olvasható: arxiv.org/abs/2610.25837.