Skip to content

Big m constraint

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}"
        )