Oracle paper

Oracle Paper — reference implementation for price-setting problems in logistics.

This package provides four solution approaches for the Price-Setting Bilevel Hub Location Problem (PS-BHLP), built on top of BilevelPy:

• PS_HLP — Big-M linearization
• PC_HLP — Fast Lagrange with recursive client aggregation
• PPC_HLP — Standard Lagrange decomposition with precedence constraints
• PS_BHLP — Bilevel formulation (requires Julia)

BilevelDataCol

Bases: StrEnum

Extra column names used in bilevel hub location datasets.

These columns sit alongside the standard [DataCol][bilevelpy.core.columns.DataCol] columns and carry the additional data that the bilevel models need: per-client budgets, transport weights, Lagrange multipliers, and aggregated keys for the recursive (PC-HLP) formulation.

Attributes:

Name	Type	Description
CLIENT_KEY		Unique integer key assigned to each client.
CLIENT_ID_ROUTE		Zero-based index \(z\) of a client on route \((i,j)\).
CLIENT_ROUTE		The \((i,j)\) route tuple the client belongs to.
CLIENT_RATIO		Budget-to-weight ratio \(b_{ij}^z / a_{ij}^z\).
BUDGET		Client budget \(b_{ij}^z\) (willingness to pay).
TRANSPORT_WEIGHT_CLIENT		Client demand weight \(a_{ij}^z\).
LAGRANGE		Lagrange multiplier \(\lambda_{ij}^z\) for the PPC-HLP model.
RECURSIVE_LAGRANGE		Lagrange multiplier after recursive merging (PC-HLP).
CLIENT_KEYS		Mapping \((i,j,z) \to\) list of original client keys that were merged into this aggregated client.
SUMMED_LINEAR_WEIGHTS		Sum of \(a_{ij}^z\) over all clients merged into an aggregated recursive client.
SUMMED_BUDGETS		Sum of \(b_{ij}^z\) over all clients merged into an aggregated recursive client.

OraclePaperModelNames

Registry of [ModelMetaData][bilevelpy.models.meta.ModelMetaData] instances for all four models studied in the paper.

Each attribute is a [ModelMetaData][bilevelpy.models.meta.ModelMetaData] carrying a short value (used for equality checks) and a display_name (shown in UIs and reports).

Attributes:

Name	Type	Description
PS_HLP		Big-M price-setting model (price is a Gurobi variable).
PC_HLP		Fast Lagrange model with recursive client aggregation.
PPC_HLP		Standard Lagrange decomposition with precedence constraints.
PS_BHLP		Bilevel formulation solved via Julia + BilevelJuMP.

PC_HLP(n_hubs, alpha, data)

Bases: BaseModel

Fast Lagrange Model — recursive client-aggregated formulation.

Unlike PS_HLP, this model uses aggregated client keys \((i,j,z)\) where \(z\) indexes a group of original clients. Clients are grouped by route \((i,j)\), ranked, and Lagrange multipliers \(\lambda_{ij}^z\) are computed recursively over segments. Price is not a Gurobi variable — it is inferred post-solve from the budget/weight ratio of the marginal client.

Variables:

Symbol	Reproduces	Variable	Domain
\(x_{ik}\)	—	[AllocationVariable][bilevelpy.models.vars.hlp_vars.AllocationVariable]	\(\{0,1\}\)
\(y_{ij}^z\)	—	RecursiveClientDecisionVariable	\(\{0,1\}\)
\(X_{ijkm}^z\)	\(y_{ij}^z \cdot x_{ik} \cdot x_{jm}\)	RecursiveLinearXYVariable	\(\{0,1\}\)

Constraints:

Constraint	Reference
HLP base	[NumberOfHubs][bilevelpy.models.constraints.hlp_constraints.NumberOfHubsConstraint], [SingleAllocation][bilevelpy.models.constraints.hlp_constraints.SingleAllocationConstraint], [AssignmentRestriction][bilevelpy.models.constraints.hlp_constraints.AssignmentRestrictionConstraint]
\(y = \sum X\), \(X \leq x\)	RecursiveLinearizationConstraint

Objective (maximizes Lagrange-adjusted profit):

\[\max \sum_{(i,j,z) \in K} \Bigl( \lambda_{ij}^z y_{ij}^z - a_{ij}^z \tilde{c}_{ij}(x) \Bigr)\]

where \(K\) is the set of aggregated client keys and \(\lambda_{ij}^z\) are the recursive Lagrange multipliers.

Parameters:

Name	Type	Description	Default
n_hubs	int	Number of hubs to open (\(p\)).	required
alpha	float	Cost scaling factor (\(\alpha\)).	required
data	MultiEntityDataset	Dataset with recursive Lagrange multipliers and grouped client keys.	required

Source code in src/oracle_paper/models/pc_hlp.py

