Facility Location (FLP)¶
Principles learned¶
Create a generic model that uses data
Define the actual set of decision variables
Use non-linearities: ternary operator, minimizing a sum of “min”
Problem¶
The facility location problem is defined as follows: given a set of N locations and a transportation cost W between each pair of locations, select a subset S of p locations, which become facilities, in order to minimize transportation costs. The transportation cost for a location is defined as the distance to the closest facility, that is, the closest location in S. Thus, it aims to provide an optimal placement of facilities to minimize transportation costs. This problem is also known as the p-median problem.
Download the exampleData¶
The data files pmed1.in, pmed2.in, …, pmed40.in provided come from the OR-LIB. They are the 40 test problems from Table 2 of J.E.Beasley “A note on solving large p-median problems” European Journal of Operational Research 21 (1985) 270-273.
Each instance file contains the number of locations n, the number of edges in the original instance, the number of facilities to select p and the distance matrix computed from the original file using Floyd’s algorithm.
Program¶
In this problem, once you know the locations that are in the subset S, you can deduce which facility in S is the closest to each location.
The general idea behind the model is than once one know the facilities that are in the subset S, one can deduce the distance between each location and the closest facility in S. There is no need to actually know which facility is the closest in the model, just the closest distance. It can still be obtained through post-processing if one need to know this information to print out the results.
Thus, the only decision variables are the booleans x[i]
, equal to 1 if the
ith location is in the subset S. The expressions costs[i][j]
are created to
store the transportation cost between location i and j. This cost is:
edge weight between i and j if j is in the subset S, i.e is a facility
infinity otherwise (represented by 2 times the maximum edge weight)
The transportation cost between each location i and the closest facility in S is
represented by cost[i]
: it is the minimum value among costs[i][j]
for
all j. The objective is then to minimize the sum of these transportation costs.
- Execution:
- localsolver facility_location.lsp inFileName=instances/pmed1.in [lsTimeLimit=] [solFileName=]
/********** facility_location.lsp **********/
use io;
/* Reads instance data. */
function input() {
local usage = "Usage: localsolver facility_location.lsp "
+ "inFileName=inputFile [solFileName=outputFile] [lsTimeLimit=timeLimit]";
if (inFileName == nil) throw usage;
local inFile = io.openRead(inFileName);
N = inFile.readInt();
E = inFile.readInt();
p = inFile.readInt();
wmax = 0;
w[i in 1..N][j in 1..N] = inFile.readInt();
wmax = max[i in 1..N][j in 1..N] (w[i][j]);
}
/* Declares the optimization model. */
function model() {
// One variable for each location : 1 if facility, 0 otherwise
x[1..N] <- bool();
// No more than p locations are selected to be facilities
constraint sum[i in 1..N] (x[i]) <= p;
// Costs between location i and j is w[i][j] if j is a facility or 2*wmax if not
costs[i in 1..N][j in 1..N] <- x[j] ? w[i][j] : 2*wmax;
// Cost between location i and the closest facility
cost[i in 1..N] <- min[j in 1..N] (costs[i][j]);
// Minimize the total cost
totalCost <- sum[i in 1..N] (cost[i]);
minimize totalCost;
}
/* Parameterizes the solver. */
function param() {
if (lsTimeLimit == nil) lsTimeLimit = 20;
}
/* Writes the solution in a file following the following format:
* - value of the objective
* - indices of the facilities (between 0 and N-1) */
function output() {
if (solFileName == nil) return;
local solFile = io.openWrite(solFileName);
solFile.println(totalCost.value);
for [i in 1..N : x[i].value == 1]
solFile.print(i-1, " ");
solFile.println("");
}
- Execution (Windows)
- set PYTHONPATH=%LS_HOME%\bin\pythonpython facility_location.py instances\pmed1.in
- Execution (Linux)
- export PYTHONPATH=/opt/localsolver_11_0/bin/pythonpython facility_location.py instances/pmed1.in
########## facility_location.py ##########
import localsolver
import sys
if len(sys.argv) < 2:
print("Usage: python facility_location.py inputFile [outputFile] [timeLimit]")
sys.exit(1)
def read_integers(filename):
with open(filename) as f:
return [int(elem) for elem in f.read().split()]
with localsolver.LocalSolver() as ls:
#
# Reads instance data
#
file_it = iter(read_integers(sys.argv[1]))
# Number of locations
N = next(file_it)
# Number of edges between locations
E = next(file_it)
# Size of the subset S of facilities
p = next(file_it)
# w: Weight matrix of the shortest path between locations
# wmax: Maximum distance between two locations
wmax = 0
w = [None] * N
for i in range(N):
w[i] = [None] * N
for j in range(N):
w[i][j] = next(file_it)
if w[i][j] > wmax:
wmax = w[i][j]
#
# Declares the optimization model
#
m = ls.model
# One variable for each location : 1 if facility, 0 otherwise
x = [m.bool() for i in range(N)]
# No more than p locations are selected to be facilities
opened_locations = m.sum(x[i] for i in range(N))
m.constraint(opened_locations <= p)
# Costs between location i and j is w[i][j] if j is a facility or 2*wmax if not
costs = [None] * N
for i in range(N):
costs[i] = [None] * N
for j in range(N):
costs[i][j] = m.iif(x[j], w[i][j], 2 * wmax)
# Cost between location i and the closest facility
cost = [None] * N
for i in range(N):
cost[i] = m.min(costs[i][j] for j in range(N))
# Minimize the total cost
total_cost = m.sum(cost[i] for i in range(N))
m.minimize(total_cost)
m.close()
#
# Parameterizes the solver
#
if len(sys.argv) >= 4:
ls.param.time_limit = int(sys.argv[3])
else:
ls.param.time_limit = 20
ls.solve()
#
# Writes the solution in a file following the following format:
# - value of the objective
# - indices of the facilities (between 0 and N-1)
#
if len(sys.argv) >= 3:
with open(sys.argv[2], 'w') as f:
f.write("%d\n" % total_cost.value)
for i in range(N):
if x[i].value == 1:
f.write("%d " % i)
f.write("\n")
- Compilation / Execution (Windows)
- cl /EHsc facility_location.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver110.libfacility_location instances\pmed1.in
- Compilation / Execution (Linux)
- g++ facility_location.cpp -I/opt/localsolver_11_0/include -llocalsolver110 -lpthread -o facilitylocation./facility_location instances/pmed1.in
//********* facility_location.cpp *********
#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include "localsolver.h"
using namespace localsolver;
using namespace std;
class Facilitylocation {
public:
// Number of locations
lsint N;
// Number of edges between locations
lsint E;
// Size of the subset S of facilities
lsint p;
// Weight matrix of the shortest path between locations
vector<vector<lsint> > w;
// Maximum distance between two locations
lsint wmax;
// LocalSolver
LocalSolver localsolver;
// Decisions variables
vector<LSExpression> x;
// Objective
LSExpression totalCost;
// Vector of facilities
vector<int> solution;
// Reads instance data
void readInstance(const string & fileName) {
ifstream infile;
infile.exceptions(ifstream::failbit | ifstream::badbit);
infile.open(fileName.c_str());
infile >> N;
infile >> E;
infile >> p;
w.resize(N);
wmax = 0;
for (int i = 0; i < N; i++) {
w[i].resize(N);
for (int j = 0; j < N; j++) {
infile >> w[i][j];
if (w[i][j] > wmax) {
wmax = w[i][j];
}
}
}
}
// Declares the optimization model
void solve(int limit) {
LSModel m = localsolver.getModel();
// One variable for each location : 1 if facility, 0 otherwise
x.resize(N);
for (int i = 0; i < N; i++)
x[i] = m.boolVar();
// No more than p locations are selected to be facilities
LSExpression openedLocations = m.sum(x.begin(), x.end());
m.constraint(openedLocations <= p);
// Costs between location i and j is w[i][j] if j is a facility or 2*wmax if not
vector<vector<LSExpression> > costs(N);
for (int i = 0; i < N; i++) {
costs[i].resize(N);
for (int j = 0; j < N; j++) {
costs[i][j] = m.iif(x[j], w[i][j], 2*wmax);
}
}
// Cost between location i and the closest facility
vector<LSExpression> cost(N);
for (int i = 0; i < N; i++) {
cost[i] = m.min(costs[i].begin(), costs[i].end());
}
// Minimize the total cost
totalCost = m.sum(cost.begin(), cost.end());
m.minimize(totalCost);
m.close();
// Parameterizes the solver
localsolver.getParam().setTimeLimit(limit);
localsolver.solve();
solution.clear();
for (int i = 0; i < N; i++) {
if (x[i].getValue() == 1) {
solution.push_back(i);
}
}
}
// Writes the solution in a file following the following format:
// each line contains the index of a facility (between 0 and N-1)
void writeSolution(const string& fileName) {
ofstream outfile;
outfile.exceptions(ofstream::failbit | ofstream::badbit);
outfile.open(fileName.c_str());
outfile << totalCost.getValue() << endl;
for (int i = 0; i < solution.size(); i++)
outfile << solution[i] << " ";
outfile << endl;
}
};
int main(int argc, char** argv) {
if (argc < 2) {
cerr << "Usage: 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 {
Facilitylocation model;
model.readInstance(instanceFile);
model.solve(atoi(strTimeLimit));
if (solFile != NULL) model.writeSolution(solFile);
return 0;
} catch (const exception& e) {
cerr << "An error occurred: " << e.what() << endl;
return 1;
}
}
- Compilation / Execution (Windows)
- copy %LS_HOME%\bin\localsolvernet.dll .csc Facilitylocation.cs /reference:localsolvernet.dllFacilitylocation instances\pmed1.in
/********** Facilitylocation.cs **********/
using System;
using System.IO;
using System.Collections.Generic;
using localsolver;
public class Facilitylocation : IDisposable
{
// Number of locations
int N;
// Number of edges between locations
int E;
// Size of the subset S of facilities
int p;
// Weight matrix of the shortest path beween locations
int[][] w;
// Maximum distance between two locations
int wmax;
// LocalSolver
LocalSolver localsolver;
// Decision variables
LSExpression[] x;
// Objective
LSExpression totalCost;
// List of facilities
List<int> solution;
public Facilitylocation()
{
localsolver = new LocalSolver();
}
// Reads instance data
public void ReadInstance(string fileName)
{
using (StreamReader input = new StreamReader(fileName))
{
var tokens = input.ReadLine().Split(' ');
N = int.Parse(tokens[0]);
E = int.Parse(tokens[1]);
p = int.Parse(tokens[2]);
w = new int[N][];
wmax = 0;
for (int i = 0; i < N; i++)
{
tokens = input.ReadLine().Split(' ');
w[i] = new int[N];
for (int j = 0; j < N; j++)
{
w[i][j] = int.Parse(tokens[j]);
if (w[i][j] > wmax)
wmax = w[i][j];
}
}
}
}
public void Dispose()
{
if (localsolver != null)
localsolver.Dispose();
}
// Declares the optimization model
public void Solve(int limit)
{
localsolver = new LocalSolver();
LSModel model = localsolver.GetModel();
x = new LSExpression[N];
// One variable for each location : 1 if facility, 0 otherwise
for (int i = 0; i < N; i++)
x[i] = model.Bool();
// No more than p locations are selected to be facilities
LSExpression openedLocations = model.Sum(x);
model.Constraint(openedLocations <= p);
// Costs between location i and j is w[i][j] if j is a facility or 2*wmax if not
LSExpression[][] costs = new LSExpression[N][];
for (int i = 0; i < N; i++)
{
costs[i] = new LSExpression[N];
for (int j = 0; j < N; j++)
{
costs[i][j] = model.If(x[j], w[i][j], 2 * wmax);
}
}
// Cost between location i and the closest facility
LSExpression[] cost = new LSExpression[N];
for (int i = 0; i < N; i++)
cost[i] = model.Min(costs[i]);
// Minimize the total cost.
totalCost = model.Sum(cost);
model.Minimize(totalCost);
model.Close();
// Parameterizes the solver
localsolver.GetParam().SetTimeLimit(limit);
localsolver.Solve();
solution = new List<int>();
for (int i = 0; i < N; i++)
if (x[i].GetValue() == 1)
solution.Add(i);
}
// Writes the solution in a file following the following format:
// - value of the objective
// - indices of the facilities (between 0 and N-1)
public void WriteSolution(string fileName)
{
using (StreamWriter output = new StreamWriter(fileName))
{
output.WriteLine(totalCost.GetValue());
for (int i = 0; i < solution.Count; ++i)
output.Write(solution[i] + " ");
output.WriteLine();
}
}
public static void Main(string[] args)
{
if (args.Length < 1)
{
Console.WriteLine("Usage: Facilitylocation inputFile [outputFile] [timeLimit]");
Environment.Exit(1);
}
string instanceFile = args[0];
string outputFile = args.Length > 1 ? args[1] : null;
string strTimeLimit = args.Length > 2 ? args[2] : "20";
using (Facilitylocation model = new Facilitylocation())
{
model.ReadInstance(instanceFile);
model.Solve(int.Parse(strTimeLimit));
if (outputFile != null)
model.WriteSolution(outputFile);
}
}
}
- Compilation / Execution (Windows)
- javac Facilitylocation.java -cp %LS_HOME%\bin\localsolver.jarjava -cp %LS_HOME%\bin\localsolver.jar;. Facilitylocation instances\pmed1.in
- Compilation / Execution (Linux)
- javac Facilitylocation.java -cp /opt/localsolver_11_0/bin/localsolver.jarjava -cp /opt/localsolver_11_0/bin/localsolver.jar:. Facilitylocation instances/pmed1.in
/********** Facilitylocation.java **********/
import java.util.*;
import java.io.*;
import localsolver.*;
public class Facilitylocation {
// Number of locations
private int N;
// Number of edges between locations
private int E;
// Size of the subset S of facilities
private int p;
// Weight matrix of the shortest path between locations
private int[][] w;
// Maximum distance between two locations
private int wmax;
// LocalSolver.
private final LocalSolver localsolver;
// Decisions variables
private LSExpression[] x;
// Objective
private LSExpression totalCost;
// List of selected locations
private List<Integer> solution;
private Facilitylocation(LocalSolver localsolver) {
this.localsolver = localsolver;
}
// Reads instance data
private void readInstance(String fileName) throws IOException {
try (Scanner input = new Scanner(new File(fileName))) {
N = input.nextInt();
E = input.nextInt();
p = input.nextInt();
w = new int[N][N];
wmax = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
w[i][j] = input.nextInt();
if (w[i][j] > wmax)
wmax = w[i][j];
}
}
}
}
// Declares the optimization model
private void solve(int limit) {
LSModel model = localsolver.getModel();
// One variable for each location : 1 if facility, 0 otherwise
x = new LSExpression[N];
for (int i = 0; i < N; i++) {
x[i] = model.boolVar();
}
// No more than p locations are selected to be facilities
LSExpression openedLocations = model.sum(x);
model.constraint(model.leq(openedLocations, p));
// Costs between location i and j is w[i][j] if j is a facility or 2*wmax if not
LSExpression[][] costs = new LSExpression[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
costs[i][j] = model.iif(x[j], w[i][j], 2 * wmax);
}
}
// Cost between location i and the closest facility
LSExpression[] cost = new LSExpression[N];
for (int i = 0; i < N; i++) {
cost[i] = model.min(costs[i]);
}
// Minimize the total cost
totalCost = model.sum(cost);
model.minimize(totalCost);
model.close();
// Parameterizes the solver
localsolver.getParam().setTimeLimit(limit);
localsolver.solve();
solution = new ArrayList<Integer>();
for (int i = 0; i < N; i++) {
if (x[i].getValue() == 1)
solution.add(i);
}
}
// Writes the solution in a file following the following format:
// - value of the objective
// - indices of the facilities (between 0 and N-1) */
private void writeSolution(String fileName) throws IOException {
try (PrintWriter output = new PrintWriter(fileName)) {
output.println(totalCost.getValue());
for (int i = 0; i < solution.size(); i++) {
output.print(solution.get(i) + " ");
}
output.println();
}
}
public static void main(String[] args) {
if (args.length < 1) {
System.err.println("Usage: java Facilitylocation inputFile [outputFile] [timeLimit]");
System.exit(1);
}
String instanceFile = args[0];
String outputFile = args.length > 1 ? args[1] : null;
String strTimeLimit = args.length > 2 ? args[2] : "10";
try (LocalSolver localsolver = new LocalSolver()) {
Facilitylocation model = new Facilitylocation(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);
}
}
}