生成满足线性约束的随机点

Question

在我的问题中，我有一个len N的向量x。其中每个元素x_I，j是产品I在国家j的价格。假设我有100个产品和20个国家，所以N=100x20=2000。

X的解受到一组线性约束。例如，每个产品的最低/最高价格以及国家之间相同产品允许的最大差异。因此，我可以将约束定义为矩阵Ax<b

我想这个问题就像是从一个由约束定义的超平面限定的空间中采样点。

假设问题有多个可行的解决方案。如何生成满足约束的随机点(向量x的解(？或者有什么图书馆可以帮我？

我试过了https://github.com/python-constraint/python-constraint，但似乎因为解的数量非常多，算法在某个点上陷入停滞或需要很长时间才能返回解。

Answer 1

也许我遗漏了什么，或者您过于简化了实际用例。但对于上述情况，没有必要进行约束编程：

• 每个产品都有min_price、max_price和max_diff(我假设为max_diff <= max_price - min_price(
• 因此，您可以设置的实际最低价格将在min_price和max_price - max_diff之间。假设你在这个范围内随机设置
• 因此，实际最高价格为actual_min + max_diff
• 现在，每个国家的产品价格将只是介于actual_min和actual_max之间的一个值

我在一个三步过程中实现了这一点：为产品创建(随机(数据(您将跳过这一步(；计算实际的最小/最大值；并最终分配每个产品/国家的价格。在我的旧i5 windows笔记本电脑上，每秒大约有1300个解决方案，适用于100种产品和20个国家，它甚至没有预期的那么慢

from dataclasses import dataclass
from random import choices, randint
@dataclass
class Product:
min_price : int
max_price : int
max_diff : int
actual_min : int = 0
actual_max : int = 0
class Prices():
def __init__(self, no_products, no_countries):
self.products = {}
for i in range(no_products):
min_price = randint(100,200)
max_price = min_price + randint(200,300)
max_diff = randint(10,max_price - min_price)
self.products[i] = Product(min_price, max_price, max_diff)
self.countries = [c for c in range(no_countries)]
self.prices = []
def calc_actuals(self):
for p in self.products.values():
p.actual_min = randint(p.min_price, p.max_price - p.max_diff)
p.actual_max = p.actual_min + p.max_diff
def calc_prices(self):
self.prices = []
for p in self.products.values():
self.prices.append([*choices(range(p.actual_min, p.actual_max+1),k=len(self.countries))])