QAP og jagten på millionen

I aften skal jeg holde foredrag i Ungdommens Naturvidenskabelige Forening om NP-fuldstændighed. Noget af det, computere formodentlig ikke kan gøre generelt, er at beregne en optimal fordeling af resurser. Eller rettere: selvfølgelig kan man lave en algoritme, der simpelthen afprøver alle muligheder, men den vil være uhyggeligt ineffektiv. Klassen af de problemer, hvor det er nemt at finde en løsning, kalder man i teorien for beregningskompleksitet for P. Klassen af problemer, for hvilke det er nemt at kontrollere et bud på en løsning, kaldes for NP. De værste problemer i NP er de NP-fuldstændige problemer, og det er et åbent problem om disse problemer ligger i P. Er det tilfældet, ved vi at P = NP. Clay Mathematics Institute har P=NP-problemet angivet som et af de 7 åbne forskningsproblemer i matematik, hvis løsning vil give en præmie på 1 million amerikanske dollars. Dette sidste er den del af historien, der plejer at fascinere lægfolk mest – historien om millionen, der venter, afslører, at der er  matematiske problemer, der er uløste og udfordrende.

Ét af de NP-fuldstændige problemer, som man ikke hører så meget om i typiske algoritmekurser på datalogiuddannelserne, er det kvadratiske tildelingsproblem. Det er et højst reelt problem.

Hvis vi skal bygge et hospital, ved vi hvor store afstandene er i bygningen og vi ved også, fordi vi kender arbejdsgangene på hospitalet, hvor mange patienter, der skal flyttes mellem de enkelte afdelinger. Hvis vi kender størrelsen på denne “strøm” af patienter og betegner strømningen fra afdeling i til afdeling j med f_{ij}, handler det om at finde en tildeling af bygningsafsnit til hver enkelt afdeling på hospitalet. Lad os sige at p(i) betegner den bygning, som afdeling i har fået og lad d_{p(i)p(j)} betegne afstanden mellem disse to afdelinger. Så er den samlede afstand, som patienter skal flyttes, summen

\sum_{i} \sum_{j} f_{ij} d_{p(i)p(j)}

Og spørgsmålet er så, hvordan skal fordelingen af bygninger p mon se ud for at minimere denne sum. Hvis der er n bygninger, er der n! = 1 \cdot 2 \cdots (n-1) \cdot n muligheder for at fordele afdelingerne, så der er uhyggeligt mange muligheder at undersøge. Allerede i 1968, dvs. før Stephen Cook introducerede begrebet NP-fuldstændighed, anede forskerne, at der var noget her, der var rigtig træls. Nugent, Vollman og Ruml identificerede en samling instanser af problemet som de anså for at være særligt besværlige at løse med en “prøv-alle-muligheder”-algoritme. Først i 2000 lykkedes det Kurt Anstreicher, Nathan Brixius, Jean-Pierre Goux og Jeff Linderoth at beregne en løsning til den værste af disse instanser, den såkaldte nug30-instans. Takket være brug af massivt parallel beregning fik de fundet løsningen på “kun” 7 dage!

Der er andre, der har kastet sig over andre trælse instanser af tildelingsproblemet. En anden klasse af besværlige instanser kaldes esc-instanserne (som skyldes Eschermann og Wunderlich) og tai-instanserne, og nu er der godt nyt om nogle af disse. For få uger siden lykkedes det Matteo Fischetti, Michele Monaci og Domenico Salvagnin fra universitetet i Padova at knække esc64a med kun en halv times beregningstid og tai64c med kun 5 timers beregningstid. Og ikke nok med det – de klarede esc128 på få sekunder på én pc.

Den dårlige nyhed er selvfølgelig, at der ikke er tale om en generel strategi. Millionen er ikke blevet uddelt. Italienernes algoritme er stadig baseret på at afprøve alle muligheder, men den udnytter pæne egenskaber ved de problem-instanser, der er tale om.

Ovre i Ukraine sidder der imidlertid en professor ved navn Anatoly Plotnikov og hævder at have bevist at P er forskellig fra NP. Det er han ikke ene om – det er forbløffende, så mange der mener at have bevist at P er forskellig fra NP, og så mange, der mener at have bevist at P er lig med NP. Efter mandens ansigtsudtryk at dømme har han ikke modtaget millionen, men hans universitet viderebringer glad og gerne denne epokegørende (men tvivlsomme) nyhed.