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

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

提前致谢！

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

感谢apete！我使用 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

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

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

Here's an example 关于如何使用 ojAlgo 对优化问题建模。

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

Java library to find parametric solutions to a linear algebra system with singular matrix

java

solution

linear-algebra

solver

singular