OR-Tools  8.2
lp_decomposer.h
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
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"
23
24namespace operations_research {
25namespace 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.
51 public:
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_
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_)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...