在 R 中使用 lpSolveAPI 的所有可行解决方案

Question

我正在尝试找出包装物品的所有可能组合。基本上这是一个整数规划问题，你有 i 个项目，j 个框和二进制变量 x[i,j]。

约束有很多，但我先建了一个简单的问题，有一个体积约束，就是分配给j盒的物品体积之和不能超过j盒的体积。

我需要此约束的所有可行解决方案。我将 AMPL 与 cplex 一起使用，但没有找到所有可行点的 cplex 选项。

我想知道是否有可能通过使用 R 的 lpSolveAPI 包获得所有可行的解决方案。为了更好地理解，我在下面附上了我的 AMPL 代码。谢谢。

set items;
set containers;

param items_vol {i in items};
param containers_vol {j in containers};

var x{i in items, j in containers} binary;
var y{j in containers} binary;

minimize containers_volume: sum{i in items, j in containers} 
containers_vol[j] * x[i,j];

subject to volumes {j in containers}:
sum {i in items} x[i,j] * items_vol[i] <= containers_vol[j];

subject to usage {i in items}:
sum {j in containers} x[i,j] = 1;

subject to usage2 {j in containers}:
y[j] - sum{i in items} x[i,j]  <= 1

Answer 1

有两种不同的方法可以枚举所有可行的整数解。

第一个是对禁止先前找到的解决方案的约束添加切割。即

 1. solve problem
 2. if infeasible: done
 3. record optimal solution x[i] into a[i]
 4. add cut of the form
      sum(i, (2*a[i]-1)*x[i]) <= sum(i,a[i])-1
 5. go to step 1.

我这里假设二元变量是x[i]。

第二种方法是使用 Cplex 解决方案池。如果有很多解决方案，这会快得多。

PS：LpSolveApi 记录 get.solutioncount 和 select.solution 之类的内容。我认为这实际上行不通。

在 R 中使用 lpSolveAPI 的所有可行解决方案

All feasible solutions using lpSolveAPI in R

r

linear-programming

lpsolve