Skip to content

Ps hlp

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 
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
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 
118
119
120
121
122
123
124
125
126
127
128
129
130
131
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
    )