Библиотека 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.