def __init__(
        self,
        n_hubs: int,
        alpha: float,
        data: MultiEntityDataset,
) -> None:
    super().__init__(data)

    self._n_hubs = n_hubs
    self._alpha = alpha

    vars = [AllocationVariable,
            RecursiveClientDecisionVariable,
            RecursiveLinearXYVariable]

    constraints = [
        NumberOfHubsConstraint,
        SingleAllocationConstraint,
        AssignmentRestrictionConstraint,
        RecursiveLinearizationConstraint,
    ]

    self.build(
        variables=vars,
        constraints=constraints,
        n_hubs=n_hubs,
    )

PPC_HLP(n_hubs, alpha, data)

Bases: BaseModel

Lagrange Model — standard Lagrange multiplier decomposition.

Uses Lagrange multipliers \(\lambda_{ij}^z\) to decompose the bilevel problem. Price is inferred post-solve (no price variable). Includes a precedence constraint ordering client decisions.

Variables:

Symbol	Reproduces	Variable	Domain
\(x_{ik}\)	—	[AllocationVariable][bilevelpy.models.vars.hlp_vars.AllocationVariable]	\(\{0,1\}\)
\(y_{ij}^z\)	—	ClientDecisionVariable	\(\{0,1\}\)
\(X_{ijkm}^z\)	\(y_{ij}^z \cdot x_{ik} \cdot x_{jm}\)	LinearXYVariable	\(\{0,1\}\)

Constraints:

Constraint	Reference
HLP base	[NumberOfHubs][bilevelpy.models.constraints.hlp_constraints.NumberOfHubsConstraint], [SingleAllocation][bilevelpy.models.constraints.hlp_constraints.SingleAllocationConstraint], [AssignmentRestriction][bilevelpy.models.constraints.hlp_constraints.AssignmentRestrictionConstraint]
\(y = \sum X\), \(X \leq x\)	LinearizationConstraint
\(y_{ij}^z \geq y_{ij}^{z+1}\)	[PrecendenceConstraint][oracle_paper.constraints.precedence_constraint.PrecendenceConstraint]

Objective (maximizes Lagrange-adjusted profit):

\[\max \sum_{(i,j,z) \in M} \Bigl( \lambda_{ij}^z y_{ij}^z - a_{ij}^z \tilde{c}_{ij}(x) \Bigr)\]

Precedence constraint:

\[y_{ij}^z \geq y_{ij}^{z+1} \quad \forall (i,j,z),(i,j,z+1) \in M\]

Ensures clients on the same route are accepted in ranked order (highest budget/weight ratio first).

Parameters:

Name	Type	Description	Default
n_hubs	int	Number of hubs to open (\(p\)).	required
alpha	float	Cost scaling factor (\(\alpha\)).	required
data	MultiEntityDataset	Dataset with Lagrange multipliers and client data.	required

Source code in src/oracle_paper/models/ppc_hlp.py

def __init__(
        self,
        n_hubs: int,
        alpha: float,
        data: MultiEntityDataset,
) -> None:
    super().__init__(data)

    self._n_hubs = n_hubs
    self._alpha = alpha

    vars = [AllocationVariable,
                ClientDecisionVariable,
                LinearXYVariable]

    constraints = [
        NumberOfHubsConstraint,
        SingleAllocationConstraint,
        AssignmentRestrictionConstraint,
        LinearizationConstraint,
        PrecedenceConstraint,
    ]

    self.build(
        variables=vars,
        constraints=constraints,
        n_hubs=n_hubs,
    )

PS_BHLP(n_hubs, alpha, data)

Bases: BaseModel

PS-BHLP solved via Julia Big-M reformulation.

Requires Julia ≥ 1.10 with JuMP, Gurobi, BilevelJuMP, and JSON on PATH.

Source code in src/oracle_paper/models/ps_bhlp.py

def __init__(
    self,
    n_hubs: int,
    alpha: float,
    data: MultiEntityDataset,
) -> None:
    super().__init__(data)
    self._n_hubs = n_hubs
    self._alpha = alpha

    json_payload = self._build_json_payload()

    lp_path: str | None = None
    json_path: str | None = None

    try:
        with tempfile.NamedTemporaryFile(
            mode="w", suffix=".json", delete=False, encoding="utf-8"
        ) as jf:
            json.dump(json_payload, jf)
            json_path = jf.name

        lp_path = json_path.replace(".json", ".lp")

        result = subprocess.run(
            [
                _JULIA_EXE,
                str(self.julia_script),
                json_path,
                lp_path,
            ],
            capture_output=True,
            text=True,
            timeout=600,
        )

        if result.returncode != 0:
            raise RuntimeError(
                f"Julia PS_BHLP model generation failed.\n"
                f"STDERR:\n{result.stderr}\n"
                f"STDOUT:\n{result.stdout}"
            )

        if not os.path.exists(lp_path) or os.path.getsize(lp_path) == 0:
            raise RuntimeError(
                f"Julia exited successfully but no LP file was produced "
                f"at {lp_path}"
            )

        self.model = gp.read(lp_path)

    finally:
        for path in (json_path, lp_path):
            if path and os.path.exists(path):
                try:
                    os.unlink(path)
                except OSError:
                    pass

