Capacitated Facility Location (CFLP)¶

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