Archives de catégorie : Devoir

Projet de recherche locale stochastique

En M2 Bases de données et IA et M2 Image et IA

Par Olivier Bailleux, Maître de conférences HDR, Université de bourgogne

Coloration de nombres entiers

Ce travail facultatif peut rapporter jusqu’à 3 points.

Énoncé

Le problème abordé est la coloration des entiers de 1 à \(N\) en utilisant \(K\) couleurs, où \(N\) et \(K\) sont des entiers donnés, en respectant la propriété suivante : pour tout \(a,b,c\) appartenant à l’ensemble \(1..N\), si \(a+b=c\) alors \(a,b\) et \(c\) ne doivent pas tous avoir la même couleur.

Une autre manière d’énoncer le problème consiste à dire que l’ensemble \(1..N\) doit être partitionné en \( K\) parties telles que pour tout triplet \((a,b,c)\in (1..N)^3\), si \(a+b=c\) alors \(a,b\) et \(c\) ne sont pas dans la même partie. Attention, la règle s’applique aussi si \(a=b\), donc par exemple 3 et 6 ne doivent pas appartenir à la même partie, ou en d’autres termes ne pas avoir la même couleur.

Voici un exemple de solution pour \(N=13\) et \(K=3\) :

  • \(P_1=\{1,4,10,13\}\)
  • \(P_2=\{2,3,11,12\}\)
  • \(P_3=\{5,6,7,8,9\}\)

On vérifie que les sommes inférieures ou égales à 13 de deux valeurs de \(P_1\), c’est à dire \(2,8,5,11\), ne sont pas dans \(P_1\). Le même constat est valable pour \(P_2\) et \(P_3\).

Ce problème est directement lié à la notion de nombre de Schur. Vous pourrez trouver des précisions ici.

Vous devez programmer une application qui tente de trouver une solution à ce problème à l’aide d’un algorithme de recherche locale stochastique.

La solution trouvée, si applicable, doit être affichée de manière lisible et facilement vérifiable, à savoir pour chaque partie \(P_i\), la liste des éléments de cette partie, puis la liste croissante des sommes de ces éléments inférieures ou égale à \(N\).

Par exemple, pour \(N=13\) et \(K=3\), on devrait avoir l’affichage :

P1 : 1 4 10 13 [2 5 8 11]
P2 : 2 3 11 12 [4 5 6 13]
P3 : 5 6 7 8 9 [10 11 12 13]

Monôme ou binôme

Vous pouvez traiter ce sujet seul ou en binôme.

Si vous le traitez seul, vous devrez à minima implémenter l’algorithme de Métropolis et rechercher expérimentalement la température qui maximise l’efficacité de la recherche.

Si vous travaillez en binôme, vous devez implémenter en plus au moins une deuxième stratégie, comme par exemple le recuit simulé avec une variation de température en cours de la recherche.

Critères d’évaluation

Vous serez évalués sur les critères suivants :

  • Pertinence de la représentation des configurations, du voisinage et de la fonction coût.
  • Démarche expérimentale de recherche des meilleurs réglages.
  • Clarté et efficacité du code.
  • Performance de l’application.

Si vous inspirez de travaux publiés, merci de donner les références. Vous pouvez utiliser le langage de programmation de votre choix, après validation par l’enseignant si vous utilisez un autre langage de Java ou C++.

Livrables

Pour livrer ce projet, vous devez vous inscrire à l’équipe Teams Livraison projets PPC 2122 grâce au code d’accès ipr9fop. Vous aurez alors accès à un devoir permettant de livrer le projet.

Les fichiers à remettre sont les suivants. Merci de ne pas les placer dans des archives zip ou autres.

  • Le code commenté, dans un unique fichier. Le code devra être indenté en style Allman, c’est à dire avec un alignement strict des accolades ouvrantes et fermantes.
  • Un document au format pdf d’au plus 10 pages comportant :
    • Une présentation et une justification (théorique et/ou expérimentale) de vos choix en matière de représentation, voisinage, fonction de coût (si applicable).
    • Une description de la ou des stratégies de recherche implémentées.
    • Une présentation des résultats obtenus, avec les temps de calculs correspondants.

Si vous avez travaillé en binôme,

  • l’un des auteurs doit livrer les deux fichiers du projet, avec le nom du coauteur mentionné dans chaque document,
  • et l’autre auteur doit seulement livrer un fichier pdf d’une page sur laquelle est juste indiqué le nom du coauteur.

PPC : Miniprojets

En M2 Bases de données et IA et M2 Image et IA

Par Olivier Bailleux, Maître de conférences HDR, Université de bourgogne

Mini-projets de PPC

Objectif

Maîtriser les bases de l’utilisation de CHOCO avec des contraintes à domaines finis.

Prérequis

Partie I

Miniprojet 1

Ce travail peut rapporter jusqu’à 2 points. Vous pourrez avoir une assistance et une pré-validation avec droit à l’erreur en séances de TP.

Énoncé

Vous devez implémenter en Java et CHOCO un programme permettant de résoudre le problèmes des sacs à dos présenté en exercice de modélisation dans la partie B du cours.

On a \(N\) objets numérotés de 0 à \(N-\)1 et \(K\) sacs numérotés de 0 à \(K-1\). Chaque objet peut être embarqué dans au plus un sac. Chaque objet a un poids et une valeur. On note \(w_0, …, w_{N-1}\) les poids des objets et \(v_0, …, v_{K-1}\) leurs valeurs. Le poids cumulé des objet embarqués dans un même sac ne doit pas excéder une valeur \(W\). La valeur cumulée de tous les objets embarqués dans tous les sacs doit être au moins égale à \(V\).

