Apache common SimplexSolver ObjectiveFunzione per massimizzare la somma di valori in una matrice

Question

Sto cercando di risolvere il seguente problema lineare utilizzando il risolutore Simplex da apache-commons: org.apache.commons.math3.optim.linear.SimplexSolver.

n è il numero di righe
m è il numero di colonne
L è un limite globale per il valore della somma di ogni riga

Questo è quello che ho finora:

List<LinearConstraint> constraints = new ArrayList<>(); 

double[][] A = calculateAValues(); 
// m = count of columns 
// constraint 1: the sum of values in all column must be <= 1 
for(int i = 0; i < m; i++) { 
    double[] v = new double[n]; 
    for(int j=0; j < n; j++) { 
     v[j] = 1; 
    } 
    constraints.add(new LinearConstraint(v, Relationship.LEQ, 1)); 
} 
// n = count of rows 
// constraint 2: sum of a_i,j in all row must be <= L (Limit) 
for(int i = 0; i < n; i++) { 
    double[] v = new double[m]; 
    for(int j=0; j < m; j++) { 
     v[j] = A[i][j]; 
    } 
    constraints.add(new LinearConstraint(v, Relationship.LEQ, L)); 
} 

double[] objectiveCoefficients = new double[n * m]; 
for(int i = 0; i < n * m; ++i) { 
    objectiveCoefficients[i] = 1; 
} 

LinearObjectiveFunction objective = new LinearObjectiveFunction(objectiveCoefficients, 0); 
LinearConstraintSet constraintSet = new LinearConstraintSet(constraints); 

SimplexSolver solver = new SimplexSolver(); 
PointValuePair solution = solver.optimize(objective, constraintSet, GoalType.MAXIMIZE); 
return solution.getValue(); 

Ho difficoltà a ottenere correttamente la funzione obiettivo, e potrebbe anche mancare qualche altra cosa. Ogni mio tentativo finora ha portato a UnboundedSolutionException.

Answer 1

L'errore sembra essere nelle matrici dei coefficienti dei vincoli lineari.

Si dispone delle variabili n*m pertanto le matrici dei coefficienti per i vincoli e le funzioni obiettivo devono avere lunghezza n*m. Sfortunatamente lo SimplexSolver espande silenziosamente la matrice dei vincoli se sono più corti dell'array della funzione obiettivo. Quindi il tuo codice non ha specificato i vincoli corretti che portano a una soluzione illimitata.

Constraint 1: la somma dei valori in tutto colonna deve essere < = 1

for(int j=0; j<m; j++) 
{ 
    double[] v = new double[n*m]; 
    for(int i=0; i<n; i++) 
     v[i*n + j] = 1; 
    constraints.add(new LinearConstraint(v, Relationship.LEQ, 1)); 
} 

Constraint 2: somma di a_i, j in ciascuno riga deve essere < = L (Limit)

// n = count of rows 
for(int i=0; i<n; i++) 
{ 
    double[] v = new double[n*m]; 
    for(int j=0; j<m; j++) 
     v[i*n + j] = A[i][j]; 
    constraints.add(new LinearConstraint(v, Relationship.LEQ, L)); 
} 

coffecifients Obiettivo:

double[] objectiveCoefficients = new double[n * m]; 
Arrays.fill(objectiveCoefficients, 1.0); 
LinearObjectiveFunction objective = LinearObjectiveFunction(objectiveCoefficients, 0); 

Il vincolo x_ij <= 1 è già soddisfatta a causa di vincolo 2. Forse rende le cose più chiaro anche per specificare esplicitamente un vincolo per 0 <= x_ij utilizzando un NonNegativeConstraint:

SimplexSolver solver = new SimplexSolver(); 
PointValuePair solution = solver.optimize(objective, constraintSet, 
    GoalType.MAXIMIZE, new NonNegativeConstraint(true));