1 // Copyright 2010-2021 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 //
15 // Utilities used by frequency_assignment_problem.cc.
16 //
17
18 #ifndef OR_TOOLS_EXAMPLES_FAP_UTILITIES_H_
19 #define OR_TOOLS_EXAMPLES_FAP_UTILITIES_H_
20
21 #include <cstdint>
22 #include <map>
23 #include <set>
24 #include <vector>
25
26 #include "absl/strings/str_format.h"
27 #include "examples/cpp/fap_parser.h"
28 #include "ortools/base/logging.h"
29 #include "ortools/base/map_util.h"
30 #include "ortools/constraint_solver/constraint_solver.h"
31
32 namespace operations_research {
33
34 // Checks if the solution given from the Solver satisfies all
35 // the hard binary constraints specified in the ctr.txt.
36 bool CheckConstraintSatisfaction(
37 const std::vector<FapConstraint>& data_constraints,
38 const std::vector<int>& variables,
39 const std::map<int, int>& index_from_key);
40
41 // Checks if the solution given from the Solver has not modified the values of
42 // the variables that were initially assigned and denoted as hard in var.txt.
43 bool CheckVariablePosition(const std::map<int, FapVariable>& data_variables,
44 const std::vector<int>& variables,
45 const std::map<int, int>& index_from_key);
46
47 // Counts the number of different values in the variable vector.
48 int NumberOfAssignedValues(const std::vector<int>& variables);
49
50 // Prints the duration of the solving process.
51 void PrintElapsedTime(const int64_t time1, const int64_t time2);
52
53 // Prints the solution found by the Hard Solver for feasible instances.
54 void PrintResultsHard(SolutionCollector* const collector,
55 const std::vector<IntVar*>& variables,
56 IntVar* const objective_var,
57 const std::map<int, FapVariable>& data_variables,
58 const std::vector<FapConstraint>& data_constraints,
59 const std::map<int, int>& index_from_key,
60 const std::vector<int>& key_from_index);
61
62 // Prints the solution found by the Soft Solver for unfeasible instances.
63 void PrintResultsSoft(SolutionCollector* const collector,
64 const std::vector<IntVar*>& variables,
65 IntVar* const total_cost,
66 const std::map<int, FapVariable>& hard_variables,
67 const std::vector<FapConstraint>& hard_constraints,
68 const std::map<int, FapVariable>& soft_variables,
69 const std::vector<FapConstraint>& soft_constraints,
70 const std::map<int, int>& index_from_key,
71 const std::vector<int>& key_from_index);
72
CheckConstraintSatisfaction(const std::vector<FapConstraint> & data_constraints,const std::vector<int> & variables,const std::map<int,int> & index_from_key)73 bool CheckConstraintSatisfaction(
74 const std::vector<FapConstraint>& data_constraints,
75 const std::vector<int>& variables,
76 const std::map<int, int>& index_from_key) {
77 bool status = true;
78 for (const FapConstraint& ct : data_constraints) {
79 const int index1 = gtl::FindOrDie(index_from_key, ct.variable1);
80 const int index2 = gtl::FindOrDie(index_from_key, ct.variable2);
81 CHECK_LT(index1, variables.size());
82 CHECK_LT(index2, variables.size());
83 const int var1 = variables[index1];
84 const int var2 = variables[index2];
85 const int absolute_difference = abs(var1 - var2);
86
87 if ((ct.operation == ">") && (absolute_difference <= ct.value)) {
88 LOG(INFO) << " Violation of contraint between variable " << ct.variable1
89 << " and variable " << ct.variable2 << ".";
90 LOG(INFO) << " Expected |" << var1 << " - " << var2
91 << "| (= " << absolute_difference << ") > " << ct.value << ".";
92 status = false;
93 } else if ((ct.operation == "=") && (absolute_difference != ct.value)) {
94 LOG(INFO) << " Violation of contraint between variable " << ct.variable1
95 << " and variable " << ct.variable2 << ".";
96 LOG(INFO) << " Expected |" << var1 << " - " << var2
97 << "| (= " << absolute_difference << ") = " << ct.value << ".";
98 status = false;
99 }
100 }
101 return status;
102 }
103
CheckVariablePosition(const std::map<int,FapVariable> & data_variables,const std::vector<int> & variables,const std::map<int,int> & index_from_key)104 bool CheckVariablePosition(const std::map<int, FapVariable>& data_variables,
105 const std::vector<int>& variables,
106 const std::map<int, int>& index_from_key) {
107 bool status = true;
108 for (const auto& it : data_variables) {
109 const int index = gtl::FindOrDie(index_from_key, it.first);
110 CHECK_LT(index, variables.size());
111 const int var = variables[index];
112
113 if (it.second.hard && (it.second.initial_position != -1) &&
114 (var != it.second.initial_position)) {
115 LOG(INFO) << " Change of position of hard variable " << it.first << ".";
116 LOG(INFO) << " Expected " << it.second.initial_position
117 << " instead of given " << var << ".";
118 status = false;
119 }
120 }
121 return status;
122 }
123
NumberOfAssignedValues(const std::vector<int> & variables)124 int NumberOfAssignedValues(const std::vector<int>& variables) {
125 std::set<int> assigned(variables.begin(), variables.end());
126 return static_cast<int>(assigned.size());
127 }
128
PrintElapsedTime(const int64_t time1,const int64_t time2)129 void PrintElapsedTime(const int64_t time1, const int64_t time2) {
130 LOG(INFO) << "End of solving process.";
131 LOG(INFO) << "The Solve method took " << (time2 - time1) / 1000.0
132 << " seconds.";
133 }
134
PrintResultsHard(SolutionCollector * const collector,const std::vector<IntVar * > & variables,IntVar * const objective_var,const std::map<int,FapVariable> & data_variables,const std::vector<FapConstraint> & data_constraints,const std::map<int,int> & index_from_key,const std::vector<int> & key_from_index)135 void PrintResultsHard(SolutionCollector* const collector,
136 const std::vector<IntVar*>& variables,
137 IntVar* const objective_var,
138 const std::map<int, FapVariable>& data_variables,
139 const std::vector<FapConstraint>& data_constraints,
140 const std::map<int, int>& index_from_key,
141 const std::vector<int>& key_from_index) {
142 LOG(INFO) << "Printing...";
143 LOG(INFO) << "Number of Solutions: " << collector->solution_count();
144 for (int solution_index = 0; solution_index < collector->solution_count();
145 ++solution_index) {
146 Assignment* const solution = collector->solution(solution_index);
147 std::vector<int> results(variables.size());
148 LOG(INFO) << "------------------------------------------------------------";
149 LOG(INFO) << "Solution " << solution_index + 1;
150 LOG(INFO) << "Cost: " << solution->Value(objective_var);
151 for (int i = 0; i < variables.size(); ++i) {
152 results[i] = solution->Value(variables[i]);
153 LOG(INFO) << " Variable " << key_from_index[i] << ": " << results[i];
154 }
155 if (CheckConstraintSatisfaction(data_constraints, results,
156 index_from_key)) {
157 LOG(INFO) << "All hard constraints satisfied.";
158 } else {
159 LOG(INFO) << "Warning! Hard constraint violation detected.";
160 }
161 if (CheckVariablePosition(data_variables, results, index_from_key)) {
162 LOG(INFO) << "All hard variables stayed unharmed.";
163 } else {
164 LOG(INFO) << "Warning! Hard variable modification detected.";
165 }
166
167 LOG(INFO) << "Values used: " << NumberOfAssignedValues(results);
168 LOG(INFO) << "Maximum value used: "
169 << *std::max_element(results.begin(), results.end());
170 LOG(INFO) << " Failures: " << collector->failures(solution_index);
171 }
172 LOG(INFO) << " ============================================================";
173 }
174
PrintResultsSoft(SolutionCollector * const collector,const std::vector<IntVar * > & variables,IntVar * const total_cost,const std::map<int,FapVariable> & hard_variables,const std::vector<FapConstraint> & hard_constraints,const std::map<int,FapVariable> & soft_variables,const std::vector<FapConstraint> & soft_constraints,const std::map<int,int> & index_from_key,const std::vector<int> & key_from_index)175 void PrintResultsSoft(SolutionCollector* const collector,
176 const std::vector<IntVar*>& variables,
177 IntVar* const total_cost,
178 const std::map<int, FapVariable>& hard_variables,
179 const std::vector<FapConstraint>& hard_constraints,
180 const std::map<int, FapVariable>& soft_variables,
181 const std::vector<FapConstraint>& soft_constraints,
182 const std::map<int, int>& index_from_key,
183 const std::vector<int>& key_from_index) {
184 LOG(INFO) << "Printing...";
185 LOG(INFO) << "Number of Solutions: " << collector->solution_count();
186 for (int solution_index = 0; solution_index < collector->solution_count();
187 ++solution_index) {
188 Assignment* const solution = collector->solution(solution_index);
189 std::vector<int> results(variables.size());
190 LOG(INFO) << "------------------------------------------------------------";
191 LOG(INFO) << "Solution";
192 for (int i = 0; i < variables.size(); ++i) {
193 results[i] = solution->Value(variables[i]);
194 LOG(INFO) << " Variable " << key_from_index[i] << ": " << results[i];
195 }
196 if (CheckConstraintSatisfaction(hard_constraints, results,
197 index_from_key)) {
198 LOG(INFO) << "All hard constraints satisfied.";
199 } else {
200 LOG(INFO) << "Warning! Hard constraint violation detected.";
201 }
202 if (CheckVariablePosition(hard_variables, results, index_from_key)) {
203 LOG(INFO) << "All hard variables stayed unharmed.";
204 } else {
205 LOG(INFO) << "Warning! Hard constraint violation detected.";
206 }
207
208 if (CheckConstraintSatisfaction(soft_constraints, results,
209 index_from_key) &&
210 CheckVariablePosition(soft_variables, results, index_from_key)) {
211 LOG(INFO) << "Problem feasible: "
212 "Soft constraints and soft variables satisfied.";
213 LOG(INFO) << " Weighted Sum: " << solution->Value(total_cost);
214 } else {
215 LOG(INFO) << "Problem unfeasible. Optimized weighted sum of violations.";
216 LOG(INFO) << " Weighted Sum: " << solution->Value(total_cost);
217 }
218
219 LOG(INFO) << "Values used: " << NumberOfAssignedValues(results);
220 LOG(INFO) << "Maximum value used: "
221 << *std::max_element(results.begin(), results.end());
222 LOG(INFO) << " Failures: " << collector->failures(solution_index);
223 }
224 LOG(INFO) << " ============================================================";
225 }
226
227 } // namespace operations_research
228 #endif // OR_TOOLS_EXAMPLES_FAP_UTILITIES_H_
229