ortools.math_opt.python.compute_infeasible_subsystem_result

  1# Copyright 2010-2025 Google LLC
  2# Licensed under the Apache License, Version 2.0 (the "License");
  3# you may not use this file except in compliance with the License.
  4# You may obtain a copy of the License at
  5#
  6#     http://www.apache.org/licenses/LICENSE-2.0
  7#
  8# Unless required by applicable law or agreed to in writing, software
  9# distributed under the License is distributed on an "AS IS" BASIS,
 10# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 11# See the License for the specific language governing permissions and
 12# limitations under the License.
 13
 14"""Data types for the result of calling `mathopt.compute_infeasible_subsystem."""
 15
 16import dataclasses
 17from typing import FrozenSet, Mapping
 18
 19import immutabledict
 20
 21from ortools.math_opt import infeasible_subsystem_pb2
 22from ortools.math_opt.python import linear_constraints as linear_constraints_mod
 23from ortools.math_opt.python import model
 24from ortools.math_opt.python import result
 25from ortools.math_opt.python import variables as variables_mod
 26
 27
 28@dataclasses.dataclass(frozen=True)
 29class ModelSubsetBounds:
 30    """Presence of the upper and lower bounds in a two-sided constraint.
 31
 32    E.g. for 1 <= x <= 2, `lower` is the constraint 1 <= x and `upper` is the
 33    constraint x <= 2.
 34
 35    Attributes:
 36      lower: If the lower bound half of the two-sided constraint is selected.
 37      upper: If the upper bound half of the two-sided constraint is selected.
 38    """
 39
 40    lower: bool = False
 41    upper: bool = False
 42
 43    def empty(self) -> bool:
 44        """Is empty if both `lower` and `upper` are False."""
 45        return not (self.lower or self.upper)
 46
 47    def to_proto(self) -> infeasible_subsystem_pb2.ModelSubsetProto.Bounds:
 48        """Returns an equivalent proto message for these bounds."""
 49        return infeasible_subsystem_pb2.ModelSubsetProto.Bounds(
 50            lower=self.lower, upper=self.upper
 51        )
 52
 53
 54def parse_model_subset_bounds(
 55    bounds: infeasible_subsystem_pb2.ModelSubsetProto.Bounds,
 56) -> ModelSubsetBounds:
 57    """Returns an equivalent `ModelSubsetBounds` to the input proto."""
 58    return ModelSubsetBounds(lower=bounds.lower, upper=bounds.upper)
 59
 60
 61@dataclasses.dataclass(frozen=True)
 62class ModelSubset:
 63    """A subset of a Model's constraints (including variable bounds/integrality).
 64
 65    When returned from `solve.compute_infeasible_subsystem`, the contained
 66    `ModelSubsetBounds` will all be nonempty.
 67
 68    Attributes:
 69      variable_bounds: The upper and/or lower bound constraints on these variables
 70        are included in the subset.
 71      variable_integrality: The constraint that a variable is integer is included
 72        in the subset.
 73      linear_constraints: The upper and/or lower bounds from these linear
 74        constraints are included in the subset.
 75    """
 76
 77    variable_bounds: Mapping[variables_mod.Variable, ModelSubsetBounds] = (
 78        immutabledict.immutabledict()
 79    )
 80    variable_integrality: FrozenSet[variables_mod.Variable] = frozenset()
 81    linear_constraints: Mapping[
 82        linear_constraints_mod.LinearConstraint, ModelSubsetBounds
 83    ] = immutabledict.immutabledict()
 84
 85    def empty(self) -> bool:
 86        """Returns true if all the nested constraint collections are empty.
 87
 88        Warning: When `self.variable_bounds` or `self.linear_constraints` contain
 89        only ModelSubsetBounds which are themselves empty, this function will return
 90        False.
 91
 92        Returns:
 93          True if this is empty.
 94        """
 95        return not (
 96            self.variable_bounds or self.variable_integrality or self.linear_constraints
 97        )
 98
 99    def to_proto(self) -> infeasible_subsystem_pb2.ModelSubsetProto:
