Je cherche des avis et conseils sur une problématique assez spécifique. Voici le lien du sujet détaillé dans les discussions de programmation générale :
Voici un problème qui m'a l'air drôlement intéressant !
Je vois deux approches possibles :
− Si le nombre de possibilités (de placer les bâtiments) n'est pas trop élevé, calculer toutes les possibilités et retenir la meilleure. Est-ce que tu as une estimation du nombre de possibilités ? On ne sait jamais, ça vaut peut-être le coup de se poser la question.
− Sinon, c'est un problème d'optimisation mathématique et ce n'est pas forcément trivial. En gros, il faut définir une fonction qui retourne le nombre de blocs à ajouter : c'est la fonction qu'on veut minimiser. En entrée, il faut définir un vecteur contenant les données du problème. On a donc une fonction x = f(u) où x est le nombre à minimiser et u est le vecteur qui permet d'obtenir ce minimum. Dans ce cadre, il existe des méthodes mathématiques permettant de trouver un minimum (méthode du gradient, par exemple). Le problème est que ces méthodes marchent sous certaines conditions théoriques qui ne sont peut-être pas remplies (de plus s'agira-t-il d'un minimum relatif ou absolu ?).
- Concernant la première approche émise, en omettant la contrainte des routes et en admettant une moyenne de 100 bâtiments, alors le nombre de possibilités reste raisonnable. Avec les routes, le nombre de possibilités est nettement supérieur mais beaucoup se révéleraient rapidement fausses (conditions non remplies, routes tronquées ou liaisons à l'hôtel de ville impossible). En terme de temps de calcul cela pourrait demander plusieurs minutes voire dizaines de minutes, cela dit ce critère n'est pas important tant que j'arrive à le maintenir dans les limites de l'acceptable.
- Pour la seconde approche, tu m'as beaucoup aidé, c'est tout à fait le genre de réponse que j'étais venu cherche. J'avoue que les mathématiques sont mon point faible, j'ai pas mal de lacunes. En reprenant mes recherches à partant de la méthode du gradient puis la recherche linéaire, cela m'a fourni des pistes de réflexion. Par exemple, le multiplicateur de Lagrange peut-il être utilisé pour ce cas ou je fais fausse route ? Pour répondre à ta question, il s'agira du minimum absolu, idéalement.
Je suis encore assez loin de la totale compréhension, j'en ai au moins saisi l'aspect théorique et je sais maintenant quoi chercher, me restera après coup à convertir le tout en programmation.
Le souci avec la seconde approche, c'est que ça va te demander du temps : du temps pour assimiler les notions mathématiques. La méthode des multiplicateurs de Lagrange est en effet une éventualité. Après, c'est juste une piste : ça se trouve, il ne sera pas possible d'utiliser en pratique ces méthodes, par exemple parce que la fonction qui mesure le nombre de blocs à ajouter ne s'y prête pas (j'ai un vague souvenir comme quoi ce genre de méthode marche bien si la fonction est convexe, ce qui se produit naturellement avec certains types de problèmes, mais là je n'en sais rien...)
De plus, je préfère préciser que, pour moi, tout ça ne sont que des souvenirs. J'ai vu ces méthodes lors de mes études, mais ça remonte au siècle dernier et j'ai à peu près tout oublié... (Mais j'aimais bien cette discipline !)
Oui c'est certains que le projet en lui même, et tout les étapes d'apprentissages qu'il implique vont me demander beaucoup de temps. Ce n'est pas important, je ne suis pas pressé, comme j'ai dit, c'est un projet perso. S'il me faut 6 mois pour le faire ça me va. Je ne veux pas bosser dessus 12h par jour. Avec ce projet, je cherche à repousser mes limites et ces complications sont parfaites, cela me force à explorer tous les angles d'approche dès le début du projet. J'aime autant ces phases d'analyse que la programmation en elle même.
J'y vois déjà plus clair et je pense que je vais commencer à poser sur papier la première approche et la coupler avec les propositions de TabouretBleu (dans l'autre conversation). Peut-être que les résultats obtenus au fil du développement vont orienter une méthode d'optimisation plus qu'une autre. Cela me laissera aussi du temps pour appréhender ces concepts mathématiques qui me font défaut.
A vue de nez, ca devrait pouvoir se résoudre avec de la programmation par contraintes. L'idée est de faire une recherche arborescente (type branch and bound) en utilisant les contraintes pour réduire le domaine des valeurs possibles pour chaque variable.
Quant aux langages, voilà une liste non exhaustive. Le plus simple est sûrement d'écrire un modèle AMPL (un langage de modélisation assez intuitif) et de résoudre le problème en utilisant les solveurs du serveur NEOS.
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Mon portfolio photo : https://www.instagram.com/charlievanaret_photo/