logo标签列表

如何解决一个不等式系统？

algorithmsystemsolverlinear-programminginequality
4
我已将我的问题（表格布局算法）简化为以下问题：
假设我有N个变量X1，X2，...，XN。 我还有一些（未确定数量的）不等式，如：
X1 >= 2
X2 + X3 >= 13
等等。
每个不等式都是一个或多个变量的总和，并且始终使用“>=”运算符与常数进行比较。我无法提前确定每次将有多少个不等式，但所有变量都必须为非负数，因此每个变量已经有一个。
如何解决这个系统，使得变量的值尽可能小？
补充：阅读了维基百科文章并意识到我忘记了提到变量必须是整数。猜测这会使它成为NP-hard问题，对吧？
仅仅因为整数（线性）规划的一般问题是NP难的，并不意味着你不能获得“足够好”的结果。传统人工智能多年来一直在尝试并经常成功地解决这些类型的问题，尽管无法保证您的特定情况可解。查看《人工智能：现代方法：第5章：约束满足问题》（http://aima.cs.berkeley.edu/newchap05.pdf）。它可能会有所帮助。 - bitsplit
4个回答
7

线性规划是指在满足线性约束条件下，最小化x1 + x2 + ...的问题。在维基百科中有详细介绍。

6
您所面对的是一个相当基础的线性规划问题。您希望在以下条件下最大化方程式X_1 + ... + X_n：线性规划。
X_1 >= 2
X_2 + X_3 >= 13
etc.

有许多算法可以解决这种类型的问题。最著名的是单纯形算法，它可以在平均情况下相当高效地解决您的方程（带有某些警告），尽管存在LP问题，对于这些问题，单纯形算法需要指数级的步骤才能解决（在问题规模上）。

存在各种LP求解器的实现。例如LP_Solve应该满足您的大部分需求。

2

您还可以直接将线性模型发布到NEOS平台(http://neos.mcs.anl.gov/neos/solvers/index.html)。您只需首先使用诸如AMPL之类的代数语言编写模型，然后NEOS将解决该模型并通过电子邮件返回结果。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接