Vous pouvez bien sûr vous inspirer de la modélisation proposée dans les indices et solutions de la partie B du cours.

Voici comment les données d’une instance du problème peuvent être représentées en Java :

int[] w = {7000,2000,3000,5000,5000,4000,4000,3000,5000,7000};
int[] v = {150,100,200,50,100,200,150,200,100,100};
int N = 10; int K=3;
int V = 1000; int W = 10000;

Votre solution devra être testée avec des instances cohérentes et des instances incohérentes non trivialement simplifiables. Une instance est dite trivialement simplifiable si elle comporte des objets de poids supérieur à \(W\) ou si la somme des valeurs des objets est inférieure à \(V\).

Pour toute instance cohérente, votre programme doit afficher une solution. L’affichage devra indiquer les objet embarqués dans chaque sac, soit sous forme explicite, soit sous une forme permettant de retrouver l’information à partir de l’affichage des valeurs des variables. Dans ce dernier cas, vous devrez donner sous forme explicite, par exemple à l’aide d’une représentation sur papier, les solutions de vos instances de test.

Livrables

Si vous terminez ce projet avant la fin de la première heure de la troisième et dernière séance de TP, vous n’avez pas à rédiger de document. Vous devrez monter à votre enseignant votre code commenté et lui faire une démo en faisant apparaitre explicitement les solutions, quand applicable.

Si vous terminez plus tard et que l’enseignant n’a pas le temps de valider votre travail, vous devrez lui transmettre votre code commenté, une copie d’écran de vos instances de tests et résultats, un document illustrant les solutions obtenues si celle-ci ne sont pas explicites sur les copies d’écran (par explicite on entend que les objets embarqués dans chaque sac apparaissent clairement), et un document d’une ou deux pages expliquant comment vous avez traduit votre modèle théorique en Java + CHOCO.

Miniprojet 2

Énoncé

Vous devez modéliser le problème suivant :

Soit un rectangle de largeur \(L\) et de hauteur \(H\), ou \(H\) et \(L\) sont des entiers. Soient \(K\) rectangles de largeurs et hauteurs \(l_1, h_1,…, l_k, h_k\), qui sont également des valeurs entières.

Peut-on placer les \(K\) petits rectangles dans le grand rectangle sans qu’aucun petit rectangle ne chevauche un autre ? Si c’est possible, une solution doit être donnée. Un affichage graphique de cette solution n’est pas exigé. Les positions des coins inférieurs gauche de chaque petit rectangle sont suffisantes.

La figure ci-dessous donne un exemple d’instance du problème et d’une solution.

image-20211003134447539

Pour traiter ce sujet, vous pourriez avoir besoin de spécifier des contraintes complexes par composition logique (négation, disjonction,…) de contraintes plus simple. La lecture de la documentation du site https://choco-solver.org, et notamment de cette page concernant la composition de contraintes arithmétiques, pourra vous apporter des informations très utiles.

Le petit exemple suivant (sans rapport avec le sujet) montre comment exprimer facilement la contrainte \((A+B=3) \vee (A+B=5)\), où \(A\) et \(B\) sont des variables de domaine \(1..5\).

Model model = new Model("Test");
IntVar A = model.intVar("A", 1,5);
IntVar B = model.intVar("B", 1,5);
( A.add(B).eq(3) ).or( A.add(B).eq(5) ).post();

Livrables

Pour livrer ce projet, vous devez vous inscrire à l’équipe Teams Livraison projets PPC 2122 grâce au code d’accès ipr9fop. Vous aurez alors accès à un devoir permettant de livrer le projet.

Les fichiers à remettre sont les suivants. Merci de ne pas les placer dans des archives zip ou autres.

  • Le code java, dans un unique fichier avec l’extension java, de votre solution. Le code devra être commenté et indenté en style Allman, c’est à dire avec un alignement strict des accolades ouvrantes et fermantes.
  • Un document au format pdf d’au plus 3 pages
    • expliquant succinctement le principe de votre modélisation, avec autant que possible des illustrations qui peuvent être des photographies de dessins réalisées à la main,
    • et présentant les instances avec lesquelles vous avez testé votre programme et les résultats obtenus. Les résultats doivent être représentés sous la forme d’un dessins, ne serait-ce que la photographie d’un croquis fait à la main sur papier. Vous ne serez pas évalués sur la forme. Le seul but est que le correcteur et vous-même puissent vérifier que les solutions trouvées par le solveur sont correctes.

Vous pouvez utiliser l’instance présentée en exemple ci-dessus pour la mise au point de votre programme, mais vous devez créer au moins deux instances de votre cru : une criticalement cohérente et une incohérente non triviale.

Par criticalement cohérente, on entend que la somme des aires des petits rectangles est égale à l’aire du grand rectangle.

Par incohérente non triviale, on entend que la somme des aires des petits rectangles est au plus égale à l’aire du grand rectangle, mais qu’il n’y a aucune solution. Faites preuve de créativité.

Si vous avez travaillé en binôme,

  • l’un des auteurs doit livrer les deux fichiers du projet, avec le nom du coauteur mentionné dans chaque document,
  • et l’autre auteur doit seulement livrer un fichier pdf d’une page sur laquelle est juste indiqué le nom du coauteur.