Sistemi con Vincoli 2016/2017

Sistemi con Vincoli 2016/2017 michele.lombar… Wed, 01/03/2017 - 10:44

Questo sito Web è dedicato al corso di Sistemi con Vincoli, presso l'Università di Padova.

Il sito vuole consentire agli allievi di avere accesso a tutte le informazioni relative a finalità, contenuti, testi adottati e modalità di valutazione del corso.

ATTENZIONE: mercoledì 10 Maggio ci sarà lezione in aula, mentre Giovedì 11 Maggio in laboratorio.

Orario del corso: consultabile sul sistema informatizzato del corso di laurea.

Titolare del corso:
Dott. Michele Lombardi, Tel. 051 20 93270, michele <dot> lombardi2 <at> unibo <dot> it
Ricevimento: su appuntamento, subito prima o subito dopo le lezioni


Obiettivi

Fornire una introduzione complessiva alla tecnica di Programmazione a Vincoli, a partire dalle basi sue basi teoriche fondamentali. L'enfasi del corso sarà su metodi di modellazione, propagazione di vincoli e strategie di ricerca direttamente applicabili a problemi pratici. Una parte consistente delle ore del corso sarà svolta in laboratorio, così da consentire agli allievi di maturare familiarità con risolutori a vincoli allo stato dell'arte.

Gli obiettivi pricipali del corso sono:

  • Apprendere tecniche potenti e mature per la risoluzione di problemi di soddisfacimento di vincoli e di ottimizzazione combinatoria
  • Apprendere le basi teoriche della Programmazione a Vincoli
  • Fornire esempi pratici

Inoltre:

  • Insegnare a leggere in modo critico un articolo di rassegna su un argomento del corso
  • Fornire un approccio pratico a problemi reali
  • Insegnare a preparare una presentazione simile a quella di laurea

Metodi e materiale

  • Il corso sarà costituito da lezioni frontali e sessioni di laboratorio
  • Il materiale didattico sarà costituito principalmente dalle slide del corso
  • Alcuni articoli scientifici verranno proposti come letture consigliate
  • Le slide del corso e delle sessioni di laboratorio saranno pubblicate di volta in volta nella apposita sezione del sito

Lo strumento software utilizzato in laboratorio sarà Google or-tools, disponibile gratuitamente. Apposite istruzioni di installazione saranno fornite dopo la prima sessione di laboratorio.


Modalità d'esame

L'esame sarà costituito da un prova scritta, più un progetto (opzionale, in linea di massima da 0 a 3 punti addizionali)

  • La prova scritta conterrà esercizi e domande di teoria
  • Con il progredire del corso, verrano forniti fac-simile di esercizi e temi d'esame
  • Il tema del progetto andrà concordato con il docente
  • Il progetto dovrà essere presentato (orale + slides, eventualmente una demo)

 

Laboratorio

Laboratorio michele.lombar… Tue, 20/10/2015 - 22:29
Sessioni di Laboratorio
  • Sessione 1: introduzione a python e Google or-tools [pdf] [web]
  • Sessione 2: modellare problemi semplici [pdf] [web]
    • L'esercizio 2 sarà brevemente rivisto anche in una delle prossima sessioni. Se qualche studente vuole provare già a svolgerlo lo faccia liberamente (può essere utile per rendersi conto di alcune difficoltà).
    • Start Kit [zip]
    • Soluzioni [zip]
  • Sessione 3: ottimizzazione [pdf] [web]
    • Start-kit [zip] (sono stati corretti dei bug nell'implementazione del metodo di ricerca binaria)
    • Per la soluzione, si veda il capitolo 6 nelle lezioni del corso
  • Sessione 4: problema di ottimizzazione #2 [pdf] [web] [screen-rec]
    • Start-kit [zip]
    • Soluzione (per miglioramenti vedere la sessione 5) [zip]
  • Sessione 5: migliorare le prestazioni di un modello [pdf] [web] [screen-rec]
    • Start-kit per il Partial Latin Square [zip]
    • Start-kit per il problema di server consolidation [zip]
    • Soluzione [zip]
  • Sessione 6: implementare una strategia di ricerca [pdf] [web] [screen-rec]
  • Sessione 7: utilizzare vincoli globali [pdf] [web] [screen-rec]

 

Un po' di idee per il progetto [web] (la pagine verrà aggiornata nel tempo)

 

Riferimento per l'API di Google or-tools

Un foglio di riferimento per python

 

Le istruzioni sull'installazione di Google sono disponibili qui. Qualche raccomandazione:

  • Per il corso, sarà sufficiente l'installazione python
  • Per installare python su sistemi Win e OS X, si consiglia di utilizzare la distribuzione Anaconda
    • Anaconda contiene già ipython (console python avanzata) ed un package manager utilizzabile da riga di comando

 

Materiale Didattico

Materiale Didattico michele.lombar… Mon, 05/10/2015 - 16:11

Lezioni del corso

I lucidi verrano resi disponibili mano a mano che il corso progredisce.

Per alcune lezioni è disponibile una registrazione (voce + slides)

I lucidi sono in lingua inglese.

Articoli consigliati

Durante il corso, verranno indicati degli articoli scientifici come lettura consigliata.

  • Un articolo sulle simmetrie e tecniche di eliminazione delle simmetrie [pdf]
  • Un articolo recente su un dominance breaking constraints [pdf]
  • Una rassegna di Jean-Charles Régin sui vincoli globali [pdf]
  • Un articolo di Christian Bessièere sugli algoritmi di propagazione [pdf]

 

Temi D'Esame

Temi D'Esame michele.lombar… Wed, 20/01/2016 - 10:42

Esercizi svolti a lezione

  • Esercizi tipo esame #1 [screen-rec]
    • Senza soluzioni [pdf]
    • Con soluzioni [pdf]
    • È stato corretto un piccolo errore (requisiti e durate invertiti in un cumulative nella soluzione dell'esercizio di modellazione)
    • Aggiunto lo stato della coda di AC3 nella soluzione dell'esercizio sulla propagazione
  • Esercizi tipo esame #2 [screen-rec]
    • Senza soluzioni [pdf]
    • Con soluzioni [pdf]
    • È stato corretto un piccolo errore (capacità del vincolo cumulative nel testo di un esercizio)
  • Esercizi tipo esame #3 [screen-rec]
    • Senza soluzioni [pdf]
    • Con soluzione [pdf]
    • È stato correto un piccolo errore (un indice di variabile scorretto nel testo sull'esercizio su AC1)

Alcuni esami passati

Alcuni esercizi di modellazione (tratti da esami svolti a Bologna)