ortools.math_opt.python.compute_infeasible_subsystem_result

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