In de 2e practicumopgave bouwen we voort op de eerste. De opgave bestaat uit verschillende delen. Deze pagina beschrijft de 1e delen. Opnieuw gaan we een allocatieprobleem oplossen; deze keer gaan we echter gebruik maken van CP solvers en ILP solvers, in plaats van zelf depth-first search te implementeren. Hieronder worden de verschillende stappen beschreven die je dient te nemen.

Downloaden en installeren solvers

We gaan gebruik maken van een Python interface naar verschillende solvers, genaamd Numberjack.

Volg hiertoe de volgende stappen.

1. Download de interface hier
2. Unzip het gedownloade bestand
3. Ga de folder in en type make local_install
4. Let goed op de laatste regels; deze lezen: Remember to add the following lines to your .profile or .bashrc: ...

   Numberjack is na het bovenstaande commando wel geinstalleerd, maar Python kan het nog niet vinden. Hiertoe moet een omgevingsvariabele gedefinieerd worden. Hoe je dit doet, hangt af van de shell die je gebruikt. Type hiertoe echo $SHELL in. Als je hier tcsh ziet, dien je de volgende regels toe te voegen aan ~/.tcsh:

   setenv PYTHONPATH ~/Numberjack/Numberjack-master/local_lib:$PYTHONPATH

   setenv PATH ~/Numberjack/Numberjack-master/local_lib:$PATH

   Type source ~/.tcsh in om de instellingen in te lezen. Hierbij is aangenomen dat je de Numberjack bestanden uitgepakt hebt in de ~/Numberjack/ folder. Voor andere shells gelden andere instructies.

5. Probeer een voorbeeld programma in te typen en uit te voeren:

   from Numberjack import *
   import Mistral
   
   a,b,c = (Variable() for val in range(3))
   model = Model( [ a + b >= 1, a==False, c==True, Minimise(a+b+c)] ) 
   solver = model.load('Mistral')
   
   print solver.solve()
   print solver.printStatistics()
   print a,b,c
   
   

   Wat doet dit programma?

Constraint Programming

Het doel van het eerste deel van opgave is simpel: implementeer dezelfde taak als van het eerste practicum door gebruik te maken de Mistral CP solver die opgenomen is in Numberjack. Je dient hiertoe het probleem te definieren door gebruik te maken van constraints opgenomen in Numberjack. Tip: bekijk ook de voorbeelden en de documentatie van Numberjack.

Evalueer je code op niet al te grote grafen die je willekeurig genereert door middel van de generator die je in de eerste opgave gemaakt hebt.

Integer linear programming

Numberjack ondersteunt de SCIP integer lineair programming solver. Lees de documentatie van Numberjack voor het aan het werk krijgen van deze solver. Pas vervolgens het model van het eerste deel aan zodanig dat je alleen lineaire constraints gebruikt; pas SCIP toe op dit model op dezelfde voorbeelden die je in het eerste deel gebruikte. Welke van de methoden is sneller?

Instructies

Houd er bij de uitwerking rekening mee dat ook de leesbaarheid van je code beoordeeld zal worden: het is belangrijk dat je commentaar opneemt, waar nuttig, en namen voor je variabelen kiest die informatief zijn. Functies moeten overzichtelijk zijn en niet te lang.