ortools.math_opt.python.model_parameters

  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"""Model specific solver configuration (e.g. starting basis)."""
 15import dataclasses
 16from typing import Dict, List, Optional
 17
 18from ortools.math_opt import model_parameters_pb2
 19from ortools.math_opt.python import model
 20from ortools.math_opt.python import solution
 21from ortools.math_opt.python import sparse_containers
 22
 23
 24@dataclasses.dataclass
 25class SolutionHint:
 26    """A suggested starting solution for the solver.
 27
 28    MIP solvers generally only want primal information (`variable_values`),
 29    while LP solvers want both primal and dual information (`dual_values`).
 30
 31    Many MIP solvers can work with: (1) partial solutions that do not specify all
 32    variables or (2) infeasible solutions. In these cases, solvers typically solve
 33    a sub-MIP to complete/correct the hint.
 34
 35    How the hint is used by the solver, if at all, is highly dependent on the
 36    solver, the problem type, and the algorithm used. The most reliable way to
 37    ensure your hint has an effect is to read the underlying solvers logs with
 38    and without the hint.
 39
 40    Simplex-based LP solvers typically prefer an initial basis to a solution
 41    hint (they need to crossover to convert the hint to a basic feasible
 42    solution otherwise).
 43
 44    Floating point values should be finite and not NaN, they are validated by
 45    MathOpt at Solve() time (resulting in an exception).
 46
 47    Attributes:
 48      variable_values: a potentially partial assignment from the model's primal
 49        variables to finite (and not NaN) double values.
 50      dual_values: a potentially partial assignment from the model's linear
 51        constraints to finite (and not NaN) double values.
 52    """
 53
 54    variable_values: Dict[model.Variable, float] = dataclasses.field(
 55        default_factory=dict
 56    )
 57    dual_values: Dict[model.LinearConstraint, float] = dataclasses.field(
 58        default_factory=dict
 59    )
 60
 61    def to_proto(self) -> model_parameters_pb2.SolutionHintProto:
 62        """Returns an equivalent protocol buffer to this."""
 63        return model_parameters_pb2.SolutionHintProto(
 64            variable_values=sparse_containers.to_sparse_double_vector_proto(
 65                self.variable_values
 66            ),
 67            dual_values=sparse_containers.to_sparse_double_vector_proto(
 68                self.dual_values
 69            ),
 70        )
 71
 72
 73def parse_solution_hint(
 74    hint_proto: model_parameters_pb2.SolutionHintProto, mod: model.Model
 75) -> SolutionHint:
 76    """Returns an equivalent SolutionHint to `hint_proto`.
 77
 78    Args:
 79      hint_proto: The solution, as encoded by the ids of the variables and
 80        constraints.
 81      mod: A MathOpt Model that must contain variables and linear constraints with
 82        the ids from hint_proto.
 83
 84    Returns:
 85      A SolutionHint equivalent.
 86
 87    Raises:
 88      ValueError if hint_proto is invalid or refers to variables or constraints
 89      not in mod.
 90    """
 91    return SolutionHint(
 92        variable_values=sparse_containers.parse_variable_map(
 93            hint_proto.variable_values, mod
 94        ),
 95        dual_values=sparse_containers.parse_linear_constraint_map(
 96            hint_proto.dual_values, mod
 97        ),
 98    )
 99
100
101@dataclasses.dataclass
102class ModelSolveParameters:
103    """Model specific solver configuration, for example, an initial basis.
104
105    This class mirrors (and can generate) the related proto
106    model_parameters_pb2.ModelSolveParametersProto.
107
108    Attributes:
109      variable_values_filter: Only return solution and primal ray values for
110        variables accepted by this filter (default accepts all variables).
111      dual_values_filter: Only return dual variable values and dual ray values for
112        linear constraints accepted by thei filter (default accepts all linear
113        constraints).
114      reduced_costs_filter: Only return reduced cost and dual ray values for
115        variables accepted by this filter (default accepts all variables).
116      initial_basis: If set, provides a warm start for simplex based solvers.
117      solution_hints: Optional solution hints. If the underlying solver only
118        accepts a single hint, the first hint is used.
119      branching_priorities: Optional branching priorities. Variables with higher
120        values will be branched on first. Variables for which priorities are not
121        set get the solver's default priority (usually zero).
122    """
123
124    variable_values_filter: sparse_containers.VariableFilter = (
125        sparse_containers.VariableFilter()
126    )
127    dual_values_filter: sparse_containers.LinearConstraintFilter = (
128        sparse_containers.LinearConstraintFilter()
129    )
130    reduced_costs_filter: sparse_containers.VariableFilter = (
131        sparse_containers.VariableFilter()
132    )
133    initial_basis: Optional[solution.Basis] = None
134    solution_hints: List[SolutionHint] = dataclasses.field(default_factory=list)
135    branching_priorities: Dict[model.Variable, int] = dataclasses.field(
136        default_factory=dict
137    )
138
139    def to_proto(self) -> model_parameters_pb2.ModelSolveParametersProto:
140        """Returns an equivalent protocol buffer."""
141        # TODO(b/236289022): these methods should check that the variables are from
142        # the correct model.
143        result = model_parameters_pb2.ModelSolveParametersProto(
144            variable_values_filter=self.variable_values_filter.to_proto(),
145            dual_values_filter=self.dual_values_filter.to_proto(),
146            reduced_costs_filter=self.reduced_costs_filter.to_proto(),
147            branching_priorities=sparse_containers.to_sparse_int32_vector_proto(
148                self.branching_priorities
149            ),
150        )
151        if self.initial_basis:
152            result.initial_basis.CopyFrom(self.initial_basis.to_proto())
153        for hint in self.solution_hints:
154            result.solution_hints.append(hint.to_proto())
155        return result