Capacitated Facility Location (CFLP)¶
Principles learned¶
Create a set decision variable
Use a lambda expression to compute a sum on a set
Problem¶
The capacitated facility location problem is the problem of locating a number of facilities which have to serve sites, at minimum cost, where each site has a given demand and each facility has a given capacity. The cost for a facility is defined as the sum of a fixed opening price and the allocation prices due to transportation between the facility and every site it provides. This problem is also known as capacitated warehouse location problem, or capacitated p-median problem.
Download the exampleData¶
The data files cap61, cap62, cap63 and cap64 provided come from the OR-LIB. They are the test problems from Tables 1, 2 and 3 of J.E.Beasley “An algorithm for solving large capacitated warehouse location problems” European Journal of Operational Research 33 (1988) 314-325.
Each instance file contains the number of potential facilities, the number of sites, the table of capacities and opening prices for each potential facility, the table of demand for each site, and the matrix of allocation prices between each facility and each site.
Program¶
In this problem, you need to decide the set of sites each facility will provide. If this set is empty, the facility will remain close, otherwise it will open and the associated cost will be the opening price plus the allocation costs. The capacity constraint is that for every facility, the sum of demand from the sites it provides can not exceed its capacity.
Thus, the only decision variables are the sets facilityAssignment[f]
that contains
all the sites provided by facility f. The expressions costs[f]
are created to
store cost due to facility f. This cost is :
0 if
facilityAssignment[f]
is an empty set.opening price + the sum of allocation prices between f and the sites it provides otherwise
We want to minimize the total cost.
- Execution:
- localsolver capacitated_facility_location.lsp inFileName=instances/cap61 [lsTimeLimit=] [solFileName=]
use io;
/* Read instance data */
function input() {
usage = "Usage: localsolver capacitated_facility_location.lsp "
+ "inFileName=inputFile [solFileName=outputFile] [lsTimeLimit=timeLimit]";
if (inFileName == nil) throw usage;
local inFile = io.openRead(inFileName);
nbMaxFacilities = inFile.readInt();
nbSites = inFile.readInt();
for [f in 0...nbMaxFacilities] {
// List of facilities capacities
capacity[f] = inFile.readDouble();
// List of fixed costs induced by the facilities opening
openingPrice[f] = inFile.readDouble();
}
// Demand of each site
demand[s in 0...nbSites] = inFile.readDouble();
// Allocation price between sites and facilities
allocationPrice[f in 0...nbMaxFacilities][s in 0...nbSites] = inFile.readDouble();
}
/* Declare the optimization model */
function model() {
// Facilities are represented by the set of sites they provide
facilityAssignments[f in 0...nbMaxFacilities] <- set(nbSites);
// Each site is covered by exactly one facility
constraint partition[f in 0...nbMaxFacilities](facilityAssignments[f]);
for [f in 0...nbMaxFacilities] {
local facility <- facilityAssignments[f];
local size <- count(facility);
// Capacity constraint
constraint sum(facility, i => demand[i]) <= capacity[f];
// Cost (allocation price + opening price)
cost[f] <- sum(facility, i => allocationPrice[f][i]) + openingPrice[f] * (size > 0);
}
// Objective : minimize total cost
totalCost <- sum[f in 0...nbMaxFacilities](cost[f]);
minimize totalCost;
}
/* Parametrize the solver */
function param() {
if (lsTimeLimit == nil) lsTimeLimit = 20;
}
/* Write the solution in a file with the following format:
* - value of the objective
* - indices of the open facilities followed by all the sites they provide */
function output() {
if (solFileName == nil) return;
local outfile = io.openWrite(solFileName);
outfile.println(totalCost.value);
for [f in 0...nbMaxFacilities : cost[f].value > 0] {
outfile.println(f);
for [s in facilityAssignments[f].value]
outfile.print(s, " ");
outfile.println();
}
}
- Execution (Windows)
- set PYTHONPATH=%LS_HOME%\bin\pythonpython capacitated_facility_location.py instances\cap61
- Execution (Linux)
- export PYTHONPATH=/opt/localsolver_12_0/bin/pythonpython capacitated_facility_location.py instances/cap61
import localsolver
import sys
def main(instanceFile, strTimeLimit, solFile):
#
# Read instance data
#
nb_max_facilities, nb_sites, capacity_data, opening_price_data, \
demand_data, allocation_price_data = read_data(instanceFile)
with localsolver.LocalSolver() as ls:
#
# Declare the optimization model
#
model = ls.model
# Facilities are represented by the set of sites they provide
facility_assignments = [model.set(nb_sites) for _ in range(nb_max_facilities)]
# Each site is covered by exactly one facility
model.constraint(model.partition(facility_assignments))
# Converting demand and allocationPrice into LocalSolver array
demand = model.array(demand_data)
allocation_price = model.array()
for f in range(nb_max_facilities):
allocation_price.add_operand(model.array(allocation_price_data[f]))
cost = [None] * nb_max_facilities
for f in range(nb_max_facilities):
facility = facility_assignments[f]
size = model.count(facility)
# Capacity constraint
demand_lambda = model.lambda_function(lambda i: demand[i])
model.constraint(model.sum(facility, demand_lambda) <= capacity_data[f])
# Cost (allocation price + opening price)
costSelector = model.lambda_function(lambda i: model.at(allocation_price, f, i))
cost[f] = model.sum(facility, costSelector) + opening_price_data[f] * (size > 0)
# Objective : minimize total cost
totalCost = model.sum(cost)
model.minimize(totalCost)
model.close()
# Parameterize the solver
ls.param.time_limit = int(strTimeLimit)
ls.solve()
#
# Write the solution in a file with the following format:
# - value of the objective
# - indices of the open facilities followed by all the sites they provide
#
if solFile:
with open(solFile, 'w') as outputFile:
outputFile.write("%d" % totalCost.value)
for f in range(nb_max_facilities):
if cost[f].value > 0:
outputFile.write("%d\n" % f)
for site in facility_assignments[f].value:
outputFile.write("%d " % site)
outputFile.write("\n")
def read_elem(filename):
with open(filename) as f:
return [str(elem) for elem in f.read().split()]
def read_data(filename):
file_it = iter(read_elem(filename))
nb_max_facilities = int(next(file_it))
nb_sites = int(next(file_it))
capacity_data = []
opening_price_data = []
demand_data = []
allocation_price_data = []
for f in range(nb_max_facilities):
# List of facilities capacities
capacity_data.append(float(next(file_it)))
# List of fixed costs induced by the facilities opening
opening_price_data.append(float(next(file_it)))
allocation_price_data.append([])
# Demand of each site
for s in range(nb_sites):
demand_data.append(float(next(file_it)))
# Allocation price between sites and facilities
for f in range(nb_max_facilities):
for s in range(nb_sites):
allocation_price_data[f].append(float(next(file_it)))
return nb_max_facilities, nb_sites, capacity_data, opening_price_data, \
demand_data, allocation_price_data
if __name__ == '__main__':
if len(sys.argv) < 2:
print("Usage: python capacitated_facility_location.py input_file \
[output_file] [time_limit]")
sys.exit(1)
instanceFile = sys.argv[1]
solFile = sys.argv[2] if len(sys.argv) > 2 else None
strTimeLimit = sys.argv[3] if len(sys.argv) > 3 else "20"
main(instanceFile, strTimeLimit, solFile)
- Compilation / Execution (Windows)
- cl /EHsc capacitated_facility_location.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver120.libcapacitated_facility_location instances\cap61
- Compilation / Execution (Linux)
- g++ capacitated_facility_location.cpp -I/opt/localsolver_12_0/include -llocalsolver120 -lpthread -o capacitated_facility_location./capacitated_facility_location instances/pmed1.in
#include "localsolver.h"
#include <fstream>
#include <iostream>
#include <string.h>
#include <vector>
using namespace localsolver;
using namespace std;
class CapacitatedFacilityLocation {
public:
// Data from the problem
int nbMaxFacilities;
int nbSites;
vector<double> capacityData;
vector<double> openingPriceData;
vector<double> demandData;
vector<vector<double>> allocationPriceData;
// LocalSolver
LocalSolver localsolver;
// Variables
vector<LSExpression> facilityAssignments;
// Objective
vector<LSExpression> cost;
LSExpression totalCost;
void solve(int limit) {
// Declare the optimization model
LSModel model = localsolver.getModel();
// Table of sets representing the sites provided by each facility
facilityAssignments.resize(nbMaxFacilities);
for (int f = 0; f < nbMaxFacilities; ++f) {
facilityAssignments[f] = model.setVar(nbSites);
}
// Each site is covered by exactly one facility
model.constraint(model.partition(facilityAssignments.begin(), facilityAssignments.end()));
// Converting demand and allocationPrice into LocalSolver array
LSExpression demand = model.array(demandData.begin(), demandData.end());
LSExpression allocationPrice = model.array();
for (int f = 0; f < nbMaxFacilities; ++f) {
allocationPrice.addOperand(model.array(allocationPriceData[f].begin(), allocationPriceData[f].end()));
}
cost.resize(nbMaxFacilities);
for (int f = 0; f < nbMaxFacilities; ++f) {
LSExpression facility = facilityAssignments[f];
LSExpression size = model.count(facility);
// Capacity constraint
LSExpression demandLambda = model.createLambdaFunction([&](LSExpression i) { return demand[i]; });
model.constraint(model.sum(facility, demandLambda) <= capacityData[f]);
// Cost (allocation price + opening price)
LSExpression costLambda =
model.createLambdaFunction([&](LSExpression i) { return model.at(allocationPrice, f, i); });
cost[f] = model.sum(facility, costLambda) + (size > 0) * openingPriceData[f];
}
// Objective : minimize total cost
totalCost = model.sum(cost.begin(), cost.end());
model.minimize(totalCost);
model.close();
// Parametrize the solver
localsolver.getParam().setTimeLimit(limit);
localsolver.solve();
}
/* Read instance data */
void readInstance(const string& fileName) {
ifstream infile;
infile.exceptions(ifstream::failbit | ifstream::badbit);
infile.open(fileName.c_str());
infile >> nbMaxFacilities;
infile >> nbSites;
capacityData.resize(nbMaxFacilities);
openingPriceData.resize(nbMaxFacilities);
demandData.resize(nbSites);
allocationPriceData.resize(nbMaxFacilities, vector<double>(nbSites));
for (int f = 0; f < nbMaxFacilities; ++f) {
// List of facilities capacities
infile >> capacityData[f];
// List of fixed costs induced by the facilities opening
infile >> openingPriceData[f];
}
// Demand of each site
for (int s = 0; s < nbSites; ++s) {
infile >> demandData[s];
}
// Allocation price between sites and facilities
for (int f = 0; f < nbMaxFacilities; ++f) {
for (int s = 0; s < nbSites; ++s) {
infile >> allocationPriceData[f][s];
}
}
infile.close();
}
/* Write the solution in a file with the following format:
* - value of the objective
* - indices of the open facilities followed by all the sites they provide */
void writeSolution(const string& fileName) {
ofstream outfile;
outfile.exceptions(ofstream::failbit | ofstream::badbit);
outfile.open(fileName.c_str());
outfile << totalCost.getDoubleValue() << endl;
for (int f = 0; f < nbMaxFacilities; ++f) {
if (cost[f].getDoubleValue() > 0) {
outfile << f << endl;
LSCollection sites_assigned = facilityAssignments[f].getCollectionValue();
for (lsint s = 0; s < sites_assigned.count(); ++s) {
outfile << sites_assigned[s] << " ";
}
outfile << endl;
}
}
}
};
int main(int argc, char** argv) {
if (argc < 2) {
cerr << "Usage: capacitated_facility_location inputFile [outputfile] [timeLimit]" << endl;
return 1;
}
const char* instanceFile = argv[1];
const char* solFile = argc > 2 ? argv[2] : NULL;
const char* strTimeLimit = argc > 3 ? argv[3] : "20";
try {
CapacitatedFacilityLocation model;
model.readInstance(instanceFile);
model.solve(atoi(strTimeLimit));
if (solFile != NULL)
model.writeSolution(solFile);
} catch (const exception& e) {
cerr << "An error occured " << e.what() << endl;
return -1;
}
}
- Compilation / Execution (Windows)
- copy %LS_HOME%\bin\localsolvernet.dll .csc CapacitatedFacilityLocation.cs /reference:localsolvernet.dllCapacitatedFacilityLocation instances\cap61
using System;
using System.IO;
using System.Collections.Generic;
using localsolver;
using System.Globalization;
public class CapacitatedFacilityLocation : IDisposable
{
// Data from the problem
int nbMaxFacilities;
int nbSites;
double[] capacityData;
double[] openingPriceData;
double[] demandData;
double[,] allocationPriceData;
// LocalSolver
LocalSolver localsolver = new LocalSolver();
// Variables
LSExpression[] facilityAssignments;
// Objective
LSExpression[] cost;
LSExpression totalCost;
private string[] SplitInput(StreamReader input)
{
string line = input.ReadLine();
if (line == null)
return new string[0];
return line.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
}
void ReadInstance(string fileName)
{
using (StreamReader input = new StreamReader(fileName))
{
string[] splitted;
splitted = SplitInput(input);
nbMaxFacilities = int.Parse(splitted[0]);
nbSites = int.Parse(splitted[1]);
capacityData = new double[nbMaxFacilities];
openingPriceData = new double[nbMaxFacilities];
demandData = new double[nbSites];
allocationPriceData = new double[nbMaxFacilities, nbSites];
for (int f = 0; f < nbMaxFacilities; ++f)
{
splitted = SplitInput(input);
// List of facilities capacities
capacityData[f] = double.Parse(splitted[0], CultureInfo.InvariantCulture);
// List of fixed costs induced by the facilities opening
openingPriceData[f] = double.Parse(splitted[1], CultureInfo.InvariantCulture);
}
// Demand of each site
splitted = SplitInput(input);
for (int s = 0; s < nbSites; ++s)
demandData[s] = double.Parse(splitted[s], CultureInfo.InvariantCulture);
// Allocation price between sites and facilities
for (int f = 0; f < nbMaxFacilities; ++f)
{
splitted = SplitInput(input);
for (int s = 0; s < nbSites; ++s)
allocationPriceData[f, s] = double.Parse(splitted[s], CultureInfo.InvariantCulture);
}
}
}
public void Dispose()
{
if (localsolver != null)
localsolver.Dispose();
}
void Solve(int limit)
{
// Declare the optimization model
LSModel model = localsolver.GetModel();
// Facilities are represented by the sets of sites they provide
facilityAssignments = new LSExpression[nbMaxFacilities];
for (int f = 0; f < nbMaxFacilities; ++f)
facilityAssignments[f] = model.Set(nbSites);
// Each site is covered by exactly one facility
model.Constraint(model.Partition(facilityAssignments));
// Converting demand and allocationPrice into LocalSolver array
LSExpression demand = model.Array(demandData);
LSExpression allocationPrice = model.Array(allocationPriceData);
cost = new LSExpression[nbMaxFacilities];
for (int f = 0; f < nbMaxFacilities; ++f)
{
LSExpression facility = facilityAssignments[f];
LSExpression size = model.Count(facility);
// Capacity constraint
LSExpression demandLambda = model.LambdaFunction(i => demand[i]);
model.Constraint(model.Sum(facility, demandLambda) <= capacityData[f]);
// Cost (allocation price + opening price)
LSExpression costLambda = model.LambdaFunction(i => allocationPrice[f, i]);
cost[f] = model.Sum(facility, costLambda) + model.If(size > 0, openingPriceData[f], 0);
}
// Objective : minimizing total cost
totalCost = model.Sum(cost);
model.Minimize(totalCost);
model.Close();
// Parameterize the solver
localsolver.GetParam().SetTimeLimit(limit);
localsolver.Solve();
}
// Write the solution in a file with the following format:
// - value of the objective
// - indices of the open facilities followed by all the sites they provide
void WriteSolution(string fileName)
{
using (StreamWriter output = new StreamWriter(fileName))
{
output.WriteLine(totalCost.GetDoubleValue());
for (int f = 0; f < nbMaxFacilities; ++f)
{
if (cost[f].GetDoubleValue() > 0)
{
output.WriteLine(f);
LSCollection assigned_sites = facilityAssignments[f].GetCollectionValue();
for (int s = 0; s < assigned_sites.Count(); ++s)
output.Write(assigned_sites[s] + " ");
output.WriteLine();
}
}
}
}
public static void Main(string[] args)
{
if (args.Length < 1)
{
Console.WriteLine("Usage: CapacitatedFacilityLocation instanceFile [outputFile] [timeLimit]");
System.Environment.Exit(1);
}
string instanceFile = args[0];
string outputFile = args.Length > 1 ? args[1] : null;
string strTimeLimit = args.Length > 2 ? args[2] : "20";
using (CapacitatedFacilityLocation model = new CapacitatedFacilityLocation())
{
model.ReadInstance(instanceFile);
model.Solve(int.Parse(strTimeLimit));
if (outputFile != null)
model.WriteSolution(outputFile);
}
}
}
- Compilation / Execution (Windows)
- javac CapacitatedFacilityLocation.java -cp %LS_HOME%\bin\localsolver.jarjava -cp %LS_HOME%\bin\localsolver.jar;. CapacitatedFacilityLocation instances\cap61
- Compilation / Execution (Linux)
- javac CapacitatedFacilitylocation.java -cp /opt/localsolver_12_0/bin/localsolver.jarjava -cp /opt/localsolver_12_0/bin/localsolver.jar:. CapacitatedFacilityLocation instances/cap61
import java.util.*;
import java.io.*;
import localsolver.*;
public class CapacitatedFacilityLocation {
// Data from the problem
private int nbMaxFacilities;
private int nbSites;
private double[] capacityData;
private double[] openingPriceData;
private double[] demandData;
private double[][] allocationPriceData;
// LocalSolver
private final LocalSolver localsolver;
// Variables
private LSExpression[] facilityAssignments;
// Objective
private LSExpression[] cost;
private LSExpression totalCost;
private CapacitatedFacilityLocation(LocalSolver localsolver) {
this.localsolver = localsolver;
}
/* Read instance data */
private void readInstance(String fileName) throws IOException {
try (Scanner input = new Scanner(new File(fileName))) {
nbMaxFacilities = input.nextInt();
nbSites = input.nextInt();
capacityData = new double[nbMaxFacilities];
openingPriceData = new double[nbMaxFacilities];
demandData = new double[nbSites];
allocationPriceData = new double[nbMaxFacilities][nbSites];
for (int f = 0; f < nbMaxFacilities; ++f) {
// List of facilities capacities
capacityData[f] = input.nextDouble();
// List of fixed costs induced by the facilities opening
openingPriceData[f] = input.nextDouble();
}
// Demand of each site
for (int s = 0; s < nbSites; ++s) {
demandData[s] = input.nextDouble();
}
// Allocation price between sites and facilities
for (int f = 0; f < nbMaxFacilities; ++f) {
for (int s = 0; s < nbSites; ++s) {
allocationPriceData[f][s] = input.nextDouble();
}
}
}
}
private void solve(int limit) {
// Declare the optimization model
LSModel model = localsolver.getModel();
// Facilities are represented by the sets of sites they provide
facilityAssignments = new LSExpression[nbMaxFacilities];
for (int f = 0; f < nbMaxFacilities; ++f) {
facilityAssignments[f] = model.setVar(nbSites);
}
// Each site is covered by exactly one facility
model.constraint(model.partition(facilityAssignments));
// Converting demand and allocationPrice into LocalSolver array
LSExpression demand = model.array(demandData);
LSExpression allocationPrice = model.array(allocationPriceData);
cost = new LSExpression[nbMaxFacilities];
for (int f = 0; f < nbMaxFacilities; ++f) {
LSExpression fExpr = model.createConstant(f);
LSExpression facility = facilityAssignments[f];
LSExpression size = model.count(facility);
// Capacity constraint
LSExpression demandLambda = model.lambdaFunction(i -> model.at(demand, i));
model.constraint(model.leq(model.sum(facility, demandLambda), capacityData[f]));
// Cost (allocation price + opening price)
LSExpression costLambda = model.lambdaFunction(i -> model.at(allocationPrice, fExpr, i));
cost[f] = model.sum(model.sum(facility, costLambda), model.iif(model.gt(size, 0), openingPriceData[f], 0));
}
// Objective : minimize total cost
totalCost = model.sum(cost);
model.minimize(totalCost);
model.close();
// Parameterize the solver
localsolver.getParam().setTimeLimit(limit);
localsolver.solve();
}
/*
* Write the solution in a file with the following format:
* - value of the objective
* - indices of the open facilities followed by all the sites they provide
*/
private void writeSolution(String file_name) throws IOException {
try (PrintWriter output = new PrintWriter(file_name)) {
output.println(totalCost.getDoubleValue());
for (int f = 0; f < nbMaxFacilities; ++f) {
if (cost[f].getDoubleValue() > 0) {
output.println(f);
LSCollection sites_assigned = facilityAssignments[f].getCollectionValue();
for (int s = 0; s < sites_assigned.count(); ++s) {
output.print(sites_assigned.get(s) + " ");
}
output.println();
}
}
}
}
public static void main(String[] args) {
try (LocalSolver localsolver = new LocalSolver()) {
String instanceFile = args[0];
String outputFile = args.length > 1 ? args[1] : null;
String strTimeLimit = args.length > 2 ? args[2] : "20";
CapacitatedFacilityLocation model = new CapacitatedFacilityLocation(localsolver);
model.readInstance(instanceFile);
model.solve(Integer.parseInt(strTimeLimit));
if (outputFile != null) {
model.writeSolution(outputFile);
}
} catch (Exception ex) {
System.err.println(ex);
ex.printStackTrace();
System.exit(1);
}
}
}