Skip to content

math_spec.boundedness

Provably unbounded models, named before a solver says a bare unbounded.

A variable that is unbounded on the side its objective term improves toward and appears in no constraint runs to infinity for any data at all. Advice rather than a refusal, because the same shape is what a half-written model looks like.

Which side improves is read off the sign the variable enters the objective with: under minimize a +v term runs down toward lower. Where that sign is not decidable without data — a parameter coefficient, or occurrences of both signs — nothing is claimed.

Sign = Literal['+', '-'] | None module-attribute #

unbounded_notes(schema) #

Name every variable the objective can drive to infinity unopposed.

Takes an expanded schema: a piecewise: block holds the variables it names, and does so through the constraints it expands into.

RETURNS DESCRIPTION
list[str]

One note per variable that is unbounded on the side its objective term
list[str]

improves toward and named by no constraint.
Source code in src/math_spec/boundedness.py 
53
54
55
56
57
58
59
60
61
62
63
64
65
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
def unbounded_notes(schema: Model) -> list[str]:
    """Name every variable the objective can drive to infinity unopposed.

    Takes an expanded schema: a ``piecewise:`` block holds the variables it
    names, and does so through the constraints it expands into.

    Returns:
        One note per variable that is unbounded on the side its objective term
        improves toward and named by no constraint.
    """
    if schema.objective is None:
        return []

    ns = Namespace.of(schema)
    objective = expression_of(schema.objective.expression, schema, ns, 'The objective')
    assert not isinstance(objective, ComparisonNode), 'an objective holds no comparison — checked before this runs'

    constrained = {block.variable for block in schema.sos.values()}
    for cname, cdef in schema.constraints.items():
        constrained |= _variables(expression_of(cdef.expression, schema, ns, f"Constraint '{cname}'"))

    signs: dict[str, Sign] = {}
    _walk(objective, '+', signs)

    minimize = schema.objective.sense == 'minimize'
    notes = []
    for vname, sign in signs.items():
        if sign is None or vname in constrained:
            continue
        side = 'lower' if minimize == (sign == '+') else 'upper'
        if _is_open(schema.variables[vname], side):
            notes.append(
                f"Variable '{vname}' makes this model unbounded: no constraint names it, and "
                f'bounds.{side} is {_OPEN[side]}, which is the direction a {sign}{vname} term '
                f'improves a {schema.objective.sense} objective in. No data can change that, so '
                f'the solve would answer `unbounded` and name nothing.\n'
                f'Give it a finite bounds.{side}, or the constraint that was meant to define it.'
            )
    return notes