用于查找具有奇异矩阵的线性代数系统的参数解的 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 问题。有许多免费和商业软件包可以帮助解决这个问题。 ojAlgo 是一种开源纯 Java 替代方案(我编写的)。

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