100        """Returns an equivalent proto message for this `ModelSubset`."""
101        return infeasible_subsystem_pb2.ModelSubsetProto(
102            variable_bounds={
103                var.id: bounds.to_proto()
104                for (var, bounds) in self.variable_bounds.items()
105            },
106            variable_integrality=sorted(var.id for var in self.variable_integrality),
107            linear_constraints={
108                con.id: bounds.to_proto()
109                for (con, bounds) in self.linear_constraints.items()
110            },
111        )
112
113
114def parse_model_subset(
115    model_subset: infeasible_subsystem_pb2.ModelSubsetProto, mod: model.Model
116) -> ModelSubset:
117    """Returns an equivalent `ModelSubset` to the input proto."""
118    if model_subset.quadratic_constraints:
119        raise NotImplementedError(
120            "quadratic_constraints not yet implemented for ModelSubset in Python"
121        )
122    if model_subset.second_order_cone_constraints:
123        raise NotImplementedError(
124            "second_order_cone_constraints not yet implemented for ModelSubset in"
125            " Python"
126        )
127    if model_subset.sos1_constraints:
128        raise NotImplementedError(
129            "sos1_constraints not yet implemented for ModelSubset in Python"
130        )
131    if model_subset.sos2_constraints:
132        raise NotImplementedError(
133            "sos2_constraints not yet implemented for ModelSubset in Python"
134        )
135    if model_subset.indicator_constraints:
136        raise NotImplementedError(
137            "indicator_constraints not yet implemented for ModelSubset in Python"
138        )
139    return ModelSubset(
140        variable_bounds={
141            mod.get_variable(var_id): parse_model_subset_bounds(bounds)
142            for var_id, bounds in model_subset.variable_bounds.items()
143        },
144        variable_integrality=frozenset(
145            mod.get_variable(var_id) for var_id in model_subset.variable_integrality
146        ),
147        linear_constraints={
148            mod.get_linear_constraint(con_id): parse_model_subset_bounds(bounds)
149            for con_id, bounds in model_subset.linear_constraints.items()
150        },
151    )
152
153
154@dataclasses.dataclass(frozen=True)
155class ComputeInfeasibleSubsystemResult:
156    """The result of searching for an infeasible subsystem.
157
158    This is the result of calling `mathopt.compute_infeasible_subsystem()`.
159
160    Attributes:
161      feasibility: If the problem was proven feasible, infeasible, or no
162        conclusion was reached. The fields below are ignored unless the problem
163        was proven infeasible.
164      infeasible_subsystem: Ignored unless `feasibility` is `INFEASIBLE`, a subset
165        of the model that is still infeasible.
166      is_minimal: Ignored unless `feasibility` is `INFEASIBLE`. If True, then the
167        removal of any constraint from `infeasible_subsystem` makes the sub-model
168        feasible. Note that, due to problem transformations MathOpt applies or
169        idiosyncrasies of the solvers contract, the returned infeasible subsystem
170        may not actually be minimal.
171    """
172
173    feasibility: result.FeasibilityStatus = result.FeasibilityStatus.UNDETERMINED
174    infeasible_subsystem: ModelSubset = ModelSubset()
175    is_minimal: bool = False
176
177    def to_proto(
178        self,
179    ) -> infeasible_subsystem_pb2.ComputeInfeasibleSubsystemResultProto:
180        """Returns an equivalent proto for this `ComputeInfeasibleSubsystemResult`."""
181        return infeasible_subsystem_pb2.ComputeInfeasibleSubsystemResultProto(
182            feasibility=self.feasibility.value,
183            infeasible_subsystem=self.infeasible_subsystem.to_proto(),
184            is_minimal=self.is_minimal,
185        )
186
187
188def parse_compute_infeasible_subsystem_result(
189    infeasible_system_result: infeasible_subsystem_pb2.ComputeInfeasibleSubsystemResultProto,
190    mod: model.Model,
191) -> ComputeInfeasibleSubsystemResult:
192    """Returns an equivalent `ComputeInfeasibleSubsystemResult` to the input proto."""
193    return ComputeInfeasibleSubsystemResult(
194        feasibility=result.FeasibilityStatus(infeasible_system_result.feasibility),
195        infeasible_subsystem=parse_model_subset(
196            infeasible_system_result.infeasible_subsystem, mod
197        ),
198        is_minimal=infeasible_system_result.is_minimal,
199    )