Linear Programming Problem Solver

function LPPsolver(problem) { //step 1: create tableau, tableau = createTwoPhaseTableau(problem); console.log('Tableau:', tableau); console.log('Tableau (stringified):', JSON.stringify(tableau, null, 2)); //step 2: normalise and attempt to solve auxilary problem //step 3: solve new tableau solverResult = solveTwoPhaseSimplexTableau(tableau); console.log('solverResult:', solverResult); console.log('solverResult (stringified):', JSON.stringify(solverResult, null, 2)); //step 4: use result as initial to solve //step 5: convert to format for output return formatSolutionOutput(solverResult, Object.keys(problem.variables)); }; function createTwoPhaseTableau(problem) { const variables = Object.keys(problem.variables); const constraints = Object.keys(problem.constraints); const objective = problem.optimize; const opType = problem.opType; // Count the number of actual constraints (could be up to 2 per constraint if both min and max are specified) let constraintCount = 0; let artCount = 0; // counts min therefore number of artificial variables constraints.forEach(constraint => { if (problem.constraints[constraint].min !== undefined && problem.constraints[constraint].min > 0) { constraintCount++; artCount++; } if (problem.constraints[constraint].max !== undefined) constraintCount++; }); console.log('constraintCount:', constraintCount) const tableau = []; // Objective function row (Phase 2) const objRow = new Array(variables.length + constraintCount + artCount + 1).fill(0); variables.forEach((variable, i) => { objRow[i] = problem.variables[variable][objective] * (opType === 'max' ? -1 : 1); }); tableau.push(objRow); // Artificial objective function row (Phase 1) const artObjRow = new Array(variables.length + constraintCount + artCount + 1).fill(0); for (let i = variables.length + constraintCount; i < variables.length + constraintCount + artCount; i++) { artObjRow[i] = 1; } tableau.push(artObjRow); // Constraint rows let slackIndex = variables.length; let artIndex = variables.length + constraintCount; constraints.forEach(constraint => { const minValue = problem.constraints[constraint].min; const maxValue = problem.constraints[constraint].max; if (minValue !== undefined && minValue > 0) { //LOOK AT THE >0 REQUIREMENT const row = new Array(variables.length + constraintCount + artCount + 1).fill(0); variables.forEach((variable, j) => { row[j] = problem.variables[variable][constraint]; }); row[slackIndex] = -1; // For >= constraints, we subtract the slack variable row[artIndex] = 1; // For >= constraints, we add artificial variable row[row.length - 1] = minValue; // RHS tableau.push(row); tableau[1] = tableau[1].map((value, index) => value - row[index]); //normalise table console.log('row',row) slackIndex++; artIndex++; } if (maxValue !== undefined) { const row = new Array(variables.length + constraintCount + artCount + 1).fill(0); variables.forEach((variable, j) => { row[j] = problem.variables[variable][constraint]; }); row[slackIndex] = 1; // For <= constraints, we add the slack variable row[row.length - 1] = maxValue; // RHS tableau.push(row); slackIndex++; } }); /* Non-negativity constraints for variables for (let i = 0; i < variables.length; i++) { const row = new Array(variables.length + constraintCount + artCount + 1).fill(0); row[i] = 1; row[row.length - 1] = 0; // RHS tableau.push(row); }*/ console.log('look at this one:', JSON.stringify(tableau, null, 2)); return tableau; } function solveTwoPhaseSimplexTableau(tableau) { // Helper function to find the pivot column function findPivotColumn(row) { let mostNegativeIndex = -1; let mostNegativeValue = 0; for (let i = 0; i < row.length - 1; i++) { if (row[i] < mostNegativeValue) { mostNegativeValue = row[i]; mostNegativeIndex = i; } } return mostNegativeIndex; } // Helper function to find the pivot row function findPivotRow(tableau, pivotColumn) { let minRatio = Infinity; let pivotRow = -1; for (let i = 2; i < tableau.length; i++) { if (tableau[i][pivotColumn] > 0) { const ratio = tableau[i][tableau[i].length - 1] / tableau[i][pivotColumn]; if (ratio < minRatio) { minRatio = ratio; pivotRow = i; } } } return pivotRow; } // Helper function to perform a pivot operation function pivot(tableau, pivotRow, pivotColumn) { const pivotValue = tableau[pivotRow][pivotColumn]; for (let i = 0; i < tableau.length; i++) { if (i !== pivotRow) { const factor = tableau[i][pivotColumn] / pivotValue; for (let j = 0; j < tableau[i].length; j++) { tableau[i][j] -= factor * tableau[pivotRow][j]; } } } // Normalize pivot row for (let j = 0; j < tableau[pivotRow].length; j++) { tableau[pivotRow][j] /= pivotValue; } } // Helper function to check if Phase 1 is complete function isPhase1Complete(tableau) { return tableau[1].every(value => value >= 0); } // Helper function to remove artificial variables function removeArtificialVariables(tableau, artCount) { // Remove artificial objective row console.log('pre removeArtificialVariables art Count:', artCount) console.log('pre removeArtificialVariables:', JSON.stringify(tableau, null, 2)); tableau.splice(1, 1); // Remove artificial variable columns (assuming they're the last columns before RHS) for (let i = 0; i < tableau.length; i++) { tableau[i].splice(tableau[i].length - artCount-1, artCount); } console.log('post removeArtificialVariables:', JSON.stringify(tableau, null, 2)); } // Helper function to check if optimal solution is reached function isOptimal(tableau) { return tableau[0].every(value => value >= 0); } function countNegativeOnes(tableau) { let count = 0; // Start from row 2 to skip rows 0 and 1 for (let i = 2; i < tableau.length; i++) { for (let j = 0; j < tableau[i].length - 1; j++) { if (tableau[i][j] === -1) { count++; } } } return count; } const artCount = countNegativeOnes(tableau); console.log("Number of artificial variables:", artCount); // Main solving loop let phase = 1; while (true) { console.log('Tableau (stringified):', JSON.stringify(tableau, null, 2)); let pivotColumn = findPivotColumn(tableau[phase]); console.log('pivotColumn:', pivotColumn) if (pivotColumn === -1) { if (phase === 1) { if (isPhase1Complete(tableau)) { removeArtificialVariables(tableau, artCount); phase = 0; //phase 2 continue; } else { return "No feasible solution exists."; } } else { break; // Optimal solution reached } } const pivotRow = findPivotRow(tableau, pivotColumn); console.log('pivotRow:', pivotRow) if (pivotRow === -1) { return "The problem is unbounded."; } pivot(tableau, pivotRow, pivotColumn); } // Extract solution const solution = new Array(tableau[0].length - 1).fill(0); for (let i = 2; i < tableau.length; i++) { const basicVar = tableau[i].findIndex(value => value === 1); if (basicVar !== -1 && basicVar < solution.length) { solution[basicVar] = tableau[i][tableau[i].length - 1]; } } return { tableau: tableau, solution: solution.slice(0, 6), // Assuming the first 6 variables are the original variables objectiveValue: -tableau[0][tableau[0].length - 1] // Negative because we minimized }; } function formatSolutionOutput(solverResult, variableNames) { const output = { feasible: true, result: 0, bounded: true }; if (typeof solverResult === 'string') { // Handle infeasible or unbounded cases output.feasible = false; output.bounded = !solverResult.includes('unbounded'); return output; } output.result = Number(solverResult.objectiveValue.toFixed(8)); // Add non-zero variables to the output solverResult.solution.forEach((value, index) => { if (value > 1e-8) { // Consider values greater than 1e-8 as non-zero output[variableNames[index]] = Number(value.toFixed(8)); } }); return output; }