问题标签 [mathematical-optimization]

我正在使用 CPLEX 来解决巨大的优化模型（超过 10 万个变量）现在我想看看我是否可以找到一个开源替代方案，我解决了混合整数问题 (MILP) 并且 CPLEX 效果很好，但是如果我们想要扩展，所以我真的需要找到替代方案或开始编写我们自己的临时优化库（这会很痛苦）

任何建议/见解将不胜感激

我正在寻找一个优化库。我的两个要求是它不使用 JNI，并且它没有许可证限制阻止它在商业上用于多台计算机。我发现满足这些要求的唯一一个是 Choco，但它是无法使用的越野车。

我需要在我的 Java 程序中解决非线性最小化（N 个未知数的最小残差平方）问题。解决这些问题的常用方法是Levenberg-Marquardt算法。我有一些问题

• 有人对可用的不同 LM 实现有经验吗？LM 的风格略有不同，我听说该算法的确切实现对其数值稳定性有重大影响。我的功能表现得非常好，所以这可能不是问题，但我当然想选择一个更好的选择。以下是我发现的一些替代方案：

  • FPL 统计组的非线性优化 Java 包。这包括经典 Fortran MINPACK 例程的 Java 翻译。

  • JLAPACK，另一个 Fortran 翻译。

  • 优化算法工具包。

  • Java 数字。

  • 一些 Python 实现。纯 Python 就可以了，因为它可以用 jythonc 编译成 Java。

• 是否有任何常用的启发式方法来进行 LM 所需的初始猜测？

• 在我的应用程序中，我需要对解决方案设置一些约束，但幸运的是它们很简单：我只要求解决方案（为了成为物理解决方案）是非负的。稍微负的解决方案是数据测量不准确的结果，显然应该为零。我正在考虑使用“常规”LM，但会进行迭代，以便如果某些未知数变为负数，我将其设置为零并从中解决其余的问题。真正的数学家可能会嘲笑我，但你认为这可行吗？

感谢您的任何意见！

更新：这不是火箭科学，要解决的参数数量（N）最多为 5 个，数据集几乎不足以解决问题，所以我相信 Java 足够有效地解决这个问题。而且我相信这个问题已经被聪明的应用数学家解决了无数次，所以我只是在寻找一些现成的解决方案，而不是自己做饭。例如，如果它是纯 Python，Scipy.optimize.minpack.leastsq 可能会很好。

问题：我有两个重叠的 2D 形状，A 和 B，每个形状具有相同数量的像素，但形状不同。形状的某些部分是重叠的，并且每个形状都有一些不重叠的部分。我的目标是将形状 A 中的所有非重叠像素移动到形状 B 中的非重叠像素。由于每个形状中的像素数相同，我应该能够找到 1 对 1 的映射像素。限制是我想找到最小化所有移动像素行进的总距离的映射。

蛮力：解决这个问题的蛮力方法显然是不可能的，因为我必须计算我认为有 n 的所有可能映射的总距离！（其中 n 是一个形状中的非重叠像素的数量）乘以计算映射中每对点的距离的计算，n，总共得到 O(n * n!) 或类似的东西。

回溯：我能想到的唯一“更好”的解决方案是使用回溯，我将在其中跟踪当前的最小值，并且在我评估某个映射时的任何时候，如果我达到或超过该最小值，我继续下一个映射。即使这样也不会比 O(n!) 做得更好。

有没有办法以合理的复杂性解决这个问题？

另请注意，简单地将一个点映射到它的最近匹配邻居的“明显”方法并不总是产生最佳解决方案。

更简单的方法？：作为次要问题，如果不存在可行的解决方案，一种可能性可能是将每个不重叠的部分划分为小区域，并映射这些区域，从而大大减少映射的数量。为了计算两个区域之间的距离，我将使用质心（区域中像素位置的平均值）。但是，这提出了我应该如何进行分区以获得接近最佳答案的问题。

任何想法表示赞赏！

我正在开发一个应用程序，可以优化地为医院的护士分配轮班。我相信这是一个离散变量的线性规划问题，因此可能是 NP-hard：

• 每天，每位护士（约 15-20 名）都被分配一个轮班
• 有少量（约 6 个）不同的班次
• 有相当多的约束和优化标准，无论是与一天有关，还是与员工有关，例如：
  • 每天必须为每个班次分配最少人数
  • 一些班次重叠，因此如果有人在做中间班次，则可以在早期班次少一个人
  • 有些人更喜欢早班，有些人更喜欢晚班，但需要最少的换班才能获得更高的轮班工作工资。
  • 一个人一天不能晚班，第二天早班（由于最低休息时间规定）
  • 会议分配的工作周长度（不同的人不同）
  • ...

