Skip to content

Constraints

Constraint definitions for the four PS-BHLP solution approaches.

  • BigMConstraint — couples the leader's price with the follower's decision
  • LinearizationConstraint — linearizes the cubic term \(y \cdot x \cdot x\)
  • [PrecedenceConstraint][oracle_paper.constraints.precedence_constraint.PrecendenceConstraint] — enforces ordered client acceptance
  • RecursiveLinearizationConstraint — aggregated-client version for PC-HLP

BigMConstraint

Bases: Constraint

Implements the following Big M constraints defined in PS-HLP:

Requires:

build(model, **kwargs)

Adds the following constraints to the model:

\[a_{ij}^z p_{ij} - b_{ij}^z \leq M(1 - y_{ij}^z) \quad \forall i,j \in V, z \in \Gamma_{ij}\]
\[P := \max_{i,j \in V} \frac{b_{ij}^1}{a_{ij}^1} + 1\]
\[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\]
Source code in src/oracle_paper/constraints/big_m_constraint.py 
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
def build(self, model: "BaseModel", **kwargs):
    r"""
    Adds the following constraints to the model:

    $$a_{ij}^z p_{ij} - b_{ij}^z \leq M(1 - y_{ij}^z)
    \quad \forall i,j \in V, z \in \Gamma_{ij}$$

    $$P := \max_{i,j \in V} \frac{b_{ij}^1}{a_{ij}^1} + 1$$

    $$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$$

    """
    nodes = get_nodes(model)
    data = model.data

    p = model.vars[PriceVariable]
    y = model.vars[ClientDecisionVariable]

    ratios = data[BilevelDataCol.CLIENT_RATIO]
    a = data[BilevelDataCol.TRANSPORT_WEIGHT_CLIENT]
    b = data[BilevelDataCol.BUDGET]

    P = max(ratios.values) + 1
    M = max(a.values) * P - min(b.values)

    for i in nodes:
        for j in nodes:
            model.add_constr(p[i, j] <= P, name=f"p_bound_{i}_{j}")

    for (i, j, z) in data[BilevelDataCol.CLIENT_ID_ROUTE]:
        model.add_constr(
            a[i, j, z] * p[i, j] - b[i, j, z] <= M * (1 - y[i, j, z]),
            name=f"bigM_{i}_{j}_{z}"
        )

LinearizationConstraint

Bases: Constraint

Implements the linearization from Section 5.1 of the paper, which replaces the cubic term with binary variables:

\[X_{ijkl}^z \;\widehat{=}\; y_{ij}^z \cdot x_{ik} \cdot x_{jl}\]

Used in both PS-HLP and PPC-HLP .

Requires: - [AllocationVariable][bilevelpy.models.vars.hlp_vars.AllocationVariable] - ClientDecisionVariable - LinearXYVariable

build(model, **kwargs)

Adds the following constraints to the model:

\[y_{ij}^z = \sum_{k \in V} \sum_{l \in V} X_{ijkm}^z \quad \forall i,j \in V, z \in \Gamma_{ij}\]
\[\sum_{l \in V} X_{ijkm}^z \leq x_{ik} \quad \forall i,j,k \in V, z \in \Gamma_{ij}\]
\[\sum_{k \in V} X_{ijkm}^z \leq x_{jl} \quad \forall i,j,l \in V, z \in \Gamma_{ij}\]
Source code in src/oracle_paper/constraints/linearization_constraint.py 
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
def build(self, model: "BaseModel", **kwargs):
    r"""

    Adds the following constraints to the model:

    $$y_{ij}^z = \sum_{k \in V} \sum_{l \in V}
    X_{ijkm}^z \quad \forall i,j \in V, z \in \Gamma_{ij}$$

    $$\sum_{l \in V} X_{ijkm}^z \leq x_{ik}
    \quad \forall i,j,k \in V, z \in \Gamma_{ij}$$

    $$\sum_{k \in V} X_{ijkm}^z \leq x_{jl}
    \quad \forall i,j,l \in V, z \in \Gamma_{ij}$$

    """

    nodes = get_nodes(model)
    client_keys = (model.data[BilevelDataCol.CLIENT_ID_ROUTE])

    x = model.vars[AllocationVariable]
    q = model.vars[LinearXYVariable]
    y = model.vars[ClientDecisionVariable]

    for (i, j, z) in client_keys:
        model.add_constr(
            quicksum(q[i, j, k, l, z] for k in nodes for l in nodes) == y[i, j, z],
            name=f"lin_y_{i}_{j}_{z}"
        )
        for k in nodes:
            model.add_constr(
                quicksum(q[i, j, k, l, z] for l in nodes) <= x[i, k],
                name=f"lin_x1_{i}_{j}_{z}_{k}"
            )
        for l in nodes:
            model.add_constr(
                quicksum(q[i, j, k, l, z] for k in nodes) <= x[j, l],
                name=f"lin_x2_{i}_{j}_{z}_{l}"
            )

