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 #include "ortools/lp_data/lp_decomposer.h"
15
16 #include <vector>
17
18 #include "absl/synchronization/mutex.h"
19 #include "ortools/algorithms/dynamic_partition.h"
20 #include "ortools/lp_data/lp_data.h"
21 #include "ortools/lp_data/lp_utils.h"
22
23 namespace operations_research {
24 namespace glop {
25
26 //------------------------------------------------------------------------------
27 // LPDecomposer
28 //------------------------------------------------------------------------------
LPDecomposer()29 LPDecomposer::LPDecomposer()
30 : original_problem_(nullptr), clusters_(), mutex_() {}
31
Decompose(const LinearProgram * linear_problem)32 void LPDecomposer::Decompose(const LinearProgram* linear_problem) {
33 absl::MutexLock mutex_lock(&mutex_);
34 original_problem_ = linear_problem;
35 clusters_.clear();
36
37 const SparseMatrix& transposed_matrix =
38 original_problem_->GetTransposeSparseMatrix();
39 MergingPartition partition(original_problem_->num_variables().value());
40
41 // Iterate on all constraints, and merge all variables of each constraint.
42 const ColIndex num_ct = RowToColIndex(original_problem_->num_constraints());
43 for (ColIndex ct(0); ct < num_ct; ++ct) {
44 const SparseColumn& sparse_constraint = transposed_matrix.column(ct);
45 if (sparse_constraint.num_entries() > 1) {
46 const RowIndex first_row = sparse_constraint.GetFirstRow();
47 for (EntryIndex e(1); e < sparse_constraint.num_entries(); ++e) {
48 partition.MergePartsOf(first_row.value(),
49 sparse_constraint.EntryRow(e).value());
50 }
51 }
52 }
53
54 std::vector<int> classes;
55 const int num_classes = partition.FillEquivalenceClasses(&classes);
56 clusters_.resize(num_classes);
57 for (int i = 0; i < classes.size(); ++i) {
58 clusters_[classes[i]].push_back(ColIndex(i));
59 }
60 for (int i = 0; i < num_classes; ++i) {
61 std::sort(clusters_[i].begin(), clusters_[i].end());
62 }
63 }
64
GetNumberOfProblems() const65 int LPDecomposer::GetNumberOfProblems() const {
66 absl::MutexLock mutex_lock(&mutex_);
67 return clusters_.size();
68 }
69
original_problem() const70 const LinearProgram& LPDecomposer::original_problem() const {
71 absl::MutexLock mutex_lock(&mutex_);
72 return *original_problem_;
73 }
74
ExtractLocalProblem(int problem_index,LinearProgram * lp)75 void LPDecomposer::ExtractLocalProblem(int problem_index, LinearProgram* lp) {
76 CHECK(lp != nullptr);
77 CHECK_GE(problem_index, 0);
78 CHECK_LT(problem_index, clusters_.size());
79
80 lp->Clear();
81
82 absl::MutexLock mutex_lock(&mutex_);
83 const std::vector<ColIndex>& cluster = clusters_[problem_index];
84 StrictITIVector<ColIndex, ColIndex> global_to_local(
85 original_problem_->num_variables(), kInvalidCol);
86 SparseBitset<RowIndex> constraints_to_use(
87 original_problem_->num_constraints());
88 lp->SetMaximizationProblem(original_problem_->IsMaximizationProblem());
89
90 // Create variables and get all constraints of the cluster.
91 const SparseMatrix& original_matrix = original_problem_->GetSparseMatrix();
92 const SparseMatrix& transposed_matrix =
93 original_problem_->GetTransposeSparseMatrix();
94 for (int i = 0; i < cluster.size(); ++i) {
95 const ColIndex global_col = cluster[i];
96 const ColIndex local_col = lp->CreateNewVariable();
97 CHECK_EQ(local_col, ColIndex(i));
98 CHECK(global_to_local[global_col] == kInvalidCol ||
99 global_to_local[global_col] == local_col)
100 << "If the mapping is already assigned it has to be the same.";
101 global_to_local[global_col] = local_col;
102
103 lp->SetVariableName(local_col,
104 original_problem_->GetVariableName(global_col));
105 lp->SetVariableType(local_col,
106 original_problem_->GetVariableType(global_col));
107 lp->SetVariableBounds(
108 local_col, original_problem_->variable_lower_bounds()[global_col],
109 original_problem_->variable_upper_bounds()[global_col]);
110 lp->SetObjectiveCoefficient(
111 local_col, original_problem_->objective_coefficients()[global_col]);
112
113 for (const SparseColumn::Entry e : original_matrix.column(global_col)) {
114 constraints_to_use.Set(e.row());
115 }
116 }
117 // Create the constraints.
118 for (const RowIndex global_row :
119 constraints_to_use.PositionsSetAtLeastOnce()) {
120 const RowIndex local_row = lp->CreateNewConstraint();
121 lp->SetConstraintName(local_row,
122 original_problem_->GetConstraintName(global_row));
123 lp->SetConstraintBounds(
124 local_row, original_problem_->constraint_lower_bounds()[global_row],
125 original_problem_->constraint_upper_bounds()[global_row]);
126
127 for (const SparseColumn::Entry e :
128 transposed_matrix.column(RowToColIndex(global_row))) {
129 const ColIndex global_col = RowToColIndex(e.row());
130 const ColIndex local_col = global_to_local[global_col];
131 lp->SetCoefficient(local_row, local_col, e.coefficient());
132 }
133 }
134 }
135
AggregateAssignments(const std::vector<DenseRow> & assignments) const136 DenseRow LPDecomposer::AggregateAssignments(
137 const std::vector<DenseRow>& assignments) const {
138 CHECK_EQ(assignments.size(), clusters_.size());
139
140 absl::MutexLock mutex_lock(&mutex_);
141 DenseRow global_assignment(original_problem_->num_variables(),
142 Fractional(0.0));
143 for (int problem = 0; problem < assignments.size(); ++problem) {
144 const DenseRow& local_assignment = assignments[problem];
145 const std::vector<ColIndex>& cluster = clusters_[problem];
146 for (int i = 0; i < local_assignment.size(); ++i) {
147 const ColIndex global_col = cluster[i];
148 global_assignment[global_col] = local_assignment[ColIndex(i)];
149 }
150 }
151 return global_assignment;
152 }
153
ExtractLocalAssignment(int problem_index,const DenseRow & assignment)154 DenseRow LPDecomposer::ExtractLocalAssignment(int problem_index,
155 const DenseRow& assignment) {
156 CHECK_GE(problem_index, 0);
157 CHECK_LT(problem_index, clusters_.size());
158 CHECK_EQ(assignment.size(), original_problem_->num_variables());
159
160 absl::MutexLock mutex_lock(&mutex_);
161 const std::vector<ColIndex>& cluster = clusters_[problem_index];
162 DenseRow local_assignment(ColIndex(cluster.size()), Fractional(0.0));
163 for (int i = 0; i < cluster.size(); ++i) {
164 const ColIndex global_col = cluster[i];
165 local_assignment[ColIndex(i)] = assignment[global_col];
166 }
167 return local_assignment;
168 }
169
170 } // namespace glop
171 } // namespace operations_research
172