如何在python中建模此MILP问题?

我有一个要解决的问题,但我不知道该如何建模。在问这里之前,我进行了研究并找到了有帮助的事情,但我无法解决。我下面有问题的例子

所以我有很多项目可以说40,每个项目具有2或3个功能,并且每个功能仅在有3、4、5,...个取决于功能时才有用。

目标正在获取最多10个不同项

不同有用功能

示例(如果a中包含3个或更多不同的项目,则功能a有用;如果b,c中8个或更多不同的项目,其中b或c个以上,则功能b有用)

Items   Features (a,b,c,...)
item1   a,d
item2   a,b
item3   a,e,item4   a,c
item5   b,f
item6   b,d,e
item7   b,d
item8   c,f
item9   c,e
item10  d,f
...     ...

一个示例组合

item1+item2+...+item10 = a(3),b(5) 

a和b有用的功能(c没用,因为有5个,我们需要8个才能使它有用)

我想我想对一个混合整数线性程序进行建模,并使用分支定界求解器对其进行求解。目标是每个项目和每个特征的特征权重数量(?),我曾考虑将其建模为背包问题,但随后我想不出如何应用此功能,例如容量为10,但值和重量呢?对于功能的实用性有最低要求,我需要一些指导或通用算法来解决此问题,如果我有什么要入手的话,我可以进行进一步调查

yzg338 回答:如何在python中建模此MILP问题?

我的方法是:

第1步:开发数学模型

拿一张纸并写下一个数学模型。例如:

数据:

 a(i,f) = 1   if item i has feature f
          0   otherwise
 K(f)   = number of items with feature f needed to be useful
 N      = number of items to select

二进制变量:

 x(i) = 1    if item i is selected
        0    otherwise

 u(f) = 1    if feature f is useful in selection
        0    otherwise

型号:

  maximize sum(f,u(f))
  subject to 
       sum(i,x(i)) = N
       u(f)*K(f) <= sum(i,a(i,f)*x(i))   for all f

第2步:实施

这现在很简单。首先要写下数学模型的目的。

本文链接:https://www.f2er.com/3007852.html

大家都在问