所以基本上有大量（大约 20*30 = 600）个变量，每个变量都可以取少量的离散值。

目前，我的计划是使用修改后的最小冲突算法

• 从随机分配开始
• 对每个人和每一天都有一个健身功能
• 选择健身值最差的人或日子
• 为那一天/人随机选择一项任务，并将其设置为产生最佳适应度值的值
• 重复直到达到最大迭代次数或对于选定的日期/人无法找到改进

有更好的想法吗？我有点担心它会陷入局部最优。我应该使用某种形式的模拟退火吗？或者不仅考虑一次只改变一个变量，还特别考虑两个人之间的轮班切换（当前手动算法的主要组成部分）？我想避免根据当前的约束来定制算法，因为这些可能会改变。

编辑：没有必要找到严格的最优解；名册目前是手动完成的，我很确定结果在大多数情况下都不是最理想的——应该不难打败它。短期调整和手动覆盖也肯定是必要的，但我不认为这会是一个问题；将过去和手动分配标记为“固定”实际上应该通过减少解决方案空间来简化任务。

大家。我正在研究一个大学时间表计划项目。主要是我在使用禁忌搜索，但我想问：

在一般搜索中，您可以探索当前状态的所有邻居，然后根据适应度或评估函数获取最佳状态，但是在这样的项目中，生成所有邻居会降低性能，那么有什么方法可以让我绕过这样的问题？例如，我是否可以只为一个州生成孩子，然后在搜索过程中为所有其他州从这一代中受益？

请，如果有人有此类算法方面的专家，请告诉我，因为我在此类问题上一直在努力。

我有一个问题：

我有一个 A 类和一个 B 类，可以通过编程检查它们的实例对象是否在不同数量上彼此相似或不同。例如，它们可能完全匹配，或者完全不同（即使类别不同，它们仍然可以表示相同的信息并且得分相同。）

现在，给定两个集合，一个是 A，一个是 B，将 As 和 B 配对的最佳方式是什么，以使它们最匹配，如果任一集合大于另一个集合或如果某些 As 或 B 完全不同而无法匹配？

我的第一次尝试是创建一个二维数组，其中每个单元格都是匹配的“分数”（0 = 完美，数字越大越差），并在每条路径中递归查找最低累积分数。这行得通，结果很完美，但速度非常慢。

关于更有效算法的任何想法？

如果您想知道，我的 A 类代表一个混音器输入通道，我的 B 代表相同的持久状态（称为场景）。我要解决的问题是如何将场景导入现有混音器，其中场景 (B) 可能与任何现有通道 (A) 略有不同甚至高度不同。如果我可以稍微修改任何一个以匹配，我不想只添加频道 (A)。例如，我可以在 A 中添加一个效果插入，以便与 B 完美匹配，避免添加另一个 A。

麦克风

给定两组三维点，一个源集和一个目标集。每组上的点数是任意的（可能为零）。任务是为每个目标点分配一个或不分配一个源点，以使所有距离的总和最小。如果源点多于目标点，则忽略附加点。

这个问题有一个蛮力的解决方案，但是由于点的数量可能很大，所以不可行。我听说这个问题在具有相同大小的 2D 中很容易，但遗憾的是这里没有给出这些先决条件。

我对近似值和精确解都感兴趣。

编辑：哈哈，是的，我想这听起来确实像家庭作业。事实上，它不是。我正在编写一个程序来接收大量汽车的位置，并且我正在尝试将它们映射到它们各自的停车单元。:)

我有一个以不寻常方式存储的一周范围内的日期数组。

日期以这种数字格式存储：12150

从左到右：

第一个数字代表日期：1 = 星期日，2 = 星期一，3 = 星期二，....，7 = 星期六

接下来的两位数字代表 24 小时制中的小时：00 = 午夜，23 = 晚上 11 点

接下来的两位数字代表分钟：00-59

给定输入日期和开始日期和结束日期，我需要知道输入日期是否在开始日期和结束日期之间。

我现在有一个算法，我认为它100% 有效，但我不确定。

无论如何，我认为可能有更好更简单的方法来做到这一点，我想知道是否有人知道那个算法是什么。

如果不是这样，如果有人可以仔细检查我的工作并验证它确实适用于 100% 的有效案例，那就太酷了。

我现在拥有的是：

我正在寻找一个包来做矩阵数学高达大约 100 x 100 的矩阵。

我至少需要做逆运算、乘法运算和转置运算。我更喜欢更封装的接口而不是更高的性能。