PS_HLP(n_hubs, alpha, data)

Bases: BaseModel

Price-Setting Hub Location Problem with Big-M linearization.

The leader (hub operator) sets prices \(p_{ij}\) and allocates hubs \(x_{ik}\). The follower (clients) chooses routes \(y_{ij}^z\) to maximize their utility.

Variables:

Symbol	Reproduces	Variable	Domain
\(x_{ik}\)	—	[AllocationVariable][bilevelpy.models.vars.hlp_vars.AllocationVariable]	\(\{0,1\}\)
\(y_{ij}^z\)	—	ClientDecisionVariable	\(\{0,1\}\)
\(X_{ijkm}^z\)	\(y_{ij}^z \cdot x_{ik} \cdot x_{jm}\)	LinearXYVariable	\(\{0,1\}\)
\(p_{ij}\)	—	PriceVariable	\(\mathbb{R}_{\geq 0}\)

Constraints:

Constraint	Reference
Exactly \(p\) hubs open	[NumberOfHubsConstraint][bilevelpy.models.constraints.hlp_constraints.NumberOfHubsConstraint]
Each node to one hub	[SingleAllocationConstraint][bilevelpy.models.constraints.hlp_constraints.SingleAllocationConstraint]
Only assigned to open hubs	[AssignmentRestrictionConstraint][bilevelpy.models.constraints.hlp_constraints.AssignmentRestrictionConstraint]
\(y = \sum X\), \(X \leq x\)	LinearizationConstraint
Price-revenue coupling	BigMConstraint

Objective (leader maximizes profit):

\[\max \sum_{i,j \in V} \sum_{z \in M_{ij}} a_{ij}^z \; y_{ij}^z \bigl(p_{ij} - \tilde{c}_{ij}(x)\bigr)\]

where \(\tilde{c}_{ij}(x) = \sum_{k,m \in V} X_{ijkm}^z \bigl(\alpha\, c_{ik} + \alpha\, c_{km} + c_{mj}\bigr)\) is the transport cost through hubs \(k,m\).

Big-M constraint (couples price and decision):

\[a_{ij}^z p_{ij} - b_{ij}^z \leq M(1 - y_{ij}^z)\]

\[P := \max_{i,j} \frac{b_{ij}^1}{a_{ij}^1} + 1, \qquad M := \max_{i,j,z} a_{ij}^z \cdot P - \min_{i,j,z} b_{ij}^z\]

\[p_{ij} \leq P \quad \forall i,j \in V\]

Parameters:

Name	Type	Description	Default
n_hubs	int	Number of hubs to open (\(p\)).	required
alpha	float	Cost scaling factor (\(\alpha\)).	required
data	MultiEntityDataset	Dataset with client weights, budgets, and transport costs.	required

Source code in src/oracle_paper/models/ps_hlp.py

def __init__(
    self,
    n_hubs: int,
    alpha: float,
    data: MultiEntityDataset,
) -> None:
    super().__init__(data)
    self._n_hubs = n_hubs
    self._alpha = alpha

    vars = [
        AllocationVariable,
        ClientDecisionVariable,
        LinearXYVariable,
        PriceVariable,
    ]

    constraints = [
        NumberOfHubsConstraint,
        SingleAllocationConstraint,
        AssignmentRestrictionConstraint,
        LinearizationConstraint,
        BigMConstraint,
    ]

    self.build(
        variables=vars,
        constraints=constraints,
        n_hubs=n_hubs,
    )

get_transport_cost_sum(i, j, z)

Compute the transport cost \(\tilde{c}_{ij}(x)\) for a route.

\[\tilde{c}_{ij}(x) = \sum_{k \in V} \sum_{m \in V} X_{ijkm}^z \bigl(\alpha c_{ik} + \alpha c_{km} + c_{mj}\bigr)\]

Source code in src/oracle_paper/models/ps_hlp.py

def get_transport_cost_sum(self, i, j, z) -> gp.LinExpr:
    r"""Compute the transport cost $\tilde{c}_{ij}(x)$ for a route.

    $$\tilde{c}_{ij}(x) = \sum_{k \in V} \sum_{m \in V}
    X_{ijkm}^z \bigl(\alpha c_{ik} + \alpha c_{km} + c_{mj}\bigr)$$
    """
    nodes = get_nodes(self)
    q = self.vars[LinearXYVariable]
    return quicksum(
        q[i, j, k, m, z]
        * transport_cost_hlp(self, i, k, m, j, self._alpha)
        for k in nodes
        for m in nodes
    )