Lemoine-OR Algorithms
Description

What this method is

Facility-location formulation is an exact solver-backed ULS strategy. It builds a mathematical formulation and delegates the optimization step to the selected external engine while keeping the common IUlsSolver result contract.

How it works

Core idea

The method builds its portable linear or mixed-integer formulation, automatically selects an available engine in the CPLEX -> Gurobi -> Xpress -> CBC priority order, solves the model, normalizes numerical values and reconstructs a UlsSolution that is checked independently.

Implementation in ULSAlgorithmsDisaggregated q[t,k]/y formulation
Mathematical formulation

Disaggregated facility-location model

The equations below use periods 1,...,T for readability. q_{tk} is the quantity of demand in period k supplied by production in period t.

q_{tk} assignment quantityy_t setup
\[ c_{tk}=p_t+\sum_{r=t}^{k-1}h_r \]
\[ \min \sum_{t=1}^{T}f_t y_t +\sum_{k=1}^{T}\sum_{t=1}^{k}c_{tk}q_{tk} \]

subject to

\[ \sum_{t=1}^{k}q_{tk}=d_k, \qquad k=1,\ldots,T \]
\[ q_{tk}\le d_k y_t, \qquad 1\le t\le k\le T \]
\[ q_{tk}\ge0,\qquad y_t\in\{0,1\}. \]

Zero-demand assignment variables are omitted by the implementation.

Use it

Minimal C# example

using ULSAlgorithms.Abstractions;
using ULSAlgorithms.Models;
using ULSAlgorithms.Exact.Formulations;

var problem = new UlsProblem(
    demands:             [20.0, 30.0, 25.0, 40.0],
    setupCosts:          [200.0, 200.0, 200.0, 200.0],
    unitProductionCosts: [0.0, 0.0, 0.0, 0.0],
    holdingCosts:        [4.0, 4.0, 4.0, 0.0]);

IUlsSolver solver = new FacilityLocationFormulationSolver();
var result = solver.Solve(problem);

Console.WriteLine(result.Status);
Console.WriteLine(result.ObjectiveValue);

The input example intentionally uses stationary, positive-demand data so it is compatible with restricted methods too. Always check the applicability box for your own instance.

Scientific source

Reference & provenance

Krarup & Bilde (1977), Plant Location, Set Covering and Economic Lot Size: An O(nm)-Algorithm for Structured Problems; Brahimi, Dauzere-Peres, Najid & Nordli (2006), Single Item Lot Sizing Problems, European Journal of Operational Research 168(1), 1-16 · DOI 10.1007/978-3-0348-5936-3_10

Full detailsOpen API reference → ImplementationOpen source file ↗ Before choosingComplexity & applicability →