标签: linear-programming

我正在开发一种应用程序,可以最佳地为医院的护士分配班次.我认为这是一个带离散变量的线性规划问题,因此可能是NP难的:

• 对于每一天,每位护士(约15-20岁)都会被分配轮班
• 有少量(约6个)不同的班次
• 有相当多的约束和优化标准,无论是关于一天,还是关于一个emplyoee,例如:
  • 每天必须为每个轮班分配最少数量的人员
  • 有些班次重叠,所以如果有人做中间班,可以让一个人在早班换一个人
  • 有些人更喜欢提前班次,有些人更喜欢延迟班次,但需要最少的换班才能获得更高的轮班工资.
  • 不允许一个人一天工作到第二天工作到第二天早班(由于最短的休息时间规定)
  • 满足指定的工作周长度(不同的人不同)
  • ...

因此,基本上存在大量(约20*30 = 600)变量,每个变量可以采用少量离散值.

目前,我的计划是使用修改后的Min-conflicts算法

• 从随机分配开始
• 每个人和每一天都有健身功能
• 选择具有最差健身值的人或日
• 随机选择该日/人的任务之一并将其设置为导致最佳适合度值的值
• 重复直到达到最大迭代次数或者找不到所选日期/人的改进

有更好的想法吗？我有点担心它会陷入局部最佳状态.我应该使用某种形式的模拟退火吗？或者不仅考虑一次改变一个变量,而且特别考虑两个人之间的转换(当前手动算法中的主要部分)？我想避免将算法定制到当前约束,因为那些可能会改变.

编辑:没有必要找到严格的最佳解决方案; 名单目前是手工完成的,我很确定结果在大多数时候都是非常不理想的 - 不应该难以击败.短期调整和手动覆盖也一定是必要的,但我不认为这是一个问题; 将过去和手动分配标记为"已修复"实际上应该通过减少解决方案空间来简化任务.

有谁知道这样一个执行数学优化的库(线性编程,凸优化或更一般类型的问题)？我正在寻找像MATLAB这样的东西,但能够处理更大的问题.我是否必须编写自己的实现,或者购买其中一种商业产品(CPLEX等)？

我有一个Python脚本,我需要解决线性编程问题.问题是解决方案必须是二进制的.换句话说,我需要一个等效的MATLAB的bintprog函数.NumPy和SciPy似乎没有这样的程序.有没有人建议我如何做这三件事之一:

• 找一个包含这样一个函数的Python库.

• 限制问题,使其可以通过更通用的线性编程求解器来解决.

• 使用MATLAB与Python接口,以便直接使用bintprog.

当代码等待延迟时间不确定的某种情况时,看起来很多人选择使用指数退避,即等待N秒,检查条件是否满足; 如果没有,等待2N秒,检查条件等.这对于检查恒定/线性增加的时间跨度有什么好处？

我正在尝试为幻想自行车比赛计算最佳团队。我有一个csv文件，其中包含176个自行车手，他们的球队，所获得的积分以及将其放入我的球队的价格。我试图找到得分最高的16个自行车队。

适用于任何团队组成的规则是：

• 团队的总费用不能超过100。
• 同一支队伍中的幻想自行车参赛者不得超过4名。

我的csv文件的简短摘录可以在下面找到。

THOMAS Geraint,Team INEOS,142,13
SAGAN Peter,BORA - hansgrohe,522,11.5
GROENEWEGEN Dylan,Team Jumbo-Visma,205,11
FUGLSANG Jakob,Astana Pro Team,46,10
BERNAL Egan,Team INEOS,110,10
BARDET Romain,AG2R La Mondiale,21,9.5
QUINTANA Nairo,Movistar Team,58,9.5
YATES Adam,Mitchelton-Scott,40,9.5
VIVIANI Elia,Deceuninck - Quick Step,273,9.5
YATES Simon,Mitchelton-Scott,13,9
EWAN Caleb,Lotto Soudal,13,9

解决此问题的最简单方法是生成团队所有可能组合的列表，然后应用规则排除不符合上述规则的团队。此后，很容易计算每个团队的总得分并选择得分最高的团队。从理论上讲，可以通过以下代码生成可用团队列表。

database_csv = pd.read_csv('renner_db_example.csv')
renners = database_csv.to_dict(orient='records')

budget = 100
max_same_team = 4
team_total = 16

combos = itertools.combinations(renners,team_total)
usable_combos = []

for i in combos:
    if sum(persoon["Waarde"] for persoon in i)  < budget and all(z <= max_same_team for …

我找到了一些解决方案,但它们太乱了.

我正在为 ZenUML 设计一个布局引擎。一项要求（简化后）是这样的：

1. 有一条线段；
2. 这条线段上有n个（n < 100，如果影响性能的话可以减少到n < 30）个点，顺序是固定的；(例如P1 ~ Pn)
3. 某些点之间存在已知的最小距离；（例如m_d（P2，P4）= 500）
4. 线段的长度应尽可能小；
5. （很好）相邻点之间的间隙应尽可能均匀（通过标准差^来衡量，并且不得违反1~4）。
6. （新增）在最坏的情况下（或多或少的限制），它必须在不超过 1 秒的时间内给出 30 分的结果。

^standard deviation被用作我可以用我有限的数学知识精确描述的最佳替代方案。然而，正如 Roman 和 David 指出的，在某些情况下，有更有吸引力的结果不能满足最低要求standard deviation。看到这个评论

有姐妹提问https://math.stackexchange.com/q/4377433。这与用数学语言（矩阵）描述的问题相同。

例如，对于有 4 个点（P1 ~ P4）的线段。

m_d（P1，P3）= 200，m_d（P1，P4）= 900。

• A。一种解决方案是 P1 = 0、P2 = 0、P3 = 200、P4 = 900。
• b. 更好的解决方案是 P1 = 0、P2 = 100、P3 = 200、P4 = 900。（将 P3 放在中间）
• C。更好的解决方案是 P1 = 0、P2 = 300、P3 = 600、P4 = 900。（均匀分配 P2 和 P3）。 …

我需要单纯形算法的强大C++源代码(是一种用于线性规划问题的数值解法的流行算法).

请不要链接到维基百科.我需要C++中的良好源代码,使用模板,清晰的用户友好名称,并且工作得很好.

优选地,算法必须检查不稳定的浮点计算.

经过数年和多年的Matlab,我仍然是Python的新手.我正在尝试使用Pulp来设置整数线性程序.

鉴于一系列数字:

{P[i]:i=1...N}

我想最大化:

sum( x_i P_i )

受限制

A x <= b
A_eq x = b_eq

和边界(基于矢量的边界)

LB <= x <= UB

然而,在纸浆中,我没有看到如何正确地进行矢量声明.我用的是:

RANGE = range(numpy.size(P))
x = pulp.LpVariable.dicts("x", LB_ind, UB_ind, "Integer")

我只能输入个别边界(所以只有1个数字).

prob = pulp.LpProblem("Test", pulp.LpMaximize)
prob += pulp.lpSum([Prices[i]*Dispatch[i] for i in RANGE])

对于约束,我真的必须每行做这行吗？似乎我错过了一些东西.我将不胜感激.文档讨论了一个简短的例子.在我的情况下,变量的数量是几千.

二次编程库是否有任何Haskell绑定？

如果没有,我应该编写哪一个简化的绑定来假设我无法避免需要一个？是否有一个合理的规范优惠的开源库？