对于这个问题，区域是Z d的子集，由具有整数系数的有限多个线性不等式定义，其中Z d是整数的 d 元组的集合。例如，(x, y)非负整数对的集合2x+3y >= 10构成一个区域d=2（非负性只是强加了额外的不等式x>=0和y>=0）。
问题：有没有一种好方法，使用整数编程（或其他东西？）来检查一个区域是否包含在有限多个其他区域的联合中？
我知道一种检查收容的方法，我将在下面描述，但我希望有人能够提供一些改进，因为它不是太有效。
这是我知道的检查收容措施的方法。首先，整数编程库可以直接检查区域是否为空：在整数编程术语中（据我理解），区域的空性对应于模型的不可行性。我使用 gurobi 库编写了一些代码来检查空虚，它在实践中似乎对我关心的那种区域运行良好。
现在假设我们要检查一个区域X是否包含在另一个区域中Y（问题的一个特例）。让Z是X与 的补码的交集Y。thenX包含在Y当且仅当Z为空时。现在，Z它本身不是我所说的区域，而是区域的联合Z_1, ..., Z_n，其中n是用于定义的不等式的数量Y。我们可以Z通过检查 each 是否为空来检查是否Z_1, ..., Z_n为空，我们可以如上所述进行。
一般情况可以用完全相同的方式处理：如果Y是区域的有限联合，Y_1, ..., Y_k那么Z仍然是区域的有限联合Z_1, ..., Z_n，因此我们只需检查每个区域Z_i是否为空。IfY_i由m_i不等式定义 then n = m_1 * m_2 * ... * m_k。
所以总而言之，我们可以将包含问题简化为空性问题，图书馆可以直接解决这个问题。问题是我们可能必须解决非常大量的空性问题来解决包含问题（例如，如果每个Y_i不等式仅由两个不等式定义，则n = 2^k随着 指数增长k），因此这可能需要很多时间。