java - Apache common SimplexSolver ObjectiveFunction 用于最大化矩阵中值的总和

Question

我正在尝试使用 apache-commons 中的 Simplex 求解器来解决以下线性问题:org.apache.commons.math3.optim.linear.SimplexSolver。

n 是行数
m 是列数
L 是每行总和值的全局限制

这是我目前所拥有的:

List<LinearConstraint> constraints = new ArrayList<>();

double[][] A = calculateAValues();
// m = count of columns
// constraint 1: the sum of values in all column must be <= 1
for(int i = 0; i < m; i++) {
    double[] v = new double[n];
    for(int j=0; j < n; j++) {
        v[j] = 1;
    }
    constraints.add(new LinearConstraint(v, Relationship.LEQ, 1));
}
// n = count of rows
// constraint 2: sum of a_i,j in all row must be <= L (Limit)
for(int i = 0; i < n; i++) {
    double[] v = new double[m];
    for(int j=0; j < m; j++) {
        v[j] =  A[i][j];
    }
    constraints.add(new LinearConstraint(v, Relationship.LEQ, L));
}

double[] objectiveCoefficients = new double[n * m];
for(int i = 0; i < n * m; ++i) {
    objectiveCoefficients[i] = 1;
}

LinearObjectiveFunction objective = new LinearObjectiveFunction(objectiveCoefficients, 0);
LinearConstraintSet constraintSet = new LinearConstraintSet(constraints);

SimplexSolver solver = new SimplexSolver();
PointValuePair solution = solver.optimize(objective, constraintSet, GoalType.MAXIMIZE);
return solution.getValue();

我无法正确设置目标函数，而且可能还缺少其他一些东西。到目前为止，我的每一次尝试都导致了 UnboundedSolutionException。

Answer 1

错误似乎在线性约束的系数数组中。

你有 n*m变量，因此约束和目标函数的系数数组的长度必须为 n*m .不幸的是 SimplexSolver如果约束数组比目标函数的数组短，则静默扩展约束数组。因此，您的代码没有指定导致无限解决方案的正确约束。

约束1:所有列的值之和必须<= 1

for(int j=0; j<m; j++)
{
    double[] v = new double[n*m];
    for(int i=0; i<n; i++)
        v[i*n + j] = 1;
    constraints.add(new LinearConstraint(v, Relationship.LEQ, 1));
}

约束2:所有行的a_i,j之和必须<= L (Limit)

// n = count of rows
for(int i=0; i<n; i++)
{
    double[] v = new double[n*m];
    for(int j=0; j<m; j++)
        v[i*n + j] = A[i][j];
    constraints.add(new LinearConstraint(v, Relationship.LEQ, L));
}

目标系数:

double[] objectiveCoefficients = new double[n * m];
Arrays.fill(objectiveCoefficients, 1.0);
LinearObjectiveFunction objective = LinearObjectiveFunction(objectiveCoefficients, 0);

约束x_ij <= 1由于约束 2 已经满足。也许还为 0 <= x_ij 显式指定约束会使事情变得更清楚使用 NonNegativeConstraint :

SimplexSolver solver = new SimplexSolver();
PointValuePair solution = solver.optimize(objective, constraintSet,
     GoalType.MAXIMIZE, new NonNegativeConstraint(true));