问题标签 [integer-programming]

我对 R 相当陌生，我正在尝试为我过去在 Excel 中使用 Solver 所做的事情编写一个脚本。在下面的数据中，我有一个工作类型为 AE 的工人列表。每个工人都有工资和生产率。我想让 R 做的是找到我可以从 10 名累积工资 <100,000 的工人那里获得的最大产量。限制是我总共需要 10 名工人，我需要 2 名来自工作类型 AD、1 名来自 E 和 1 名任何类型。

我已经搜索并搜索了一种使用 optim、IpSolve 等执行此操作的方法，但由于我的知识有限，我运气不佳。

感谢您的帮助！

我的教授给我们的一个问题遇到了麻烦：

一对丈夫和妻子正在旅行，并希望最大限度地利用随身携带某些物品的好处。老公可以带20公斤，老婆可以带17公斤。他们应该带什么？

这是我使用 'lp_solve' linux 命令编写和运行的：

这是我的结果：

我的结果表明，丈夫应该拿火炉和斧头，而妻子应该拿灯和望远镜。这是一个有效的结果，但它不是最有益的......有人可以向我解释我做错了什么吗？

非常感激。

我有一个大的 MIP 问题，我在 GLPK 中使用 GLPSOL 来解决它。然而，解决 LP 松弛问题需要多次迭代，并且每次迭代的 obj 和 infeas 值都相同。我认为它找到了最佳解决方案，但它不会停止并继续运行多个小时。每个大规模 MIP/LP 问题都会发生这种情况吗？我该如何处理这种情况？任何人都可以给我任何建议吗？谢谢！

在我的工作中，我遇到了以下问题：给定一个相似度矩阵 D，其中 $d_{i,j} \in \Re$ 表示对象 $i$ 和 $j$ 之间的相似度，我想选择 $k $ 个对象，对于 $k \in {1, \dots, n}$，以最小化所选对象之间的相似性的方式。我第一次尝试正式制定这个问题是使用以下整数程序：

$\最小化$ $d_{1,2}X_1X_2 + d_{1,3}X_1X_3 + \dots + d_{1,n}X_1X_n + d_{2,1}X_2X_1 + \dots + d_{n,n-1 }X_nX_{n-1} $

使得 $X_1 + X_2 + \dots + X_n = k$ 和 $X_y \in {0,1}$，对于 $y=1,\dots,n$

在上述程序中，$X_y$ 表示对象 $y$ 是否被选中。显然，上述程序不是线性的。我试图通过使用变量 $X_{1,2} $ 使目标函数成为线性的，这表明是否同时选择了对象 $X_1$ 和 $X_2$。但是，我正在努力制定必须选择恰好 $k$ 个对象的约束，即先前的约束 $X_1 + X_2 + \dots + X_n = k$。

由于我不是数学编程方面的专家，我想知道您是否可以帮助我解决这个问题。

先感谢您！一切顺利，

亚瑟

嗨，我想解决具有25000 个二进制变量和几乎2555 个等式约束和50 个不等式约束的线性规划 (LP) 问题，所以我使用了 CPLEX API 为 MATLAB 提供的cplexbilp函数，如下所示：

• 矩阵大小：f=25000x1，Aineq=50x25000，bineq=50x1，Aeq=2555x25000，beq=2255x1

当我运行脚本时，出现此错误：

当我查看错误详细信息时，我看到以下消息：

0x6df51ba9 C:/Program Files/IBM/ILOG/CPLEX_Studio_Preview125/cplex/matlab/x86_win32/cplexlink125.mexw32+00007081 (???+000000)

我认为cplexlink125.mexw32是 MATLAB 的 cplex v12.5 可调用库。
所以，我的问题是如何解决这个错误？我想知道问题大小（25000 个二进制变量）主要错误根源是什么？我在一些资源中读到 Cplex 能够解决大规模 LP 问题。

• MATLAB版本：R2011a
• CPLEX 版本：12.5

提前感谢您的任何评论或回答

我试图使用 cplex for matlab 来解决我的优化问题。但是，在我看来，cplex 只能解决具有二次目标函数和二次约束的纯整数规划问题。好吧，我当然可以使用精细网格来离散化我的连续参数，但这不是我的首选。

我的问题是：

1. 这是真的？还是我很困惑？
2. 如果我的印象是正确的，是否有人知道一些可靠的求解器能够这样做？

是否有任何免费求解器能够解决大数（至少 336 位）的整数规划问题？我看过的所有求解器似乎都只假设双精度，我还没有找到任何声称任意精度的求解器。

我正在尝试解决背包问题，这也是一个整数规划问题。我研究了几种近似解决方案，例如动态规划、贪心算法、分支定界算法、遗传算法。你能告诉我一个有助于实现任何/所有这些算法的库（用任何语言）吗？

提前致谢。

我有一个产品列表和一个功能列表。每个产品都有自己的成本并提供自己的功能子集。

我想要一个算法，这样我可以告诉它我需要哪些功能，它会告诉我需要购买的产品集，以便以最低的总组合成本获得所有这些功能。

有没有人有这样做的秘诀？我想在 JavaScript 中使用它。

什么

我正在尝试为锦标赛制作一组最佳括号（由约束定义的最佳）。

问题

我不知道如何解决这个问题。 这篇论文水平很高，但讨论了用约束规划解决集合分区问题的可能性。它还指出，大多数集合分区问题都是通过整数规划解决的。我主要是在寻找一个可以效仿的例子。这个问题类似于这个SO question。我见过的大多数约束示例都定义了特定的分区总数。是否可以建模一个系统，其中分区将由约束和参与者集动态确定？我会链接示例，但由于我的声誉，我仅限于 2 个。

一个更具体的例子

已知值

• 参加人数为 N。
• 每个参与者都有一个与他们相关的权重 W。

约束

• 一个支架（组）由 2、3、4、6、7 或 8 名参与者组成。
• 每个参与者仅在一个括号中。
• 括号中权重最低的参与者和权重最高的参与者之间的差异不得超过 15%。
• 与所有其他支架尺寸相比，更倾向于创建尺寸为 8 和 4 的支架。

例如，假设有 8 个参与者。

{ {1, W=100}, {2, W=103}, {3, W=105}, {4, W=106}, {5, W=110}, {6, W=114}, { 7, W=120}, {8, W=125} }

一种可能的解决方案是：{1, 2, 3}, {4, 5}, {6, 7, 8}

一个更优化的解决方案是：{1, 2, 3, 4}, {5, 6, 7, 8}，因为与之前的解决方案相比，这有利于 4、8 个大小的集合。

是否可以将一个集合划分为动态数量的子集合？

感谢你的宝贵时间！