O2-opgave: Heltalsprogrammering

Heltalsprogrammering er en af de hyppigst anvendte metoder til formulering og løsning af NP-hårde optimeringsproblemer. Dette beror på problemets generalitet, idet næsten ethvert problem på lineær form kan formuleres som et heltalsprogrammeringsproblem. Igennem de seneste årtier er der lagt et stort arbejde i at udvikle heltasprogrammeringsløsere, og kommercielle algoritmer er i stand til at løse problemer med flere hundrede (heltallige) beslutningsvariable.

Vejledende løsning til opgaven (udarbejdet af Jens Kristian Jensen)
Opgaveformulering som postscript fil og som pdf fil. (opdateret 3/5)
Rammeprogram ipsolver.c. (opdateret 3/5)
Rammeprogram til visual C++ ipsolver.c. (indføjet 25/4, tak til Henrik Stuart)
Heltalsprogrammeringsproblemer
- mini.lp
- subsetsum10.lp
- subsetsum20.lp
- subsetsum30.lp
- subsetsum40.lp
- subsetsum50.lp (ekstra)
- knapsack10.lp
- knapsack20.lp
- knapsack30.lp
- knapsack40.lp
- knapsack50.lp (ekstra)
- clique6.lp
- clique7.lp
- clique8.lp
- clique9.lp
- tsp4.lp
- tsp5.lp
- tsp6.lp
- tsp7.lp
- tsp8.lp (ekstra)
Følgende link viser instrukser for minestryger spillet.
Følgende link giver mulighed for at spille minestryger.

Eventuelle rettelser i opgaveformulering og rammeprogram vil blive indføjet i ovenstående filer.

24/4: Rettet to parantes-fejl i rammeprogram
25/4: Vedr opgave 1: Det er tilstrækkeligt at vise at IP indeholder SUBSET-SUM (i optimeringsversionen, se kapitel 35) som specialtilfælde. På kurset har vi benyttet definitionen at et optimeringsproblem er NP-hårdt hvis det tilhørende afgørlighedsproblem er NP-fuldstændigt. Men i litteraturen ser man ofte anvendt definitionen at et problem er NP-hårdt hvis det rummer et kendt NP-hårdt problem som specialtilfælde.
27/4: Opgave 4 og 5 omformuleret.
1/5: Opgave 2 tillader at b er 0, 1, -1.
1/5: Hint til opgave 2: Reducer fra 3CNF. Hvis udtrykket på 3CNF rummer variablene x1, x2, ... xn, kan det være en fordel også at indføre nogle nye variable som angiver negationen af x'erne. F.eks. vil ligningen n1 + x1 = 1 betyde at n1 er 1 når x1 er 0 og vice versa.
2/5: Hint til opgave 10: Følgende ramme til opgave 10 kan med fordel benyttes.
3/5: Der er tilsyneladende fejl i funktionen rint(x) hvis man oversætter med -ansi. Man kan enten vælge at oversætte uden -ansi flaget eller at omdefinere rint(x) ved brug af
#define rint(x) (floor((x)+0.5))
3/5: I opgave 9 er det tilstrækkeligt at modificere grænseværditesten så alle semi-kritiske knuder bliver besøgt.
For at generere samtlige løsninger er det nødvendigt at modificere branching strategien. Her er det tilladt at udnytte at vi løser minesweeper problemet, og specielt at alle beslutningsvariable svarende til miner er 0-1 variable.

Konkurrence

For at deltage i konkurrencen skal en eller flere af følgende minstryger instanser løses. Indsend dine køretider og antal branch-and-bound knuder til pisinger@diku.dk. Sidste frist for deltagelse i konkurrencen er tirsdag 14. maj kl. 12.00. Præmie overrækkes ved forelæsningen onsdag den 15. maj.

minesweeper19a.lp (ca. 10 min)
minesweeper19b.lp (ca. 10 min)
minesweeper19c.lp (ca. 10 min)
minesweeper21a.lp (ca. 30 min)
minesweeper21b.lp (ca. 10 min)
minesweeper21c.lp (ca. 10 min)
minesweeper21d.lp (ca. 20 min)
minesweeper21e.lp (ca. 40 min)

For at løse ovenstående instanser skal MAXN og MAXM i rammeprogrammet ipsolver.c defineres til 1000.

Bedste køretider i sekunder

Branch-and-bound knuder angivet i parantes

