ortools.math_opt.python.solution

  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"""The solution to an optimization problem defined by Model in model.py."""
 15import dataclasses
 16import enum
 17from typing import Dict, Optional, TypeVar
 18
 19from ortools.math_opt import solution_pb2
 20from ortools.math_opt.python import model
 21from ortools.math_opt.python import sparse_containers
 22
 23
 24@enum.unique
 25class BasisStatus(enum.Enum):
 26    """Status of a variable/constraint in a LP basis.
 27
 28    Attributes:
 29      FREE: The variable/constraint is free (it has no finite bounds).
 30      AT_LOWER_BOUND: The variable/constraint is at its lower bound (which must be
 31        finite).
 32      AT_UPPER_BOUND: The variable/constraint is at its upper bound (which must be
 33        finite).
 34      FIXED_VALUE: The variable/constraint has identical finite lower and upper
 35        bounds.
 36      BASIC: The variable/constraint is basic.
 37    """
 38
 39    FREE = solution_pb2.BASIS_STATUS_FREE
 40    AT_LOWER_BOUND = solution_pb2.BASIS_STATUS_AT_LOWER_BOUND
 41    AT_UPPER_BOUND = solution_pb2.BASIS_STATUS_AT_UPPER_BOUND
 42    FIXED_VALUE = solution_pb2.BASIS_STATUS_FIXED_VALUE
 43    BASIC = solution_pb2.BASIS_STATUS_BASIC
 44
 45
 46@enum.unique
 47class SolutionStatus(enum.Enum):
 48    """Feasibility of a primal or dual solution as claimed by the solver.
 49
 50    Attributes:
 51      UNDETERMINED: Solver does not claim a feasibility status.
 52      FEASIBLE: Solver claims the solution is feasible.
 53      INFEASIBLE: Solver claims the solution is infeasible.
 54    """
 55
 56    UNDETERMINED = solution_pb2.SOLUTION_STATUS_UNDETERMINED
 57    FEASIBLE = solution_pb2.SOLUTION_STATUS_FEASIBLE
 58    INFEASIBLE = solution_pb2.SOLUTION_STATUS_INFEASIBLE
 59
 60
 61def parse_optional_solution_status(
 62    proto: solution_pb2.SolutionStatusProto,
 63) -> Optional[SolutionStatus]:
 64    """Converts a proto SolutionStatus to an optional Python SolutionStatus."""
 65    return (
 66        None
 67        if proto == solution_pb2.SOLUTION_STATUS_UNSPECIFIED
 68        else SolutionStatus(proto)
 69    )
 70
 71
 72def optional_solution_status_to_proto(
 73    status: Optional[SolutionStatus],
 74) -> solution_pb2.SolutionStatusProto:
 75    """Converts an optional Python SolutionStatus to a proto SolutionStatus."""
 76    return solution_pb2.SOLUTION_STATUS_UNSPECIFIED if status is None else status.value
 77
 78
 79@dataclasses.dataclass
 80class PrimalSolution:
 81    """A solution to the optimization problem in a Model.
 82
 83    E.g. consider a simple linear program:
 84      min c * x
 85      s.t. A * x >= b
 86      x >= 0.
 87    A primal solution is assignment values to x. It is feasible if it satisfies
 88    A * x >= b and x >= 0 from above. In the class PrimalSolution variable_values
 89    is x and objective_value is c * x.
 90
 91    For the general case of a MathOpt optimization model, see go/mathopt-solutions
 92    for details.
 93
 94    Attributes:
 95      variable_values: The value assigned for each Variable in the model.
 96      objective_value: The value of the objective value at this solution. This
 97        value may not be always populated.
 98      feasibility_status: The feasibility of the solution as claimed by the
 99        solver.
100    """
101
102    variable_values: Dict[model.Variable, float] = dataclasses.field(
103        default_factory=dict
104    )
105    objective_value: float = 0.0
106    feasibility_status: SolutionStatus = SolutionStatus.UNDETERMINED
107
108    def to_proto(self) -> solution_pb2.PrimalSolutionProto:
109        """Returns an equivalent proto for a primal solution."""
110        return solution_pb2.PrimalSolutionProto(
111            variable_values=sparse_containers.to_sparse_double_vector_proto(
112                self.variable_values
113            ),
114            objective_value=self.objective_value,
115            feasibility_status=self.feasibility_status.value,
116        )
117
118
119def parse_primal_solution(
120    proto: solution_pb2.PrimalSolutionProto, mod: model.Model
121) -> PrimalSolution:
122    """Returns an equivalent PrimalSolution from the input proto."""
123    result = PrimalSolution()
124    result.objective_value = proto.objective_value
125    result.variable_values = sparse_containers.parse_variable_map(
126        proto.variable_values, mod
127    )
128    status_proto = proto.feasibility_status
129    if status_proto == solution_pb2.SOLUTION_STATUS_UNSPECIFIED:
130        raise ValueError("Primal solution feasibility status should not be UNSPECIFIED")
131    result.feasibility_status = SolutionStatus(status_proto)
132    return result
133
134
135@dataclasses.dataclass
136class PrimalRay:
137    """A direction of unbounded objective improvement in an optimization Model.
138
139    Equivalently, a certificate of infeasibility for the dual of the optimization
140    problem.
141
142    E.g. consider a simple linear program:
143      min c * x
144      s.t. A * x >= b
145      x >= 0.
146    A primal ray is an x that satisfies:
147      c * x < 0
148      A * x >= 0
149      x >= 0.
150    Observe that given a feasible solution, any positive multiple of the primal
151    ray plus that solution is still feasible, and gives a better objective
152    value. A primal ray also proves the dual optimization problem infeasible.
153
154    In the class PrimalRay, variable_values is this x.
155
156    For the general case of a MathOpt optimization model, see
157    go/mathopt-solutions for details.
158
159    Attributes:
160      variable_values: The value assigned for each Variable in the model.
161    """
162
163    variable_values: Dict[model.Variable, float] = dataclasses.field(
164        default_factory=dict
165    )
166
167
168def parse_primal_ray(proto: solution_pb2.PrimalRayProto, mod: model.Model) -> PrimalRay:
169    """Returns an equivalent PrimalRay from the input proto."""
170    result = PrimalRay()
171    result.variable_values = sparse_containers.parse_variable_map(
172        proto.variable_values, mod
173    )
174    return result
175
176
177@dataclasses.dataclass
178class DualSolution:
179    """A solution to the dual of the optimization problem given by a Model.
180
181    E.g. consider the primal dual pair linear program pair:
182      (Primal)              (Dual)
183      min c * x             max b * y
184      s.t. A * x >= b       s.t. y * A + r = c
185      x >= 0                y, r >= 0.
186    The dual solution is the pair (y, r). It is feasible if it satisfies the
187    constraints from (Dual) above.
188
189    Below, y is dual_values, r is reduced_costs, and b * y is objective_value.
190
191    For the general case, see go/mathopt-solutions and go/mathopt-dual (and note
192    that the dual objective depends on r in the general case).
193
194    Attributes:
195      dual_values: The value assigned for each LinearConstraint in the model.
196      reduced_costs: The value assigned for each Variable in the model.
197      objective_value: The value of the dual objective value at this solution.
198        This value may not be always populated.
199      feasibility_status: The feasibility of the solution as claimed by the
200        solver.
201    """
202
203    dual_values: Dict[model.LinearConstraint, float] = dataclasses.field(
204        default_factory=dict
205    )
206    reduced_costs: Dict[model.Variable, float] = dataclasses.field(default_factory=dict)
207    objective_value: Optional[float] = None
208    feasibility_status: SolutionStatus = SolutionStatus.UNDETERMINED
209
210    def to_proto(self) -> solution_pb2.DualSolutionProto:
211        """Returns an equivalent proto for a dual solution."""
212        return solution_pb2.DualSolutionProto(
213            dual_values=sparse_containers.to_sparse_double_vector_proto(
214                self.dual_values
215            ),
216            reduced_costs=sparse_containers.to_sparse_double_vector_proto(
217                self.reduced_costs
218            ),
219            objective_value=self.objective_value,
220            feasibility_status=self.feasibility_status.value,
221        )
222
223
224def parse_dual_solution(
225    proto: solution_pb2.DualSolutionProto, mod: model.Model
226) -> DualSolution:
227    """Returns an equivalent DualSolution from the input proto."""
228    result = DualSolution()
229    result.objective_value = (
230        proto.objective_value if proto.HasField("objective_value") else None
231    )
232    result.dual_values = sparse_containers.parse_linear_constraint_map(
233        proto.dual_values, mod
234    )
235    result.reduced_costs = sparse_containers.parse_variable_map(
236        proto.reduced_costs, mod
237    )
238    status_proto = proto.feasibility_status
239    if status_proto == solution_pb2.SOLUTION_STATUS_UNSPECIFIED:
240        raise ValueError("Dual solution feasibility status should not be UNSPECIFIED")
241    result.feasibility_status = SolutionStatus(status_proto)
242    return result
243
244
245@dataclasses.dataclass
246class DualRay:
247    """A direction of unbounded objective improvement in an optimization Model.
248
249    A direction of unbounded improvement to the dual of an optimization,
250    problem; equivalently, a certificate of primal infeasibility.
251
252    E.g. consider the primal dual pair linear program pair:
253      (Primal)              (Dual)
254      min c * x             max b * y
255      s.t. A * x >= b       s.t. y * A + r = c
256      x >= 0                y, r >= 0.
257
258    The dual ray is the pair (y, r) satisfying:
259      b * y > 0
260      y * A + r = 0
261      y, r >= 0.
262    Observe that adding a positive multiple of (y, r) to dual feasible solution
263    maintains dual feasibility and improves the objective (proving the dual is
264    unbounded). The dual ray also proves the primal problem is infeasible.
265
266    In the class DualRay below, y is dual_values and r is reduced_costs.
267
268    For the general case, see go/mathopt-solutions and go/mathopt-dual (and note
269    that the dual objective depends on r in the general case).
270
271    Attributes:
272      dual_values: The value assigned for each LinearConstraint in the model.
273      reduced_costs: The value assigned for each Variable in the model.
274    """
275
276    dual_values: Dict[model.LinearConstraint, float] = dataclasses.field(
277        default_factory=dict
278    )
279    reduced_costs: Dict[model.Variable, float] = dataclasses.field(default_factory=dict)
280
281
282def parse_dual_ray(proto: solution_pb2.DualRayProto, mod: model.Model) -> DualRay:
283    """Returns an equivalent DualRay from the input proto."""
284    result = DualRay()
285    result.dual_values = sparse_containers.parse_linear_constraint_map(
286        proto.dual_values, mod
287    )
288    result.reduced_costs = sparse_containers.parse_variable_map(
289        proto.reduced_costs, mod
290    )
291    return result
292
293
294@dataclasses.dataclass
295class Basis:
296    """A combinatorial characterization for a solution to a linear program.
297
298    The simplex method for solving linear programs always returns a "basic
299    feasible solution" which can be described combinatorially as a Basis. A basis
300    assigns a BasisStatus for every variable and linear constraint.
301
302    E.g. consider a standard form LP:
303      min c * x
304      s.t. A * x = b
305      x >= 0
306    that has more variables than constraints and with full row rank A.
307
308    Let n be the number of variables and m the number of linear constraints. A
309    valid basis for this problem can be constructed as follows:
310     * All constraints will have basis status FIXED.
311     * Pick m variables such that the columns of A are linearly independent and
312       assign the status BASIC.
313     * Assign the status AT_LOWER for the remaining n - m variables.
314
315    The basic solution for this basis is the unique solution of A * x = b that has
316    all variables with status AT_LOWER fixed to their lower bounds (all zero). The
317    resulting solution is called a basic feasible solution if it also satisfies
318    x >= 0.
319
320    See go/mathopt-basis for treatment of the general case and an explanation of
321    how a dual solution is determined for a basis.
322
323    Attributes:
324      variable_status: The basis status for each variable in the model.
325      constraint_status: The basis status for each linear constraint in the model.
326      basic_dual_feasibility: This is an advanced feature used by MathOpt to
327        characterize feasibility of suboptimal LP solutions (optimal solutions
328        will always have status SolutionStatus.FEASIBLE). For single-sided LPs it
329        should be equal to the feasibility status of the associated dual solution.
330        For two-sided LPs it may be different in some edge cases (e.g. incomplete
331        solves with primal simplex). For more details see
332        go/mathopt-basis-advanced#dualfeasibility. If you are providing a starting
333        basis via ModelSolveParameters.initial_basis, this value is ignored and
334        can be None. It is only relevant for the basis returned by Solution.basis,
335        and it is never None when returned from solve(). This is an advanced
336        status. For single-sided LPs it should be equal to the feasibility status
337        of the associated dual solution. For two-sided LPs it may be different in
338        some edge cases (e.g. incomplete solves with primal simplex). For more
339        details see go/mathopt-basis-advanced#dualfeasibility.
340    """
341
342    variable_status: Dict[model.Variable, BasisStatus] = dataclasses.field(
343        default_factory=dict
344    )
345    constraint_status: Dict[model.LinearConstraint, BasisStatus] = dataclasses.field(
346        default_factory=dict
347    )
348    basic_dual_feasibility: Optional[SolutionStatus] = None
349
350    def to_proto(self) -> solution_pb2.BasisProto:
351        """Returns an equivalent proto for the basis."""
352        return solution_pb2.BasisProto(
353            variable_status=_to_sparse_basis_status_vector_proto(self.variable_status),
354            constraint_status=_to_sparse_basis_status_vector_proto(
355                self.constraint_status
356            ),
357            basic_dual_feasibility=optional_solution_status_to_proto(
358                self.basic_dual_feasibility
359            ),
360        )
361
362
363def parse_basis(proto: solution_pb2.BasisProto, mod: model.Model) -> Basis:
364    """Returns an equivalent Basis to the input proto."""
365    result = Basis()
366    for index, vid in enumerate(proto.variable_status.ids):
367        status_proto = proto.variable_status.values[index]
368        if status_proto == solution_pb2.BASIS_STATUS_UNSPECIFIED:
369            raise ValueError("Variable basis status should not be UNSPECIFIED")
370        result.variable_status[mod.get_variable(vid)] = BasisStatus(status_proto)
371    for index, cid in enumerate(proto.constraint_status.ids):
372        status_proto = proto.constraint_status.values[index]
373        if status_proto == solution_pb2.BASIS_STATUS_UNSPECIFIED:
374            raise ValueError("Constraint basis status should not be UNSPECIFIED")
375        result.constraint_status[mod.get_linear_constraint(cid)] = BasisStatus(
376            status_proto
377        )
378    result.basic_dual_feasibility = parse_optional_solution_status(
379        proto.basic_dual_feasibility
380    )
381    return result
382
383
384T = TypeVar("T", model.Variable, model.LinearConstraint)
385
386
387def _to_sparse_basis_status_vector_proto(
388    terms: Dict[T, BasisStatus]
389) -> solution_pb2.SparseBasisStatusVector:
390    """Converts a basis vector from a python Dict to a protocol buffer."""
391    result = solution_pb2.SparseBasisStatusVector()
392    if terms:
393        id_and_status = sorted(
394            (key.id, status.value) for (key, status) in terms.items()
395        )
396        ids, values = zip(*id_and_status)
397        result.ids[:] = ids
398        result.values[:] = values
399    return result
400
401
402@dataclasses.dataclass
403class Solution:
404    """A solution to the optimization problem in a Model."""
405
406    primal_solution: Optional[PrimalSolution] = None
407    dual_solution: Optional[DualSolution] = None
408    basis: Optional[Basis] = None
409
410    def to_proto(self) -> solution_pb2.SolutionProto:
411        """Returns an equivalent proto for a solution."""
412        return solution_pb2.SolutionProto(
413            primal_solution=(
414                self.primal_solution.to_proto()
415                if self.primal_solution is not None
416                else None
417            ),
418            dual_solution=(
419                self.dual_solution.to_proto()
420                if self.dual_solution is not None
421                else None
422            ),
423            basis=self.basis.to_proto() if self.basis is not None else None,
424        )
425
426
427def parse_solution(proto: solution_pb2.SolutionProto, mod: model.Model) -> Solution:
428    """Returns a Solution equivalent to the input proto."""
429    result = Solution()
430    if proto.HasField("primal_solution"):
431        result.primal_solution = parse_primal_solution(proto.primal_solution, mod)
432    if proto.HasField("dual_solution"):
433        result.dual_solution = parse_dual_solution(proto.dual_solution, mod)
434    result.basis = parse_basis(proto.basis, mod) if proto.HasField("basis") else None
435    return result