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

Question

I would like to solve in Java this integer linear algebra problem, where xi, yi, zi are the integer variables (all positive, xi≥0, yi≥0, zi≥0), and a, b, c, d, e, f, g, h are the constants (positive integers ≥0, for example 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

Obviously there are a moltitude of integer solutions to this problem (but not unlimited). If it is possible I would like to easily collect a bunch of these integer solutions an randomly pop one on these from the collection.

Thanks in advance!

---

Solved (it finds a single solution):

Thanks to apete! I found a solution to this problem using ojalgo. Here is my code:

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

Cannot this be formulated as a network flow problem? (a flow from the column constraints to the row constraints with an extra row/column to handle the difference) If this is true then the network simplex algorithm can be used to produce integer solutions (all problem parameters must be integers).

If I'm wrong, it can definitely be formulated as a general MIP problem. There are many free and commercial software packages that can help solve such. One open source pure Java alternative (that I wrote) is ojAlgo.

Here's an example on how to model optimization problems using ojAlgo.