Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
solution.cc
Go to the documentation of this file.
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
15
16#include <optional>
17#include <utility>
18
19#include "absl/container/flat_hash_map.h"
20#include "absl/log/check.h"
21#include "absl/log/log.h"
22#include "absl/status/status.h"
23#include "absl/strings/string_view.h"
24#include "absl/types/span.h"
33
34namespace operations_research {
35namespace math_opt {
36
37std::optional<absl::string_view> Enum<SolutionStatus>::ToOptString(
38 SolutionStatus value) {
39 switch (value) {
41 return "feasible";
43 return "infeasible";
45 return "undetermined";
46 }
47 return std::nullopt;
48}
49
50absl::Span<const SolutionStatus> Enum<SolutionStatus>::AllValues() {
51 static constexpr SolutionStatus kSolutionStatusValues[] = {
55 };
56 return absl::MakeConstSpan(kSolutionStatusValues);
57}
58
59absl::StatusOr<PrimalSolution> PrimalSolution::FromProto(
60 const ModelStorageCPtr model,
61 const PrimalSolutionProto& primal_solution_proto) {
62 PrimalSolution primal_solution;
64 primal_solution.variable_values,
65 VariableValuesFromProto(model, primal_solution_proto.variable_values()),
66 _ << "invalid variable_values");
67 primal_solution.objective_value = primal_solution_proto.objective_value();
69 primal_solution.auxiliary_objective_values,
71 model, primal_solution_proto.auxiliary_objective_values()),
72 _ << "invalid auxiliary_objective_values");
73 const std::optional<SolutionStatus> feasibility_status =
74 EnumFromProto(primal_solution_proto.feasibility_status());
75 if (!feasibility_status.has_value()) {
76 return absl::InvalidArgumentError("feasibility_status must be specified");
77 }
78 primal_solution.feasibility_status = *feasibility_status;
79 return primal_solution;
80}
81
91
92double PrimalSolution::get_objective_value(const Objective objective) const {
93 if (!variable_values.empty()) {
94 // Here we assume all keys are in the same storage. As PrimalSolution is not
95 // properly encapsulated, we can't maintain a ModelStorage pointer and
96 // iterating on all keys would have a too high cost.
97 CHECK_EQ(variable_values.begin()->first.storage(), objective.storage());
98 }
99 if (!objective.is_primary()) {
100 CHECK(auxiliary_objective_values.contains(objective));
101 return auxiliary_objective_values.at(objective);
102 }
103 return objective_value;
104}
105
106absl::StatusOr<PrimalRay> PrimalRay::FromProto(
107 const ModelStorageCPtr model, const PrimalRayProto& primal_ray_proto) {
108 PrimalRay result;
110 result.variable_values,
111 VariableValuesFromProto(model, primal_ray_proto.variable_values()),
112 _ << "invalid variable_values");
113 return result;
114}
115
121
122absl::StatusOr<DualSolution> DualSolution::FromProto(
123 const ModelStorageCPtr model,
124 const DualSolutionProto& dual_solution_proto) {
125 DualSolution dual_solution;
127 dual_solution.dual_values,
128 LinearConstraintValuesFromProto(model, dual_solution_proto.dual_values()),
129 _ << "invalid dual_values");
132 model, dual_solution_proto.quadratic_dual_values()),
133 _ << "invalid quadratic_dual_values");
135 dual_solution.reduced_costs,
136 VariableValuesFromProto(model, dual_solution_proto.reduced_costs()),
137 _ << "invalid reduced_costs");
138 if (dual_solution_proto.has_objective_value()) {
139 dual_solution.objective_value = dual_solution_proto.objective_value();
140 }
141 const std::optional<SolutionStatus> feasibility_status =
142 EnumFromProto(dual_solution_proto.feasibility_status());
143 if (!feasibility_status.has_value()) {
144 return absl::InvalidArgumentError("feasibility_status must be specified");
145 }
146 dual_solution.feasibility_status = *feasibility_status;
147 return dual_solution;
148}
149
162
163absl::StatusOr<DualRay> DualRay::FromProto(const ModelStorageCPtr model,
164 const DualRayProto& dual_ray_proto) {
165 DualRay result;
167 result.dual_values,
168 LinearConstraintValuesFromProto(model, dual_ray_proto.dual_values()),
169 _ << "invalid dual_values");
171 result.reduced_costs,
172 VariableValuesFromProto(model, dual_ray_proto.reduced_costs()),
173 _ << "invalid reduced_costs");
174 return result;
175}
176
183
184absl::StatusOr<Basis> Basis::FromProto(const ModelStorageCPtr model,
185 const BasisProto& basis_proto) {
186 Basis basis;
188 basis.constraint_status,
190 _ << "invalid constraint_status");
192 basis.variable_status,
193 VariableBasisFromProto(model, basis_proto.variable_status()),
194 _ << "invalid variable_status");
197 return basis;
198}
199
201 const ModelStorageCPtr expected_storage) const {
202 for (const auto& [v, _] : variable_status) {
204 internal::CheckModelStorage(/*storage=*/v.storage(),
205 /*expected_storage=*/expected_storage))
206 << "invalid variable " << v << " in variable_status";
207 }
208 for (const auto& [c, _] : constraint_status) {
210 internal::CheckModelStorage(/*storage=*/c.storage(),
211 /*expected_storage=*/expected_storage))
212 << "invalid constraint " << c << " in constraint_status";
213 }
214 return absl::OkStatus();
215}
216
225
226absl::StatusOr<Solution> Solution::FromProto(
227 const ModelStorageCPtr model, const SolutionProto& solution_proto) {
229 if (solution_proto.has_primal_solution()) {
231 solution.primal_solution,
232 PrimalSolution::FromProto(model, solution_proto.primal_solution()),
233 _ << "invalid primal_solution");
234 }
235 if (solution_proto.has_dual_solution()) {
237 solution.dual_solution,
238 DualSolution::FromProto(model, solution_proto.dual_solution()),
239 _ << "invalid dual_solution");
240 }
241 if (solution_proto.has_basis()) {
243 Basis::FromProto(model, solution_proto.basis()),
244 _ << "invalid basis");
245 }
246 return solution;
247}
248
250 SolutionProto result;
251 if (primal_solution.has_value()) {
252 *result.mutable_primal_solution() = primal_solution->Proto();
253 }
254 if (dual_solution.has_value()) {
255 *result.mutable_dual_solution() = dual_solution->Proto();
256 }
257 if (basis.has_value()) {
258 *result.mutable_basis() = basis->Proto();
259 }
260 return result;
261}
262
263} // namespace math_opt
264} // namespace operations_research
#define RETURN_IF_ERROR(expr)
void set_basic_dual_feasibility(::operations_research::math_opt::SolutionStatusProto value)
const ::operations_research::math_opt::SparseBasisStatusVector & variable_status() const
::operations_research::math_opt::SparseBasisStatusVector *PROTOBUF_NONNULL mutable_constraint_status()
const ::operations_research::math_opt::SparseBasisStatusVector & constraint_status() const
::operations_research::math_opt::SolutionStatusProto basic_dual_feasibility() const
::operations_research::math_opt::SparseBasisStatusVector *PROTOBUF_NONNULL mutable_variable_status()
const ::operations_research::math_opt::SparseDoubleVectorProto & dual_values() const
::operations_research::math_opt::SparseDoubleVectorProto *PROTOBUF_NONNULL mutable_dual_values()
const ::operations_research::math_opt::SparseDoubleVectorProto & reduced_costs() const
::operations_research::math_opt::SparseDoubleVectorProto *PROTOBUF_NONNULL mutable_reduced_costs()
const ::operations_research::math_opt::SparseDoubleVectorProto & dual_values() const
::operations_research::math_opt::SolutionStatusProto feasibility_status() const
::operations_research::math_opt::SparseDoubleVectorProto *PROTOBUF_NONNULL mutable_reduced_costs()
bool has_objective_value() const
optional double objective_value = 3;
::operations_research::math_opt::SparseDoubleVectorProto *PROTOBUF_NONNULL mutable_dual_values()
void set_feasibility_status(::operations_research::math_opt::SolutionStatusProto value)
const ::operations_research::math_opt::SparseDoubleVectorProto & reduced_costs() const
::operations_research::math_opt::SparseDoubleVectorProto *PROTOBUF_NONNULL mutable_quadratic_dual_values()
const ::operations_research::math_opt::SparseDoubleVectorProto & quadratic_dual_values() const
const ::operations_research::math_opt::SparseDoubleVectorProto & variable_values() const
::operations_research::math_opt::SparseDoubleVectorProto *PROTOBUF_NONNULL mutable_variable_values()
const ::google::protobuf::Map<::int64_t, double > & auxiliary_objective_values() const
::operations_research::math_opt::SolutionStatusProto feasibility_status() const
::operations_research::math_opt::SparseDoubleVectorProto *PROTOBUF_NONNULL mutable_variable_values()
const ::operations_research::math_opt::SparseDoubleVectorProto & variable_values() const
void set_feasibility_status(::operations_research::math_opt::SolutionStatusProto value)
::google::protobuf::Map<::int64_t, double > *PROTOBUF_NONNULL mutable_auxiliary_objective_values()
bool has_primal_solution() const
optional .operations_research.math_opt.PrimalSolutionProto primal_solution = 1;
const ::operations_research::math_opt::BasisProto & basis() const
::operations_research::math_opt::DualSolutionProto *PROTOBUF_NONNULL mutable_dual_solution()
::operations_research::math_opt::PrimalSolutionProto *PROTOBUF_NONNULL mutable_primal_solution()
bool has_dual_solution() const
optional .operations_research.math_opt.DualSolutionProto dual_solution = 2;
bool has_basis() const
optional .operations_research.math_opt.BasisProto basis = 3;
::operations_research::math_opt::BasisProto *PROTOBUF_NONNULL mutable_basis()
const ::operations_research::math_opt::DualSolutionProto & dual_solution() const
const ::operations_research::math_opt::PrimalSolutionProto & primal_solution() const
absl::Status CheckModelStorage(const NullableModelStorageCPtr storage, const ModelStorageCPtr expected_storage)
Definition key_types.h:169
An object oriented wrapper for quadratic constraints in ModelStorage.
Definition gurobi_isv.cc:28
google::protobuf::Map< int64_t, double > AuxiliaryObjectiveValuesToProto(const absl::flat_hash_map< Objective, double > &aux_obj_values)
absl::Nonnull< const ModelStorage * > ModelStorageCPtr
SparseDoubleVectorProto LinearConstraintValuesToProto(const LinearConstraintMap< double > &linear_constraint_values)
Returns the proto equivalent of linear_constraint_values.
absl::StatusOr< LinearConstraintMap< double > > LinearConstraintValuesFromProto(const ModelStorageCPtr model, const SparseDoubleVectorProto &lin_cons_proto)
absl::StatusOr< absl::flat_hash_map< Objective, double > > AuxiliaryObjectiveValuesFromProto(const ModelStorageCPtr model, const google::protobuf::Map< int64_t, double > &aux_obj_proto)
std::optional< typename EnumProto< P >::Cpp > EnumFromProto(P proto_value)
Definition enums.h:281
SolutionStatus
Feasibility of a primal or dual solution as claimed by the solver.
Definition solution.h:39
@ kUndetermined
Solver does not claim a feasibility status.
Definition solution.h:41
@ kFeasible
Solver claims the solution is feasible.
Definition solution.h:44
@ kInfeasible
Solver claims the solution is infeasible.
Definition solution.h:47
SparseBasisStatusVector VariableBasisToProto(const VariableMap< BasisStatus > &basis_values)
Returns the proto equivalent of basis_values.
absl::StatusOr< LinearConstraintMap< BasisStatus > > LinearConstraintBasisFromProto(const ModelStorageCPtr model, const SparseBasisStatusVector &basis_proto)
absl::StatusOr< absl::flat_hash_map< QuadraticConstraint, double > > QuadraticConstraintValuesFromProto(const ModelStorageCPtr model, const SparseDoubleVectorProto &quad_cons_proto)
SparseBasisStatusVector LinearConstraintBasisToProto(const LinearConstraintMap< BasisStatus > &basis_values)
Returns the proto equivalent of basis_values.
SparseDoubleVectorProto VariableValuesToProto(const VariableMap< double > &variable_values)
Returns the proto equivalent of variable_values.
absl::StatusOr< VariableMap< BasisStatus > > VariableBasisFromProto(const ModelStorageCPtr model, const SparseBasisStatusVector &basis_proto)
SparseDoubleVectorProto QuadraticConstraintValuesToProto(const absl::flat_hash_map< QuadraticConstraint, double > &quadratic_constraint_values)
Returns the proto equivalent of quadratic_constraint_values.
Enum< E >::Proto EnumToProto(std::optional< E > value)
Definition enums.h:270
absl::StatusOr< VariableMap< double > > VariableValuesFromProto(const ModelStorageCPtr model, const SparseDoubleVectorProto &vars_proto)
In SWIG mode, we don't want anything besides these top-level includes.
Select next search node to expand Select next item_i to add this new search node to the search Generate a new search node where item_i is not in the knapsack Check validity of this new partial solution(using propagators) - If valid
absl::Status CheckModelStorage(ModelStorageCPtr expected_storage) const
Definition solution.cc:200
LinearConstraintMap< BasisStatus > constraint_status
Definition solution.h:233
VariableMap< BasisStatus > variable_status
Definition solution.h:234
std::optional< SolutionStatus > basic_dual_feasibility
Definition solution.h:248
static absl::StatusOr< Basis > FromProto(ModelStorageCPtr model, const BasisProto &basis_proto)
Definition solution.cc:184
DualRayProto Proto() const
Returns the proto equivalent of this.
Definition solution.cc:177
static absl::StatusOr< DualRay > FromProto(ModelStorageCPtr model, const DualRayProto &dual_ray_proto)
Definition solution.cc:163
LinearConstraintMap< double > dual_values
Definition solution.h:187
VariableMap< double > reduced_costs
Definition solution.h:188
LinearConstraintMap< double > dual_values
Definition solution.h:146
static absl::StatusOr< DualSolution > FromProto(ModelStorageCPtr model, const DualSolutionProto &dual_solution_proto)
Definition solution.cc:122
absl::flat_hash_map< QuadraticConstraint, double > quadratic_dual_values
Definition solution.h:151
std::optional< double > objective_value
Definition solution.h:153
DualSolutionProto Proto() const
Returns the proto equivalent of this.
Definition solution.cc:150
static absl::Span< const E > AllValues()
Returns all possible values of the enum.
static std::optional< absl::string_view > ToOptString(E value)
PrimalRayProto Proto() const
Returns the proto equivalent of this.
Definition solution.cc:116
VariableMap< double > variable_values
Definition solution.h:119
static absl::StatusOr< PrimalRay > FromProto(ModelStorageCPtr model, const PrimalRayProto &primal_ray_proto)
Definition solution.cc:106
absl::flat_hash_map< Objective, double > auxiliary_objective_values
Definition solution.h:84
PrimalSolutionProto Proto() const
Returns the proto equivalent of this.
Definition solution.cc:82
static absl::StatusOr< PrimalSolution > FromProto(ModelStorageCPtr model, const PrimalSolutionProto &primal_solution_proto)
Definition solution.cc:59
double get_objective_value(Objective objective) const
Definition solution.cc:92
std::optional< PrimalSolution > primal_solution
Definition solution.h:269
std::optional< DualSolution > dual_solution
Definition solution.h:270
SolutionProto Proto() const
Returns the proto equivalent of this.
Definition solution.cc:249
static absl::StatusOr< Solution > FromProto(ModelStorageCPtr model, const SolutionProto &solution_proto)
Definition solution.cc:226
#define OR_ASSIGN_OR_RETURN3(lhs, rexpr, error_expression)