Skip to content

Ppc hlp

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 
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
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,
    )