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

Question

我正在尝试使用 apache-commons 中的单纯形求解器来解决以下线性问题：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();

我无法正确使用 objective 函数，而且可能还缺少其他一些东西。到目前为止，我的每一次尝试都得到了 UnboundedSolutionException.

Answer 1

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

您有 n*m 个变量，因此约束的系数数组和 objective 函数的长度必须为 n*m。不幸的是，如果 SimplexSolver 比 objective 函数的数组短，则 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));
}

Objective咖啡机：

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

由于约束 2，约束 x_ij <= 1 已经满足。也许使用 NonNegativeConstraint:

为 0 <= x_ij 显式指定约束会让事情变得更清楚

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

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

Apache common SimplexSolver ObjectiveFunction for maximizing the sum of values in a matrix

java

linear-programming

apache-commons

apache-commons-math