问题标签 [linear-programming]

The Test Cover problem can be defined as follows:

Suppose we have a set of n diseases and a set of m tests we can perform to check for symptoms. We also are given the following:

• an nxn matrix A where A[i][j] is a binary value representing the result of running the jth test on a patient with the the ith disease (1 indicates a positive result, 0 indicates negative);
• the cost of running test j, c_j; and that
• any patient will have exactly one disease

The task is to find a set of tests that can uniquely identify each of the the n diseases at minimal cost.

This problem can be formulated as an Integer Linear Program, where we want to minimize the objective function \sum_{j=1}^{m} c_j x_j, where x_j = 1 if we choose to include test j in our set, and 0 otherwise.

My question is:

What is the set of linear constraints for this problem?

Incidentally, I believe this problem is NP-hard (as is Integer Linear Programming in general).

我正在开发一款游戏，我需要找到特定句子的最大权重。

假设我有句子“the quick brown fox”，并假设单个词和双词都具有定义的权重：“the”-> 10、“quick”-> 5、“brown”-> 3、“fox”-> 8 , “快速” -> 5, “快速棕色” -> 10, “棕色狐狸” -> 1

我想知道单字和双字的哪个组合提供了最大的权重，在这种情况下，它将是“the”、“quick brown”、“fox”（权重 = 28）

有人告诉我这个问题可以通过线性规划来解决，但我看不到如何实现这种方法。具体来说，我不知道如何表达问题的约束，在这种情况下，一些双词不能与包含的单个词组合（即“快速”不能与任何一个组合） "the" 或 "quick")

有人可以就如何解决这个问题提供一些指导吗？我不是该领域的专家，并且对 Simplex 的工作原理有一些基本的了解（从学校回来），但我缺乏关于如何为此类问题建模的知识。

此外，任何其他方法（不涉及线性编程或蛮力）也将受到欢迎。

谢谢。

我正在尝试使用“读取”命令将 CPLEX LP 文件加载到 CPLEX。我相信在这个问题中，我有一组二次约束。但是，据我了解，CPLEX 仍将尝试解决二次规划问题。

但是，当我尝试将其读入时，出现此错误：

在阅读二次规划问题时，我需要做些什么特别的事情吗？

注意：我可以将此 LP 文件加载到 scip 并使用以下方法解决它：scip -f

我正在使用 CPLEX Java API 解决大型优化问题。目前我只是

这很好用，但我经常重复这个过程，我只是在改变系数。每次重复时，我都会创建一个新cplex对象并重新创建所有变量。

有没有更有效的方法来做到这一点？IBM 文档中有“将模型添加到模型实例”之类的语言，这听起来很奇怪，但我认为它暗示了能够重用事物。

来自更有经验的用户的任何建议都会很棒。谢谢。

我的部分问题是最小化某些数字的加权和的绝对值。我必须找到重量。

假设我有一组数字 A、a1、a2、a3 和 a4，这样 (a1, a2 > 0), (a3, a4 < 0)

例如，最小重量为 0.1 (10%)，最大重量为 0.4 (40%)。我正在寻找权重w以使加权和为零；如果不可能为零，则最接近于零。可以使用一个简单的线性模型来实现这一点：

一个简单的线性程序足以快速找到解决方案。但是，我非常想为这个问题找到一个多项式算法或公式。有任何想法吗？这个问题众所周知吗？

谢谢！

我有一个复杂的问题，我想知道是否存在或适用现有且易于理解的解决方案模型，例如旅行推销员问题。

输入：

• 包含 N 个时间事件的日历，由开始和结束时间以及地点定义。
• 每个会议场所的容量（可同时容纳的最大人数）
• 一组对(Ai,Aj)，表示服务员Ai希望与服务员会面Aj并Aj接受该邀请。

输出：

• 对于每个助理A，他将参加的所有活动的时间表。主要标准是每个服务员应尽可能多地遇到接受他邀请的服务员，满足空间限制。

到目前为止，我们考虑使用回溯求解（尝试所有可能的解决方案），并使用线性规划（即定义模型并使用单纯形算法求解）

更新：如果在某些情况下Ai已经见过面Aj，他们就不需要再见面了（他们已经见过面了）。

我使用 cplex Java API。

使用以下代码：

所以我只使用两个布尔向量 x 和 y。此代码段适用于 inst.getSize() 为例如 25 的较小实例。但是，对于大小为 40 的实例，它在最后一行崩溃。

你有什么想法吗？我需要让它工作...

我正在使用 cplex 用 C++ 编写程序。我能够从一个文件中读取信息，这样我就可以创建一个包含百分比的矩阵和两个包含卖价和买价的数组。：

此外，我创建了两个最终应该优化的数组。

这是创建目标的正确方法吗？

我有一个用MathProg编写的线性程序。我未知的二进制变量是一个二维数组，定义为：

其中 V 和 L 是整数集。

然而，一些变量的值是预先知道的，我想为求解器指定它以减小 ILP 的大小。例如，我知道当 l=2 时 x[4,l] 为 1 并且对于 l 的任何其他值为零。目前，我将其指定为约束：

我想知道这是否是提前指定未知子集值的有效方法。

理想情况下，我想将此类信息与数据部分一起放在单独的文件中，而不是放在模型文件中。

我正在尝试为给定的 H 生成以下方程的所有解。

随着 H=4 ：

对于我的问题，总是有 4 个方程需要求解（独立于其他方程）。总共有 2^(H-1) 个解。对于上一个，以下是解决方案：

这是解决问题的R算法。

但是，该算法进行的计算超出了需要。我相信有可能走得更快。我的意思是不生成总和为 > H 的排列

对于给定的 H 有更好的算法的想法吗？