ortools.math_opt.python.compute_infeasible_subsystem_result

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