Models

Model implementations for the Price-Setting Bilevel Hub Location Problem.

• PS_HLP — Big-M reformulation
• PC_HLP — Fast Lagrange with recursive client aggregation
• PPC_HLP — Standard Lagrange with precedence constraints
• PS_BHLP — Julia-based bilevel formulation

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
    )