Capacitated Facility Location (CFLP)

Principles learned

  • Create a set decision variable

  • Use a lambda expression to compute a sum on a set

Problem

../_images/capacitatedfacilitylocation.svg

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 example


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;

/* 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-1] {
        // 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[0..nbSites-1] = inFile.readDouble();

    // Allocation price between sites and facilities
    allocationPrice[0..nbMaxFacilities-1][0..nbSites-1] = inFile.readDouble();
}

/* Declare the optimization model */
function model() {
    // Facilities are represented by the set of sites they provide
    facilityAssignments[0..nbMaxFacilities-1] <- set(nbSites);

    // Each site is covered by exactly one facility
    constraint partition[f in 0..nbMaxFacilities-1](facilityAssignments[f]);

    for [f in 0..nbMaxFacilities-1] {
        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-1](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-1 : 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_11_5/bin/python
python 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\localsolver115.lib
capacitated_facility_location instances\cap61
Compilation / Execution (Linux)
g++ capacitated_facility_location.cpp -I/opt/localsolver_11_5/include -llocalsolver115 -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.dll
CapacitatedFacilityLocation instances\cap61
using System;
using System.IO;
using System.Collections.Generic;
using localsolver;

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]);
                // List of fixed costs induced by the facilities opening
                openingPriceData[f] = double.Parse(splitted[1]);
            }

            // Demand of each site
            splitted = SplitInput(input);
            for (int s = 0; s < nbSites; ++s)
                demandData[s] = double.Parse(splitted[s]);

            // 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]);
            }
        }
    }

    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)
    {
        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.jar
java -cp %LS_HOME%\bin\localsolver.jar;. CapacitatedFacilityLocation instances\cap61
Compilation / Execution (Linux)
javac CapacitatedFacilitylocation.java -cp /opt/localsolver_11_5/bin/localsolver.jar
java -cp /opt/localsolver_11_5/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);
        }
    }
}