Java 库，用于查找具有奇异矩阵的线性代数系统的参数解

Question

我想在Java中解决这个整数线性代数问题，其中xi，yi，zi是整数变量（所有正数，xi≥0，yi≥0，zi≥0），a，b，c，d，e，f，g，h是常数（正整数≥0，例如a=20，b=12，c=28，d=24，e=19，f=5，g=6，h=6）。

x1+x2+x3+x4+x5 = a
y1+y2+y3+y4+y5 = b
z1+z2+z3+z4+z5 = c
x1+y1+z1 = d
x2+y2+z2 = e
x3+y3+z3 = f
x4+y4+z4 = g
x5+y5+z5 = h

It could be viewed as:
 - sum constraint on the rows
 - sum constraint on the columns
 | x1 | x2 | x3 | x4 | x5 | → sum equal to a
 | y1 | y2 | y3 | y4 | y5 | → sum equal to b
 | z1 | z2 | z3 | z4 | z5 | → sum equal to c
   ↓    ↓    ↓    ↓    ↓
   d    e    f    g    h

显然，这个问题有整数解（但不是无限的）。如果可能的话，我想轻松地收集一堆这些整数解决方案，从集合中随机弹出一个。

提前感谢！

---

已解决（它找到一个解决方案）：

感谢阿佩特！我使用ojalgo找到了这个问题的解决方案。这是我的代码：

import org.ojalgo.OjAlgoUtils;
import org.ojalgo.netio.BasicLogger;
import org.ojalgo.optimisation.Expression;
import org.ojalgo.optimisation.ExpressionsBasedModel;
import org.ojalgo.optimisation.Optimisation;
import org.ojalgo.optimisation.Variable;
/**
 * @author madx
 */
public abstract class ojAlgoTest {
    static int[] row_constraints = new int[]{20,12,28};
    static int[] col_constraints = new int[]{24,19,5,6,6};
    public static void main(final String[] args) {
        BasicLogger.debug();
        BasicLogger.debug(ojAlgoTest.class.getSimpleName());
        BasicLogger.debug(OjAlgoUtils.getTitle());
        BasicLogger.debug(OjAlgoUtils.getDate());
        BasicLogger.debug();
        int rows = row_constraints.length;
        int cols = col_constraints.length;
        // Create variables expressing servings of each of the considered variable
        // Set lower and upper limits on the number of servings as well as the weight (cost of a
        // serving) for each variable.
        final Variable matrix[][] = new Variable[rows][cols];
        for(int i=0; i<rows;i++){
            for(int j=0;j<cols;j++){
                matrix[i][j] = Variable.make("Matrix" + i + "_" + j).lower(0).upper(24).weight(1);
            }
        }
        // Create a model and add the variables to it.
        final ExpressionsBasedModel tmpModel = new ExpressionsBasedModel();
        for(int i=0; i<rows;i++){
            for(int j=0;j<cols;j++){
                tmpModel.addVariable(matrix[i][j]);
            }
        }
        // Create contraints
        for(int i=0; i<cols;i++){
            final Expression cat = tmpModel.addExpression("Col_Constraint_"+i).lower(col_constraints[i]).upper(col_constraints[i]);
            for(int j=0; j<rows;j++){
                cat.setLinearFactor(matrix[j][i], 1);
            }
        }
        for(int j=0; j<rows;j++){
            final Expression cat = tmpModel.addExpression("Row_Constraint_"+j).lower(row_constraints[j]).upper(row_constraints[j]);
            for(int i=0; i<cols;i++){
                cat.setLinearFactor(matrix[j][i], 1);
            }
        }
        // Solve the problem - minimise the cost
        Optimisation.Result tmpResult = tmpModel.minimise();
        // Print the result
        BasicLogger.debug();
        BasicLogger.debug(tmpResult);
        BasicLogger.debug();
        // Modify the model to require an integer valued solution.
        BasicLogger.debug("Adding integer constraints...");
        for(int i=0; i<rows;i++){
            for(int j=0;j<cols;j++){
                matrix[i][j].integer(true);
            }
        }
        // Solve again
        tmpResult = tmpModel.minimise();
        // Print the result, and the model
        BasicLogger.debug();
        BasicLogger.debug(tmpResult);
        BasicLogger.debug();
        BasicLogger.debug(tmpModel);
        BasicLogger.debug();
    }
}

Answer 1

这不能表述为网络流问题吗？（从列约束到行约束的流，带有额外的行/列来处理差异）如果为真，则可以使用网络单纯形算法生成整数解（所有问题参数都必须是整数）。

如果我错了，它绝对可以表述为一般的MIP问题。有许多免费和商业软件包可以帮助解决这些问题。一个开源的纯Java替代方案（我写的）是ojAlgo。

下面是如何使用 ojAlgo 对优化问题进行建模的示例。