问题标签 [linear-programming]

我是整数线性规划的新手。我计划使用整数线性规划求解器来解决我的组合优化问题。我更熟悉 IDE 上的 C++/面向对象编程。现在我大部分时间都在使用带有 Cygwin 的 NetBeans 来编写我的应用程序。

请问是否有适合我的易于使用的 ILP 求解器？还是取决于我要解决的问题？我正在尝试做一些资源映射优化。如果需要任何进一步的信息，请告诉我。

非常感谢你，卡西。

任何人都可以推荐一个图书馆 - 免费或商业但负担得起（

这里列出了一些： http ://en.wikipedia.org/wiki/Linear_programming#Solvers_and_scripting_.28programming.29_languages

....但我刚开始使用 LP，希望有人可以推荐一些东西。

我试图基本上最小化手机订阅服务的定价。
我想第一个问题是：线性规划甚至适用于解决这个问题吗？

一个简化的例子：

基本计划选项
计划 A：200 分钟语音、10 条短信、10 MB 数据 = 25 美元
计划 B：400 分钟语音、25 条短信、25 MB 数据 = 40 美元
计划 C：1000 分钟语音、50 条短信、50 MB 数据 = 65 美元
...
F 计划：2500 分钟语音、150 条短信、150 MB 数据 = 95 美元

超出计划的费用（适用于所有情况）：
每分钟语音 0.10 美元
每条短信 0.20
美元 每 MB 数据 1.50 美元

可选附加套餐（添加到基本计划中）：
免费周末 $15
免费晚上和周末（晚上 8 点之后） $20
免费晚上和周末（下午 6 点之后） $35 短信套餐 #1（50 条短信） $5
短信套餐 #2（ 150 条短信）10 美元
数据包#1（20 MB 数据）20 美元
数据包#2（50 MB 数据）30美元健谈用户混合
包#1（100 分钟语音，100 条短信）15 美元
极客用户混合包#1（50 分钟）语音、150 MB 数据）35 美元
等

我有一组 50 个用户的详细使用数据，并且想弄清楚每个人应该使用的基本计划（A、B、C ... F）的组合，以及哪些附加包他们应该有。

这是我的第一个问题，所以请宽容。

我在 prolog/CLP 中编写逻辑问题：

“众所周知，只有一个角色在说真话。April
先生说 May 先生说谎。May
先生说 June 先生说谎。June
先生说 April 先生和 May 先生都说谎。
编写一个程序来确定谁在说谎。真相。”

我在纸上解决问题，解决方案是梅先生说实话。

但是如何在prolog中编写呢？我可能找到了类似的解决方案：WHO KILL - Similar solution

但我不明白。有人可以知道如何做到这一点或有另一个例子吗？

如果可以的话请帮忙:):):)

这个很棒的 SO 答案指向了一个很好的稀疏求解器Ax=b，但是我有这样的限制，即x每个元素x都是.>=0<=N

此外，A它很大（大约 2e6x2e6），但<=4每行元素非常稀疏。

有什么想法/建议吗？我正在寻找类似 MATLABlsqlin但具有巨大稀疏矩阵的东西。

我本质上是在尝试解决稀疏矩阵上的大规模有界变量最小二乘问题：

编辑： 在CVX中：

我正在研究背包问题。所以我不明白这里的一件事。

利润/伪资源消耗比

U _j = P _j / W _j其中 W _j = R _ji * A _j

我希望你们知道这个等式，因此我认为不需要更多解释。
我想在这里计算 Aj。那个LP松弛是什么。他们如何使用总容量和重量（物品大小）进行计算。如果我有 n 个项目和 m 个容量，这意味着我应该有 m 个 LP 松弛变量。这样对吗 ？

有人说像

获得相当好的乘数的最简单方法之一是求解线性规划 (LP) 松弛 MKP，其中变量 x _j可以从区间 [0, 1] 中获得任意值，并使用对偶变量的值作为代理乘数。换句话说，a _j被设置为 LP 松弛 MKP 中第 j 个约束的影子价格。

他们如何计算 LP 宽松 MKP 中第 j 个约束的影子价格。我正在从谷歌搜索一段时间，但没有那么清楚。有谁知道通过简单的方式理解？

感谢您阅读到这里:)

我有一个 Python 脚本，我需要在其中解决线性规划问题。问题是解决方案必须是二进制的。换句话说，我需要一个等效于 MATLAB 的bintprog函数。NumPy 和 SciPy 似乎没有这样的程序。有没有人对我如何做这三件事之一有建议：

• 查找包含此类函数的 Python 库。

• 约束问题，使其可以通过更通用的线性规划求解器来求解。

• 将 Python 与 MATLAB 连接，以便直接使用bintprog。

我阅读了维基百科的文章，但似乎超出了我的理解范围。它说它是为了优化，但它与任何其他优化事物的方法有什么不同呢？

一个向我介绍线性编程的答案，这样我就可以开始深入研究一些初学者不太容易获得的材料，这将是最有帮助的。

我正在寻找 C# 的线性规划求解器。换句话说，我正在寻找一个解决线性编程问题的 C# 库。

我需要一个易于使用的库（这样我可以快速学习如何使用它），但如果它支持某些功能作为自动绝对值转换（这样我就不必自己编写转换程序了）。图书馆应该是免费的（不一定是开源的），这一点很重要。

好的文档对我来说是巨大的优势。性能下降 10%-20% 对我的项目来说并不重要。

感谢您的回答

可能重复：
C# 的良好线性编程库？

是否有任何免费的开源 .Net 线性编程库可用？

我有一些关于 的不等式{x,y}，它们满足以下等式：

请注意，xandy必须是整数。

图形上可以表示如下，蓝色区域是满足上述不等式的区域：

现在的问题是，Matlab 中是否有任何函数可以找到每个可接受的对{x,y}？如果有一种算法可以做这种事情，我也会很高兴听到它。

当然，我们总是可以使用的一种方法是蛮力方法，我们测试每种可能的组合{x,y}以查看是否满足不等式。但这是最后的手段，因为它很耗时。我正在寻找一个聪明的算法来做到这一点，或者在最好的情况下，一个我可以立即使用的现有库。

这些x^2+y^2>=100 and x^2+y^2<=200只是示例；实际上f，并且g可以是任何次数的任何多项式函数。

编辑：也欢迎 C# 代码。