哪些算法可以解决这个约束规划问题？
我需要解决工作情感问题，并且我想找到更有效的算法来解决这个问题。
假设有一些工人可以完成多种任务。 我们还有一系列必须每周完成的任务。 每个任务都需要一些时间。 每项任务都必须由专人承担。 每个工人每周必须工作 N 到 P 小时。
问题的第一部分似乎是约束规划算法的良好候选者。
但这里有一个复杂的问题：因为工人可以执行不同的任务，他们也可能有偏好（或愿望）。 如果一个人想要满足所有人的所有愿望，那么这个问题是没有解决办法的（限制太多）。
所以我需要一个算法来解决这个问题。 如果完美的轮子已经存在，我不想重新发明轮子。
该算法必须是公平的（如果可以定义这个词），因此例如我应该能够添加一个约束，例如“尝试满足每个人至少一个愿望”。 我不确定这个问题可以通过此处描述的约束层次结构方法来解决： 约束层级。 事实上，我不确定“公平”和愿望是否可以通过此类算法的有效约束来表达。
有约束规划专家给我一些建议吗？ 我是否需要开发一个带有一些启发式方法的新轮子，而不是使用高效的 CP 算法？
谢谢 ！
I need to solve a job affectation problem and I would like to find preferably efficient algorithms to solve this problem.
Let's say there are some workers that can do several kind of tasks. We also have a pool of tasks which must be done every week. Each task takes some time. Each task must be taken by someone. Each worker must work between N an P hours a week.
This first part of the problem seems to be a good candidate for a constraint programming algorithm.
But here is the complication: because a worker can do different tasks they may also have preferences (or wishes). If one want to satisfy all wishes for everyone there is no solution to the problem (too many constraints).
So I need an algorithm to solve this problem. I don't want to reinvent the wheel if the perfect wheel already exists.
The algorithm must be fair (if one can define this word) so for example I should be able to add a constraint like "try to satisfy at least one wish per people". I'm not sure that this problem can be solved by Constraint Hierarchies methods described here: Constraint Herarchies. In fact I'm not sure that "fairness" and wishes can be expressed by valid constraints for this category of algorithms.
Is there a constraint programming expert to give me some advices ? Do I need to develop a new wheel with some heuristics instead of using efficient CP algorithms ?
Thanks !
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
我已经制定了时间表，这可以被视为约束规划的一种形式。 您有硬（不可侵犯）约束和软约束（例如间隔偏好）。
线性整数规划通常在超过 30 个变量后就变得毫无用处，对于单纯形也是如此。
通过启发式算法的特定领域优化，找到了解决方案。
使用的启发式算法是模拟退火、遗传算法，元启发式 算法和类似，但最终最好的结果是由定制的“智能”域提供的贪婪搜索 算法。
基本上，您可能会通过这里的一种启发式方法获得一些不错的结果，但主要问题是能够辨别问题何时受到过度约束。
HeuristicLab 是一个很棒的开源研究工具。
I've done timetabling, which can be considered a form of constraint programming. You have hard (inviolable) constraints and soft constraints (such as interval preferences).
Linear integer programming usually becomes useless after more than 30 variables, and this can also be said about simplex.
It was trough domain-specific optimizations of heuristic algorithms that a solution was found.
The heuristic algorithms used were simmulated annealing, genetic algorithms, metaheuristic algorithms and similar, but in the end the best result were provided by an "intelligent" domain customized greedy search algorithm.
Basically, you might get some decent results with one of the heuristics here, but the main problem is being able to discern when a problem is overconstrained.
A great open-source tool for research is the HeuristicLab.
我同意这里提出的建议。 然而，由于商业代码（Xpress、Cplex、Gurobi）或开源代码（Coin-Or/Cbc），现在已经可以实际解决非常大的规模（远远超过 30 个变量！）的 MIP（混合整数规划问题）。 此外，OPL Studio、GAMS、AMPL、Flop 等精美的建模语言允许轻松编写数学模型，而不是使用 API。
您可以利用 NEOS 服务器 (http://neos.mcs.anl。 gov/neos/solvers/index.html）来尝试非常简单的不同可用的 MIP。 您以 AMPL 格式发送模型。 尽管 AMPL 是免费的有限版本，但 NEOS 可以处理无限的实例。
CP (COMET / OPL Studio) 和本地搜索 (COMET) 也存在建模语言。
请随时通过我的网站 www.rostudel.com（“联系”页面）与我联系
David
I agree with what have been proposed here. However, MIP (Mixed Integer Programming problems) of very large size (far beyond 30 variables !) are practically solved nowadays thanks to commercial codes (Xpress, Cplex, Gurobi) or open-source (Coin-Or/Cbc). Furthermore, fancy modeling languages such as OPL Studio, GAMS, AMPL, Flop ... allow to write easily mathematic models instead of using APIs.
You can take advantage of NEOS server (http://neos.mcs.anl.gov/neos/solvers/index.html) to try very esaily different MIPs available. You send your model in AMPL format . Although AMPL comes as a free limited version, NEOS can handle unlimited instances.
Modeling languages exist also for CP (COMET / OPL Studio) and Local Search (COMET).
Feel free to get in touch with me through my web site www.rostudel.com ('contact' page)
David
这听起来像车间调度。
This sounds like job shop scheduling.
您的问题足够复杂，一般解决方案可能需要制定为 线性整数问题。 另一方面，如果您能够放宽某些要求，您也许可以使用更简单的方法。 例如，双向匹配将允许您将多个工作人员安排到多个工作，甚至可以处理偏好，但无法强制执行一般的“公平”约束。 例如，请参阅此相关的SO问题。 顶点着色具有执行作业分离约束的有效算法。
其他发帖者提到了 simplex 和 车间调度。 Simplex 是一种优化算法 - 它遍历解决方案空间，寻求最大化某些目标函数。 制定目标函数当然可以完成，但并不简单。 经典的作业车间调度（例如二分匹配）可以模拟问题的某些方面，但不是全部。 例如，没有优先级限制。 有一些扩展版本可以处理一些约束，例如对任务设置时间限制。
如果您对现有实现感兴趣，Python networkx 库具有 此匹配算法。 您可能感兴趣的开源时间表程序的一个示例是 Tablix。
Your problem is complex enough that a general solution will probably require formulating as a linear-integer problem. If on the other hand you are able to relax certain requirements, you may be able to use a simpler approach. For example, bipartite matching would allow you to schedule multiple workers to multiple jobs, and can even handle preferences, but would not be able to enforce general 'fairness' constraints. See e.g. this related SO question. Vertex colouring has efficient algorithms for enforcing job separation constraints.
Other posters have mentioned simplex and job shop scheduling. Simplex is an optimisation algorithm - it traverses a solution space seeking to maximise some objective function. Formulating the objective function can certainly be done, but is non-trivial. Classical job shop scheduling, like bipartite matching, can model some aspects of your problem, but not all. There are no precedence constraints, for example. There are extended versions that can handle some constraints, for example placing time bounds on tasks.
If you're interested in existing implementations, the Python networkx library has an implementation of this matching algorithm. An example of an open source timetabling program that might be of interest is Tablix.