Quel algorithme (s) peut résoudre ce problème de la programmation par contraintes?

Question

Je dois résoudre un problème d'emploi et afféterie je voudrais trouver des algorithmes de préférence efficaces pour résoudre ce problème.

Disons qu'il ya des travailleurs qui peuvent faire plusieurs types de tâches. Nous avons aussi un groupe de tâches qui doit être fait chaque semaine. Chaque tâche prend un certain temps. Chaque tâche doit être prise par quelqu'un. Chaque travailleur doit travailler entre une heure N P par semaine.

Cette première partie du problème semble être un bon candidat pour un algorithme de programmation par contraintes.

Mais voici la complication: parce qu'un travailleur peut faire différentes tâches qu'ils peuvent aussi avoir des préférences (ou souhaits). Si l'on veut satisfaire tous les souhaits pour tout le monde il n'y a pas de solution au problème (trop de contraintes).

Je dois donc un algorithme pour résoudre ce problème. Je ne veux pas réinventer la roue si la roue parfaite existe déjà.

L'algorithme doit être juste (si l'on peut définir ce mot) ainsi, par exemple, je devrais être en mesure d'ajouter une contrainte comme « essayer de satisfaire au moins un souhait par les gens ». Je ne suis pas sûr que ce problème peut être résolu par des méthodes décrites ici Constraint Hiérarchies: Constraint Herarchies. En fait, je ne suis pas sûr que « l'équité » et souhaits peuvent être exprimées par des contraintes valides pour cette catégorie d'algorithmes.

Y at-il un expert en matière de programmation par contraintes pour me donner quelques conseils? Ai-je besoin de développer une nouvelle roue avec quelques heuristiques au lieu d'utiliser des algorithmes efficaces CP?

Merci!

Answer 1

Votre problème est assez complexe qu'une solution générale exigera probablement la formulation comme linéaire entier problème. Si d'autre part, vous êtes en mesure d'assouplir certaines exigences, vous pourriez être en mesure d'utiliser une approche plus simple. Par exemple, biparti vous permettrait de planifier correspondant à plusieurs travailleurs à de multiples emplois, et peut même gérer préférences, mais ne serait pas en mesure d'imposer des contraintes « d'équité » générales. Voir par exemple cette question liée SO. coloration Vertex a des algorithmes efficaces pour faire respecter les contraintes de cessation d'emploi.

D'autres l'ont mentionné simplex et planification boutique d'emploi . Simplex est un algorithme d'optimisation - il traverse un espace de solution cherchant à maximiser une fonction objective. La fonction objective formulation peut certainement être fait, mais est non négligeable. ordonnancement classique magasin de travail, comme la correspondance bipartites, peut modéliser certains aspects de votre problème, mais pas tous. Il n'y a pas de contraintes de priorité, par exemple. Il existe des versions étendues qui peuvent gérer certaines contraintes, par exemple placer des limites de temps sur les tâches.

Si vous êtes intéressé par les implémentations existantes, la bibliothèque Python NetworkX a une implémentation de cet algorithme correspondant . Un exemple d'un programme d'emplois du temps open source qui pourrait être d'intérêt est Tablix .

Answer 2

Je l'ai fait emplois du temps, ce qui peut être considéré comme une forme de programmation par contraintes. Vous avez des contraintes dures (inviolables) et des contraintes souples (comme les préférences d'intervalle).

programmation linéaire entier devient généralement inutile après plus de 30 variables, et cela peut aussi être dit au sujet simplex.

Il était creux optimisations spécifiques au domaine des algorithmes heuristiques qui a été trouvé une solution.

Les algorithmes heuristiques utilisés étaient simmulated recuit , algorithmes génétiques , algorithmes métaheuristiques et similaires, mais à la fin le meilleur résultat ont été fournis par un « intelligent » domaine personnalisé recherche avide algorithme .

En fait, vous pourriez obtenir des résultats décents avec un des heuristiques ici, mais le principal problème est d'être capable de discerner quand un problème est surcontraint.

Un outil open source pour la recherche est le HeuristicLab .

Answer 3

Je suis d'accord avec ce qui a été proposé ici. Cependant, MIP (problèmes de programmation mixte en nombres entiers) de très grande taille (bien au-delà 30 variables!) Sont pratiquement résolus de nos jours grâce à des codes commerciaux (Xpress, CPLEX, Gurobi) ou open-source (Coin-Or / Cbc). En outre, les langages de modélisation de fantaisie tels que OPL Studio GAMS, AMPL, ... Flop permettent d'écrire facilement des modèles mathématiques au lieu d'utiliser des API.

Vous pouvez profiter du serveur NEOS ( http: //neos.mcs .anl.gov / Neos / solveurs / index.html ) pour essayer très différents esaily MIPS disponibles. Vous envoyez votre modèle au format AMPL. Bien que AMPL se présente comme une version limitée gratuite, NEOS peut gérer un nombre illimité de cas.

langages de modélisation existent également pour les CP (COMET / OPL Studio) et Recherche locale (COMET).

Sentez-vous (page 'contact') sans entrer en contact avec moi à travers mon site web www.rostudel.com

David

Answer 4

Cela ressemble à planification de magasin de travail .