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 #ifndef OR_TOOLS_LP_DATA_LP_DECOMPOSER_H_ 15 #define OR_TOOLS_LP_DATA_LP_DECOMPOSER_H_ 16 17 #include <memory> 18 #include <vector> 19 20 #include "absl/synchronization/mutex.h" 21 #include "ortools/lp_data/lp_data.h" 22 #include "ortools/lp_data/lp_types.h" 23 24 namespace operations_research { 25 namespace glop { 26 27 // This class is used to decompose an existing LinearProgram into several 28 // independent LinearPrograms. Problems are independent when none of their 29 // variables are connected, i.e. appear in the same constraints. 30 // Consider for instance the following problem: 31 // min: x + 2 y + 3 z + 4 t + 5 u 32 // c1: 0 <= x + z <= 1; 33 // c2: 0 <= y + t <= 1; 34 // c3: 0 <= x + u <= 1; 35 // int: x, y, z, t, u 36 // Variables x, z and u are connected by constraints c1 and c3. 37 // Variables y and t are connected by constraints c2. 38 // The problem can be decomposed into two independent problems: 39 // min: x + 3 z + 5 u 40 // c1: 0 <= x + z <= 1; 41 // c3: 0 <= x + u <= 1; 42 // int: x, z, u 43 // and 44 // min: 2 y + 4 t 45 // c2: 0 <= y + t <= 1; 46 // int: y, t 47 // 48 // Note that a solution to those two independent problems is a solution to the 49 // original problem. 50 class LPDecomposer { 51 public: 52 LPDecomposer(); 53 54 // Decomposes the problem into independent problems. 55 // Note that a pointer is kept (no copy) on the linear_problem, so the problem 56 // should not change during the life of the LPDecomposer object. 57 void Decompose(const LinearProgram* linear_problem) 58 ABSL_LOCKS_EXCLUDED(mutex_); 59 60 // Returns the number of independent problems generated by Decompose(). 61 int GetNumberOfProblems() const ABSL_LOCKS_EXCLUDED(mutex_); 62 63 // Returns the original problem, i.e. as it was before any decomposition. 64 const LinearProgram& original_problem() const ABSL_LOCKS_EXCLUDED(mutex_); 65 66 // Fills lp with the problem_index^th independent problem generated by 67 // Decompose(). 68 // Note that this method runs in O(num-entries-in-generated-problem). 69 void ExtractLocalProblem(int problem_index, LinearProgram* lp) 70 ABSL_LOCKS_EXCLUDED(mutex_); 71 72 // Returns an assignment to the original problem based on the assignments 73 // to the independent problems. Requires Decompose() to have been called. 74 DenseRow AggregateAssignments(const std::vector<DenseRow>& assignments) const 75 ABSL_LOCKS_EXCLUDED(mutex_); 76 77 // Returns an assignment to the given subproblem based on the assignment to 78 // the original problem. Requires Decompose() to have been called. 79 DenseRow ExtractLocalAssignment(int problem_index, const DenseRow& assignment) 80 ABSL_LOCKS_EXCLUDED(mutex_); 81 82 private: 83 const LinearProgram* original_problem_; 84 std::vector<std::vector<ColIndex>> clusters_; 85 86 mutable absl::Mutex mutex_; 87 88 DISALLOW_COPY_AND_ASSIGN(LPDecomposer); 89 }; 90 91 } // namespace glop 92 } // namespace operations_research 93 94 #endif // OR_TOOLS_LP_DATA_LP_DECOMPOSER_H_ 95