PrecedenceConstraint

Bases: Constraint

Precedence constraint defined in PPC-HLP

Only used in the PPC-HLP model. The PC-HLP model avoids these constraints by merging customers.

Requires:

build(model, **kwargs)

Adds the following constraint to the model:

\[ y_{ij}^z \geq y_{ij}^{z+1} \quad \forall (i,j,z), (i,j,z+1) \in \Gamma_{ij} \]
Source code in src/oracle_paper/constraints/precedence_constraint.py 
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def build(self, model: "BaseModel", **kwargs):
    r"""
    Adds the following constraint to the model:

    $$
    y_{ij}^z \geq y_{ij}^{z+1} \quad \forall (i,j,z), (i,j,z+1) \in \Gamma_{ij}
    $$

    """
    data = model.data
    y = model.vars[ClientDecisionVariable]

    for (i, j, z) in data[BilevelDataCol.CLIENT_ID_ROUTE]:
        if (i, j, z + 1) in data[BilevelDataCol.CLIENT_ID_ROUTE]:
            model.add_constr(
                y[i, j, z] >= y[i, j, z + 1],
                name=f"precedence_{i}_{j}_{z}_{z + 1}"
            )

RecursiveLinearizationConstraint

Bases: Constraint

Recursive (merged-client) linearization for the PC-HLP model.

Reproduces the cubic term:

\[X_{ijkl}^z \;\widehat{=}\; y_{ij}^z \cdot x_{ik} \cdot x_{jl}\]

Same structure as LinearizationConstraint but operates on aggregated client keys from BilevelDataCol.CLIENT_KEY.

Requires: - [AllocationVariable][bilevelpy.models.vars.hlp_vars.AllocationVariable] - RecursiveClientDecisionVariable - RecursiveLinearXYVariable

build(model, **kwargs)

Adds the following constraint to the model:

\[y_{ij}^z = \sum_{k,l \in V} X_{ijkm}^z \quad \forall (i,j,z) \in K\]
\[\sum_{l} X_{ijkm}^z \leq x_{ik} \quad \sum_{k} X_{ijkm}^z \leq x_{jl}\]
Source code in src/oracle_paper/constraints/recursive_linearization_constraint.py 
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
def build(self, model: "BaseModel", **kwargs):
    r"""Adds the following constraint to the model:

        $$y_{ij}^z = \sum_{k,l \in V} X_{ijkm}^z \quad \forall (i,j,z) \in K$$

        $$\sum_{l} X_{ijkm}^z \leq x_{ik} \quad \sum_{k} X_{ijkm}^z \leq x_{jl}$$

    """
    nodes = get_nodes(model)
    client_keys = [(i, j, z) for (i, j, z), _ in model.data[BilevelDataCol.CLIENT_KEYS].items()]

    x = model.vars[AllocationVariable]
    q = model.vars[RecursiveLinearXYVariable]
    y = model.vars[RecursiveClientDecisionVariable]

    for (i, j, z) in client_keys:
        model.add_constr(
            quicksum(q[i, j, k, l, z] for k in nodes for l in nodes) == y[i, j, z],
            name=f"lin_y_{i}_{j}_{z}"
        )
        for k in nodes:
            model.add_constr(
                quicksum(q[i, j, k, l, z] for l in nodes) <= x[i, k],
                name=f"lin_x1_{i}_{j}_{z}_{k}"
            )
        for l in nodes:
            model.add_constr(
                quicksum(q[i, j, k, l, z] for k in nodes) <= x[j, l],
                name=f"lin_x2_{i}_{j}_{z}_{l}"
            )