navn	computer	19a	19b	19c	21a	21b	21c	21d	21e
Emil Soelberg Frisendal	fjalar (800MHz)	163 (21)	671 (65)	170 (19)	1167 (57)	251 (17)	261 (15)	500 (29)	496 (27)
Kristian Lerche Nielsen	6 MHz 086'er m 16k ram	569 (45)	947 (59)	1154 (75)	2738 (81)	912 (41)	1025 (37)	1054 (41)	4305 (103)
Bjørn Petersen (a)	Athlon 1533Mhz	43 (7)	79 (12)	22 (4)	346 (20)	344 (22)	8 (1)	7 (1)	436 (22)
Bjørn Petersen (b)	Athlon 1533Mhz	80 (12)	27 (5)	13 (3)	466 (26)	254 (16)	9 (1)	7 (1)	279 (15)
Bjørn Petersen (c)	Athlon 1533Mhz (dual)	37 (9)	58 (14)	18 (4)	134 (14)	64 (8)	8 (0)	7 (0)	186 (18)
Bjørn Petersen (d)	Athlon 1533Mhz (dual)	47 (12)	16 (4)	8 (2)	490 (21)	124 (14)	8 (0)	7 (0)	112 (11)
Emil Soelberg Frisendal	Celeron 506 MHz	169 (11)	56 (4)	28 (2)	1609 (36)	543 (15)	19 (0)	16 (0)	596 (14)
Emil Soelberg Frisendal	Celeron 506 MHz (dual)	111 (9)	174 (14)	54 (4)	396 (14)	219 (9)	19 (0)	16 (0)	513 (18)
Jens K. Jensen	???	39 (5)
Morten Nielsen	Intel 866MHz	12 (2)	12 (2)	7 (1)	25 (2)	36 (3)	52 (4)	25 (2)	157 (12)
Morten Nielsen (b)	Intel 866MHz						25 (2)		51 (4)
Peter Berg Larsen	'alvis'	21 (165)	8 (1)	6 (1)	241 (267)	123 (189)	88 (120)	73 (56)	285 (205)
Allan Nordlunde Hjorth	'grerr'	18 (3)	65 (9)	94 (13)	45 (3)	119 (9)	41 (3)	633 (45)	353 (21)

Metoder

Bjørn Petersen (a) (b): Jeg kører simplex på begge delproblemer til at starte med, og vælger så en løsning ud fra hvilket z der er størst eller mindst. Det er vist det man normalt ville kalde ivrig.
Bjørn Petersen (c) (d): Jeg har paralelliseret min løsning! Antallet af branch er som tidligere nævnt ikke det samme som antallet af kald til simplex. De kan dog hurtigt oversættes (#simplex = 2*#Branch + 1).
Emil Soelberg Frisendal: Jeg har mere eller mindre fulgt opskriften fra opgavebeskrivelsen. Jeg har dog bestræbt mig på at skrive 'hurtig kode', fx. undgå nestede for loops, samle flere for loops i een osv. Det er faktisk også et spørgsmål om held... fx. kan der være _stor_ forskel om man vælger 'venstre' underrum fremfor højre.
Kristian Lerche Nielsen: Hovedet totalt under armen algoritme: Første variabel i LP-løsningen som ikke er et heltal bliver delt i to constraints. Før eller siden sikres det at alle variable bliver heltallige.
Jens K. Jensen: Jeg forgrener på den variabel, der er tættest på at være heltallig OG på den variabel, der giver størst udbytte. Jeg får altså 4 nye knuder hver gang (med mindre de to variabler er sammenfaldende).
Emil Soelberg Frisendal: Ivrig og multitrådet. Oversat med VC++.NET på WinXP.
Morten Nielsen: Metoden er den samme som i det udleverede pseudo-kode.
Peter Berg Larsen: Jeg forgrener i en bestemt reakkefoelge (den som de indlaeses i). Er der helt talsloesninger genbruger jeg de gamle tal, derfor kalder jeg simplex meget faerre gange end antal besoegte knuder.
Allan Nordlunde Hjorth: Min løsningstrategi minder meget om Kristian Lerche Nielsen's: Følg opskriften uden nogen særlig optimering. Forskellen er blot at jeg deler op efter den sidste ikke-heltallige variabel i LP-løsningen. Det giver åbenbart en rimelig stor forskel i disse eksempler, da antallet af branch-and-bound knuder bliver ret lavt (bortset fra i 21d).

pisinger@diku.dk.