Skip to content

math_spec.boundedness

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

A variable unbounded on the side its objective term improves toward, and named by no constraint, runs to infinity for any data. Which side 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.

BoundSide = Literal['lower', 'upper'] module-attribute #

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

unbounded_notes(program) #

Name every variable the objective can drive to infinity unopposed.

PARAMETER DESCRIPTION
program

The lowered program, in which piecewise: has already become the constraints it expands into.

TYPE: Program

RETURNS DESCRIPTION
list[Advice]

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

improves toward and named by no constraint.
Source code in src/math_spec/boundedness.py 
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
92
93
94
95
def unbounded_notes(program: Program) -> list[Advice]:
    """Name every variable the objective can drive to infinity unopposed.

    Args:
        program: The lowered program, in which ``piecewise:`` has already
            become 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 program.objective is None:
        return []

    constrained = {block.variable for block in program.sos.values()}
    for constraint in program.constraints.values():
        constrained |= variables_of(constraint.lhs, constraint.rhs)

    signs: dict[str, Sign] = {}
    _record_signs(program.objective.expression, '+', signs)

    minimize = program.objective.sense == 'minimize'
    notes: list[Advice] = []
    for vname, sign in signs.items():
        if sign is None or vname in constrained:
            continue
        side: BoundSide = 'lower' if minimize == (sign == '+') else 'upper'
        if _is_open(program.variables[vname], side):
            notes.append(
                Advice(
                    'unbounded',
                    vname,
                    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 {program.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