Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
assignment.h
Go to the documentation of this file.
1// Copyright 2010-2025 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_SET_COVER_ASSIGNMENT_H_
15#define OR_TOOLS_SET_COVER_ASSIGNMENT_H_
16
17#include <vector>
18
23
24namespace operations_research {
25
26// `SetCoverAssignment` stores a possibly partial, possibly infeasible solution
27// to a `SetCoverModel`. It only stores a solution and no metadata,
28// so that it can be shared efficiently among constraints.
29//
30// This class is equivalent to an `Assignment` object in the CP/routing solver.
31// (//ortools/routing).
33 public:
34 // Constructs an empty set covering assignment.
35 //
36 // The model size or costs must not change after the invariant was built.
37 // The caller must guarantee that the model outlives the assignment without
38 // changing its costs.
40 : model_(m), constraint_(nullptr), side_constraints_({}) {
41 Clear();
42 }
43
44 // Clears the current assignment.
45 void Clear();
46
47 // Adds a constraint to the problem. At least one set-covering constraint is
48 // required; use side constraints as required (no set-covering constraint can
49 // be a side constraint).
50 void AttachInvariant(SetCoverInvariant* i);
51 void AttachInvariant(CapacityInvariant* i);
52
53 // Returns the cost of current solution.
54 Cost cost() const { return cost_; }
55
56 // Returns the subset assignment vector.
57 const SubsetBoolVector& assignment() const { return values_; }
58
59 // Sets the subset's assignment to the given bool.
60 void SetValue(SubsetIndex subset, bool is_selected,
61 SetCoverInvariant::ConsistencyLevel set_cover_consistency);
62
63 // Returns the current solution as a proto.
64 SetCoverSolutionResponse ExportSolutionAsProto() const;
65
66 // Loads the solution and recomputes the data in the invariant.
67 //
68 // The given assignment must fit the model of this assignment.
70
71 // Imports the solution from a proto.
72 //
73 // The given assignment must fit the model of this assignment.
74 void ImportSolutionFromProto(const SetCoverSolutionResponse& message);
75
76 // Checks the consistency of the solution (between the selected subsets and
77 // the solution cost).
78 bool CheckConsistency() const;
79
80 private:
81 // Computes the cost for the given choices.
82 Cost ComputeCost(const SubsetBoolVector& choices) const;
83
84 // The weighted set covering model on which the solver is run.
85 const SetCoverModel& model_;
86
87 // Current cost of the assignment.
88 Cost cost_;
89
90 // Current assignment. Takes |S| bits.
91 SubsetBoolVector values_;
92
93 // Constraints that this assignment must respect. The constraints are checked
94 // every time the assignment changes (with the methods `Flip`, `Select`, and
95 // `Deselect`).
96 //
97 // For now, the only side constraints are capacity constraints.
98 SetCoverInvariant* constraint_;
99 // TODO(user): merge the several constraints into one invariant.
100 std::vector<CapacityInvariant*> side_constraints_;
101};
102
103} // namespace operations_research
104
105#endif // OR_TOOLS_SET_COVER_ASSIGNMENT_H_
const SubsetBoolVector & assignment() const
Returns the subset assignment vector.
Definition assignment.h:57
void LoadAssignment(const SubsetBoolVector &solution)
Definition assignment.cc:90
void ImportSolutionFromProto(const SetCoverSolutionResponse &message)
Definition assignment.cc:96
Cost cost() const
Returns the cost of current solution.
Definition assignment.h:54
SetCoverAssignment(const SetCoverModel &m)
Definition assignment.h:39
void Clear()
Clears the current assignment.
Definition assignment.cc:26
void SetValue(SubsetIndex subset, bool is_selected, SetCoverInvariant::ConsistencyLevel set_cover_consistency)
Sets the subset's assignment to the given bool.
Definition assignment.cc:47
SetCoverSolutionResponse ExportSolutionAsProto() const
Returns the current solution as a proto.
Definition assignment.cc:77
void AttachInvariant(SetCoverInvariant *i)
Definition assignment.cc:35
Main class for describing a weighted set-covering problem.
In SWIG mode, we don't want anything besides these top-level includes.
Select next search node to expand Select next item_i to add this new search node to the search Generate a new search node where item_i is not in the knapsack Check validity of this new partial solution(using propagators) - If valid
util_intops::StrongVector< SubsetIndex, bool > SubsetBoolVector
Definition base_types.h:71
double Cost
Basic non-strict type for cost. The speed penalty for using double is ~2%.
Definition base_types.h:32