OR-Tools  8.2
lp_decomposer.cc
Go to the documentation of this file.
1// Copyright 2010-2018 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 <vector>
17
18#include "absl/synchronization/mutex.h"
22
23namespace operations_research {
24namespace glop {
25
26//------------------------------------------------------------------------------
27// LPDecomposer
28//------------------------------------------------------------------------------
30 : original_problem_(nullptr), clusters_(), mutex_() {}
31
32void 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
66 absl::MutexLock mutex_lock(&mutex_);
67 return clusters_.size();
68}
69
71 absl::MutexLock mutex_lock(&mutex_);
72 return *original_problem_;
73}
74
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];
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));
108 local_col, original_problem_->variable_lower_bounds()[global_col],
109 original_problem_->variable_upper_bounds()[global_col]);
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));
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
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
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
#define CHECK(condition)
Definition: base/logging.h:495
#define CHECK_LT(val1, val2)
Definition: base/logging.h:700
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
int MergePartsOf(int node1, int node2)
int FillEquivalenceClasses(std::vector< int > *node_equivalence_classes)
void Set(IntegerType index)
Definition: bitset.h:803
const std::vector< IntegerType > & PositionsSetAtLeastOnce() const
Definition: bitset.h:813
void Decompose(const LinearProgram *linear_problem) ABSL_LOCKS_EXCLUDED(mutex_)
const LinearProgram & original_problem() const ABSL_LOCKS_EXCLUDED(mutex_)
void ExtractLocalProblem(int problem_index, LinearProgram *lp) ABSL_LOCKS_EXCLUDED(mutex_)
DenseRow AggregateAssignments(const std::vector< DenseRow > &assignments) const ABSL_LOCKS_EXCLUDED(mutex_)
DenseRow ExtractLocalAssignment(int problem_index, const DenseRow &assignment) ABSL_LOCKS_EXCLUDED(mutex_)
int GetNumberOfProblems() const ABSL_LOCKS_EXCLUDED(mutex_)
void SetVariableBounds(ColIndex col, Fractional lower_bound, Fractional upper_bound)
Definition: lp_data.cc:248
std::string GetVariableName(ColIndex col) const
Definition: lp_data.cc:359
void SetConstraintName(RowIndex row, absl::string_view name)
Definition: lp_data.cc:244
const SparseMatrix & GetTransposeSparseMatrix() const
Definition: lp_data.cc:375
void SetCoefficient(RowIndex row, ColIndex col, Fractional value)
Definition: lp_data.cc:316
void SetVariableName(ColIndex col, absl::string_view name)
Definition: lp_data.cc:231
const DenseColumn & constraint_lower_bounds() const
Definition: lp_data.h:214
void SetConstraintBounds(RowIndex row, Fractional lower_bound, Fractional upper_bound)
Definition: lp_data.cc:308
VariableType GetVariableType(ColIndex col) const
Definition: lp_data.cc:371
const DenseRow & variable_upper_bounds() const
Definition: lp_data.h:231
void SetVariableType(ColIndex col, VariableType type)
Definition: lp_data.cc:235
std::string GetConstraintName(RowIndex row) const
Definition: lp_data.cc:365
const DenseColumn & constraint_upper_bounds() const
Definition: lp_data.h:217
const DenseRow & objective_coefficients() const
Definition: lp_data.h:222
void SetObjectiveCoefficient(ColIndex col, Fractional value)
Definition: lp_data.cc:325
const SparseMatrix & GetSparseMatrix() const
Definition: lp_data.h:174
const DenseRow & variable_lower_bounds() const
Definition: lp_data.h:228
void SetMaximizationProblem(bool maximize)
Definition: lp_data.cc:342
RowIndex EntryRow(EntryIndex i) const
Definition: sparse_column.h:51
const SparseColumn & column(ColIndex col) const
Definition: sparse.h:180
const Constraint * ct
const ColIndex kInvalidCol(-1)
ColIndex RowToColIndex(RowIndex row)
Definition: lp_types.h:48
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...