I am trying to solve the Capacitated Plant Location Model from this YouTube Video using lp_solve:
In Excel the objective function is done using SUMPRODUCT() and I developed this function in JavaScript to replicate it:
// Sample data arrays
/* const array1 = [1, 2, 3, 4, 5];
const array2 = [2, 3, 4, 5, 6]; */
// Function to calculate the sum product
export default function sumProduct(arr1, arr2) {
if (arr1.length !== arr2.length) {
throw new Error('Arrays must have the same length');
}
let result = 0;
for (let i = 0; i < arr1.length; i++) {
result += arr1[i] * arr2[i];
}
return result;
}
// Calculate the sum product
// const result = sumProduct(array1, array2); // OUTPUT: 70 (correct)
However I cannot set up the model properly using lp_solve because the sumProd require numbers for arrays but the Decision Variables array are strings for now. Excel can just compute the empty cells using the SUMPRODUCT() function, and I am wondering if I can achieve a similar functionality with the Javascript (lp_solve) model.
Or is there another way to set up the model?
Here is how I set it up:
import sumProduct from "./sumProd.mjs";
import lp_solve from "lp_solve";
// Create a new LP model
const lp = new lp_solve.LinearProgram();
// Supply and demand locations
const locations = ["N_America", "S_America", "NCE", "MED", "APAC"];
// Transportation costs matrix
const transportationCosts = [
[81, 92, 101, 130, 115],
[117, 77, 108, 98, 100],
[102, 105, 95, 119, 111],
[115, 125, 90, 59, 74],
[142, 100, 103, 105, 71],
];
// Fixed costs and capacities
const Fixed_Costs_L = [6000, 4500, 6500, 4100, 4000];
const Low_Capacity = [10, 10, 10, 10, 10];
const Fixed_Costs_H = [9000, 6750, 9750, 6150, 6000];
const High_Capacity = [20, 20, 20, 20, 20];
// Demand values for each location
const demand = [12, 8, 14, 16, 7];
// Create an object to store indices for demand locations
const demandIndices = {};
locations.forEach((location, index) => {
demandIndices[location] = index;
});
// Add binary variables for opening/closing plants
const openPlants = {};
for (const location of locations) {
openPlants[location] = lp.addColumn(`Open_${location}`, true, false); // Indicate integer variable with 0/1 values
}
// Add columns (variables) for supply and demand allocations
const allocation = {};
for (const supplyLocation of locations) {
allocation[supplyLocation] = {};
for (const demandLocation of locations) {
allocation[supplyLocation][demandLocation] = lp.addColumn(`${supplyLocation}_${demandLocation}`, true, true); // Indicate integer variable
}
}
// Add constraints to ensure supply meets demand
for (const demandLocation of locations) {
const demandConstraint = new lp_solve.Row();
for (const supplyLocation of locations) {
demandConstraint.Add(allocation[supplyLocation][demandLocation], 1);
}
lp.addConstraint(demandConstraint, "EQ", demand[demandIndices[demandLocation]], `Demand_${demandLocation}`);
}
// Add constraints for plant capacity based on the binary decision variable
for (const supplyLocation of locations) {
const capacityConstraint = new lp_solve.Row();
capacityConstraint.Add(openPlants[supplyLocation], High_Capacity[locations.indexOf(supplyLocation)]);
capacityConstraint.Add(openPlants[supplyLocation], Low_Capacity[locations.indexOf(supplyLocation)]);
for (const demandLocation of locations) {
capacityConstraint.Subtract(allocation[supplyLocation][demandLocation], 1);
}
lp.addConstraint(capacityConstraint, "GE", 0, `Excess_Capacity_${supplyLocation}`);
}
// Add constraints to ensure supply and demand allocations are non-negative
for (const supplyLocation of locations) {
for (const demandLocation of locations) {
const nonNegativeConstraint = new lp_solve.Row();
nonNegativeConstraint.Add(allocation[supplyLocation][demandLocation], 1);
lp.addConstraint(nonNegativeConstraint, "GE", 0, `NonNegative_${supplyLocation}_${demandLocation}`);
}
}
// Set the objective function to minimize total cost
const objective = new lp_solve.Row();
for (const supplyLocation of locations) {
for (const demandLocation of locations) {
objective.Add(allocation[supplyLocation][demandLocation], transportationCosts[locations.indexOf(supplyLocation)][locations.indexOf(demandLocation)]);
}
objective.Add(openPlants[supplyLocation], Fixed_Costs_L[locations.indexOf(supplyLocation)]);
objective.Add(openPlants[supplyLocation], Fixed_Costs_H[locations.indexOf(supplyLocation)]);
}
lp.setObjective(objective, true); // true indicates minimizing
// Solve the LP optimization problem
const result = lp.solve();
console.log(lp.dumpProgram());
console.log(lp.solve());
// Display the results
if (result.description === "OPTIMAL") {
console.log("Solution found:");
for (const supplyLocation of locations) {
for (const demandLocation of locations) {
const value = lp.get(allocation[supplyLocation][demandLocation]);
if (value > 0) {
console.log(`${supplyLocation} -> ${demandLocation}: ${value}`);
}
}
const openValue = lp.get(openPlants[supplyLocation]);
console.log(`${supplyLocation} Open: ${openValue}`);
}
console.log(`Total Cost: $${lp.getObjectiveValue()}`);
} else {
console.log("No feasible solution found.");
}
What am I missing? Please help!
When ran, the model output an objective function like this, which is incorrect:
minimize: +81 N_America_N_America +92 N_America_S_America +101 N_America_NCE +130 N_America_MED +115 N_America_APAC +15000 Open_N_America +117 S_America_N_America +77 S_America_S_America +108 S_America_NCE +98 S_America_MED +100 S_America_APAC +11250 Open_S_America +102 NCE_N_America +105 NCE_S_America +95 NCE_NCE +119 NCE_MED +111 NCE_APAC +16250 Open_NCE +115 MED_N_America +125 MED_S_America +90 MED_NCE +59 MED_MED +74 MED_APAC +10250 Open_MED +142 APAC_N_America +100 APAC_S_America +103 APAC_NCE +105 APAC_MED +71 APAC_APAC +10000 Open_APAC;
The constraints seem okay, don't they?:
Demand_N_America: +1 N_America_N_America +1 S_America_N_America +1 NCE_N_America +1 MED_N_America +1 APAC_N_America = 12;
Demand_S_America: +1 N_America_S_America +1 S_America_S_America +1 NCE_S_America +1 MED_S_America +1 APAC_S_America = 8;
Demand_NCE: +1 N_America_NCE +1 S_America_NCE +1 NCE_NCE +1 MED_NCE +1 APAC_NCE = 14;
Demand_MED: +1 N_America_MED +1 S_America_MED +1 NCE_MED +1 MED_MED +1 APAC_MED = 16;
Demand_APAC: +1 N_America_APAC +1 S_America_APAC +1 NCE_APAC +1 MED_APAC +1 APAC_APAC = 7;
Excess_Capacity_N_America: +30 Open_N_America -1 N_America_N_America -1 N_America_S_America -1 N_America_NCE -1 N_America_MED -1 N_America_APAC >= 0;
Excess_Capacity_S_America: +30 Open_S_America -1 S_America_N_America -1 S_America_S_America -1 S_America_NCE -1 S_America_MED -1 S_America_APAC >= 0;
Excess_Capacity_NCE: +30 Open_NCE -1 NCE_N_America -1 NCE_S_America -1 NCE_NCE -1 NCE_MED -1 NCE_APAC >= 0;
Excess_Capacity_MED: +30 Open_MED -1 MED_N_America -1 MED_S_America -1 MED_NCE -1 MED_MED -1 MED_APAC >= 0;
Excess_Capacity_APAC: +30 Open_APAC -1 APAC_N_America -1 APAC_S_America -1 APAC_NCE -1 APAC_MED -1 APAC_APAC >= 0;
NonNegative_N_America_N_America: +1 N_America_N_America >= 0;
NonNegative_N_America_S_America: +1 N_America_S_America >= 0;
NonNegative_N_America_NCE: +1 N_America_NCE >= 0;
NonNegative_N_America_MED: +1 N_America_MED >= 0;
NonNegative_N_America_APAC: +1 N_America_APAC >= 0;
NonNegative_S_America_N_America: +1 S_America_N_America >= 0;
NonNegative_S_America_S_America: +1 S_America_S_America >= 0;
NonNegative_S_America_NCE: +1 S_America_NCE >= 0;
NonNegative_S_America_MED: +1 S_America_MED >= 0;
NonNegative_S_America_APAC: +1 S_America_APAC >= 0;
NonNegative_NCE_N_America: +1 NCE_N_America >= 0;
NonNegative_NCE_S_America: +1 NCE_S_America >= 0;
NonNegative_NCE_NCE: +1 NCE_NCE >= 0;
NonNegative_NCE_MED: +1 NCE_MED >= 0;
NonNegative_NCE_APAC: +1 NCE_APAC >= 0;
NonNegative_MED_N_America: +1 MED_N_America >= 0;
NonNegative_MED_S_America: +1 MED_S_America >= 0;
NonNegative_MED_NCE: +1 MED_NCE >= 0;
NonNegative_MED_MED: +1 MED_MED >= 0;
NonNegative_MED_APAC: +1 MED_APAC >= 0;
NonNegative_APAC_N_America: +1 APAC_N_America >= 0;
NonNegative_APAC_S_America: +1 APAC_S_America >= 0;
NonNegative_APAC_NCE: +1 APAC_NCE >= 0;
NonNegative_APAC_MED: +1 APAC_MED >= 0;
NonNegative_APAC_APAC: +1 APAC_APAC >= 0;
Please help!
You have formulated your program slightly incorrectly, and also had some paramaters wrong. For a solution to this problem you need 35 decision variables (5x5=25 for transportation allocation, 5 for low production factorys and 5 for high production factorys.) You have combined the last 10 in to 5.
Additionally, you have the isBinary flag inverted for addColumn calls.
Below is a working solution to the video's problem.
const lp_solve = require("lp_solve");
// Create a new LP model
const lp = new lp_solve.LinearProgram();
// Supply and demand locations
const locations = ["N_America", "S_America", "NCE", "MED", "APAC"];
// Transportation costs matrix
const transportationCosts = [
[81, 92, 101, 130, 115],
[117, 77, 108, 98, 100],
[102, 105, 95, 119, 111],
[115, 125, 90, 59, 74],
[142, 100, 103, 105, 71],
];
// Fixed costs and capacities
const Fixed_Costs_L = [6000, 4500, 6500, 4100, 4000];
const Low_Capacity = [10, 10, 10, 10, 10];
const Fixed_Costs_H = [9000, 6750, 9750, 6150, 6000];
const High_Capacity = [20, 20, 20, 20, 20];
// Demand values for each location
const demand = [12, 8, 14, 16, 7];
// Create an object to store indices for demand locations
const demandIndices = {};
locations.forEach((location, index) => {
demandIndices[location] = index;
});
// Add binary variables for opening/closing plants
const highPlants = {};
const lowPlants = {};
for (const location of locations) {
highPlants[location] = lp.addColumn(`Open_${location}_high`, true, true); // Indicate integer variable with 0/1 values
lowPlants[location] = lp.addColumn(`Open_${location}_low`, true, true); // Indicate integer variable with 0/1 values
}
// Add columns (variables) for supply and demand allocations
const allocation = {};
for (const supplyLocation of locations) {
allocation[supplyLocation] = {};
for (const demandLocation of locations) {
allocation[supplyLocation][demandLocation] = lp.addColumn(`${supplyLocation}_${demandLocation}`, true, false); // Indicate integer variable
}
}
// Add constraints to ensure supply meets demand
for (const demandLocation of locations) {
const demandConstraint = new lp_solve.Row();
for (const supplyLocation of locations) {
demandConstraint.Add(allocation[supplyLocation][demandLocation], 1);
}
lp.addConstraint(demandConstraint, "EQ", demand[demandIndices[demandLocation]], `Demand_${demandLocation}`);
}
// Add constraints for plant capacity based on the binary decision variable
for (const supplyLocation of locations) {
const capacityConstraint = new lp_solve.Row();
capacityConstraint.Add(highPlants[supplyLocation], High_Capacity[locations.indexOf(supplyLocation)]);
capacityConstraint.Add(lowPlants[supplyLocation], Low_Capacity[locations.indexOf(supplyLocation)]);
for (const demandLocation of locations) {
capacityConstraint.Subtract(allocation[supplyLocation][demandLocation], 1);
}
lp.addConstraint(capacityConstraint, "GE", 0, `Excess_Capacity_${supplyLocation}`);
}
// Set the objective function to minimize total cost
const objective = new lp_solve.Row();
for (const supplyLocation of locations) {
for (const demandLocation of locations) {
objective.Add(allocation[supplyLocation][demandLocation], transportationCosts[locations.indexOf(supplyLocation)][locations.indexOf(demandLocation)]);
}
objective.Add(lowPlants[supplyLocation], Fixed_Costs_L[locations.indexOf(supplyLocation)]);
objective.Add(highPlants[supplyLocation], Fixed_Costs_H[locations.indexOf(supplyLocation)]);
}
lp.setObjective(objective, true); // true indicates minimizing
console.log(lp.dumpProgram());
// Solve the LP optimization problem
const result = lp.solve();
// Display the results
if (result.description === "OPTIMAL") {
console.log("Solution found:");
for (const supplyLocation of locations) {
for (const demandLocation of locations) {
const value = lp.get(allocation[supplyLocation][demandLocation]);
if (value > 0) {
console.log(`${supplyLocation} -> ${demandLocation}: ${value}`);
}
}
const openHighValue = lp.get(highPlants[supplyLocation]);
console.log(`${supplyLocation} High Output: ${openHighValue}`);
const openLowValue = lp.get(lowPlants[supplyLocation]);
console.log(`${supplyLocation} Low Output: ${openLowValue}`);
}
console.log(`Total Cost: $${lp.getObjectiveValue()}`);
} else {
console.log("No feasible solution found.");
}
And the output:
Solution found:
N_America High Output: 0
N_America Low Output: 0
S_America -> N_America: 12
S_America -> S_America: 8
S_America High Output: 1
S_America Low Output: 0
NCE High Output: 0
NCE Low Output: 0
MED -> NCE: 4
MED -> MED: 16
MED High Output: 1
MED Low Output: 0
APAC -> NCE: 10
APAC -> APAC: 7
APAC High Output: 1
APAC Low Output: 0
Total Cost: $23751
Hope this helps.