# 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.

## Data¶

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;

function input() {
usage = "Usage: localsolver capacitated_facility_location.lsp "
+ "inFileName=inputFile [solFileName=outputFile] [lsTimeLimit=timeLimit]";

if (inFileName == nil) throw usage;

for [f in 0...nbMaxFacilities] {
// List of facilities capacities
// List of fixed costs induced by the facilities opening
}

// Demand of each site

// 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\python
python capacitated_facility_location.py instances\cap61
Execution (Linux)
export PYTHONPATH=/opt/localsolver_12_0/bin/python
python capacitated_facility_location.py instances/cap61
```import localsolver
import sys

def main(instanceFile, strTimeLimit, solFile):

#
#
nb_max_facilities, nb_sites, capacity_data, opening_price_data, \

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):

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")

with open(filename) as f:
return [str(elem) for elem in f.read().split()]

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
solFile = sys.argv if len(sys.argv) > 2 else None
strTimeLimit = sys.argv 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.lib
capacitated_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) {
}

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();
}

ifstream infile;
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.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;
const char* solFile = argc > 2 ? argv : NULL;
const char* strTimeLimit = argc > 3 ? argv : "20";
try {
CapacitatedFacilityLocation model;
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.dll
CapacitatedFacilityLocation 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;

{
if (line == null)
return new string;
return line.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
}

{
{
string[] splitted;
splitted = SplitInput(input);
nbMaxFacilities = int.Parse(splitted);
nbSites = int.Parse(splitted);

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, CultureInfo.InvariantCulture);
// List of fixed costs induced by the facilities opening
openingPriceData[f] = double.Parse(splitted, 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;
string outputFile = args.Length > 1 ? args : null;
string strTimeLimit = args.Length > 2 ? args : "20";

using (CapacitatedFacilityLocation model = new CapacitatedFacilityLocation())
{
model.Solve(int.Parse(strTimeLimit));
if (outputFile != null)
model.WriteSolution(outputFile);
}
}
}
```
Compilation / Execution (Windows)
javac CapacitatedFacilityLocation.java -cp %LS_HOME%\bin\localsolver.jar
java -cp %LS_HOME%\bin\localsolver.jar;. CapacitatedFacilityLocation instances\cap61
Compilation / Execution (Linux)
javac CapacitatedFacilitylocation.java -cp /opt/localsolver_12_0/bin/localsolver.jar
java -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;
}

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;
String outputFile = args.length > 1 ? args : null;
String strTimeLimit = args.length > 2 ? args : "20";

CapacitatedFacilityLocation model = new CapacitatedFacilityLocation(localsolver);