DatV, Projektopgave P2

• Opgaveformulering ps, pdf
  • 15/11: mindre præcisering af opgave 3 tilføjet.
  • 17/11: mindre præcisering af opgave 4 tilføjet.
  • 18/11: ny path angivet til licensfil for CPLEX.
  • 19/11: mindre præcisering af opgave 5 (mængden S_C skal naturligvis være en ægte delmængde af alle knuder)
• Rammeprogram tsp.c Husk at ændre '#define TMPFILE' til noget unikt (f.eks. di04****.lp)!
  • 22/11: Rettelse i rammeprogrammets Branch-and-bound funktion. Husk at opdatere.
  • 24/11: Rettelse i udskrivning af antallet af snit i BAB metoden.
  • 24.11: LEDA er droppe. I stedet kan filerne Graph.h, Graph.c og GraphAlg.h bruges.
    • Graph.h indeholder en sparse graf klasse, som oprettes med antallet af knuder i grafen som argument (Sparse_Graph *G = new Sparse_Graph(n);) eller (Sparse_Graph G(n);) hvis man vil have den statisk allokeret.) Herefter kan tilføjes kanter med addEdge-funktionen. Graph.c implementerer graf klassen.
    • GraphAlg.h indeholder grafalgoritmerne BFS, bredde først søgning, og MinimumSTCut, et minimum cut mellem s og t i en graf.
  • 2/12: Hint til grafen: Knuderne eksisterer i grafen efter oprettelse, ingen grund til at oprette nye. Kanter kan indsættes ved at give id'erne på knuderne samt en omkostning, dvs. ingen grund til at new'e knuder her. Benyt to faste knuder som s og t og sæt deres id inden hvert kald af MinimumSTCut. Husk at kanter til knuden selv ikke skal tilføjes.
  • 3/12: Staff siger cplex er igang igen. Download patchen og følg instruktionerne her:
    • Gem patchen i kataloget hvor tsp.c ligger
    • Kør kommandoen 'patch < tsp-glibc_workaround.patch'
• Makefile Makefile (virker kun på brok)
  • 16/11: Makefile til bach-[0-3] maskinerne lagt op
  • 19/11: Makefile til bach-[0-3] rettet her.
  • 22/11: Der er stadig problemer med at linke med LEDA på bach-[0-3]. Vi arbejder på det.
  • 24/11: Ny Makefile uden LEDA link. Virker på bach-[0-2], bemærk virker ikke på bach-3.
• Instanser rand5, rand10, bornholm, burma14, gr17, gr21, gr24, gr48, gr120, bays29, bayg29, swiss42, br17, ftv33, ftv35, ftv38, ftv44, ftv47, ftv55, ftv70, ftv170, ry48p
• Meget store instanser (husk at udvide tabeller) rbg323, rbg358, rbg403, rbg443, si535, si1032

For at kunne få en licens til CPLEX skal man skrive 'setenv ILOG_LICENSE_FILE /opt/cplex/cplex70/etc/cplex.ilm' før man kører sit oversatte program. Man kan også bare indsætte linjen i sin '.tcshrc'-fil, så virker det næste gang man logger ind. For at køre de meget store instanser kan det være nødvendigt at allokere tabellerne med malloc. Se også CPLEX online-manual appendix A for tuning af CPLEX's parametre, og appendix C for diverse CPLEX fejlkoder. Bemærk at manualen kun kan læses fra DIKU's maskiner.

Meget store instanser (som tager mere end et minut at løse) skal afvikles på projektmaskinerne.

Konkurrence

Der udloves en øl til den gruppe der løser det største TSP problem. Såfremt flere grupper løser samme størrelse problem, er vinderen den gruppe der løser problemet hurtigst.

Bemærk at de største assymetriske instanser i TSPLIB er rbg323, rbg358, rbg403, rbg443, så hvis I kan løse disse er det temmelig imponerende.

Bemærk si535 og si1032 instanserne er givet ved en øvre trekantsmatrix, så indlæsningsrutinen skal ændres for at få indlæst instansen korrekt. Endvidere skal erklæringen
double x1[MAXV*MAXV];
ændres til
static double x1[MAXV*MAXV];
så den ikke kommer på stakken. (tak til Philip, Mads og Niels).

Send dine bedste tider til pisinger@diku.dk for at deltage. Sidste frist for indsendelse af tider er torsdag den 9. december. Vinderen kåres ved forelæsningen fredag den 10. december.

All participants

Winning teams