OR-Tools  8.2
variables_info.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_GLOP_VARIABLES_INFO_H_
15#define OR_TOOLS_GLOP_VARIABLES_INFO_H_
16
19
20namespace operations_research {
21namespace glop {
22
23// Class responsible for maintaining diverse information for each variable that
24// depend on its bounds and status.
25//
26// Note(user): Not all information is needed at all time, but it is cheap to
27// maintain it since it only requires a few calls to Update() per simplex
28// iteration.
30 public:
31 // Takes references to the linear program data we need.
32 VariablesInfo(const CompactSparseMatrix& matrix, const DenseRow& lower_bound,
33 const DenseRow& upper_bound);
34
35 // Recomputes the variable types from the bounds (this is the only function
36 // that changes them). This also resets all the non-type quantities to a
37 // default value. Note however that nothing should be assumed on the return
38 // values of the getters until Update() has been called at least once on all
39 // the columns.
41
42 // Updates the information of the given variable. Note that it is not needed
43 // to call this if the status or the bound of a variable didn't change.
44 void Update(ColIndex col, VariableStatus status);
45
46 // Slightly optimized version of Update() above for the two separate cases.
47 void UpdateToBasicStatus(ColIndex col);
48 void UpdateToNonBasicStatus(ColIndex col, VariableStatus status);
49
50 // Various getter, see the corresponding member declaration below for more
51 // information.
52 const VariableTypeRow& GetTypeRow() const;
53 const VariableStatusRow& GetStatusRow() const;
54 const DenseBitRow& GetCanIncreaseBitRow() const;
55 const DenseBitRow& GetCanDecreaseBitRow() const;
56 const DenseBitRow& GetIsRelevantBitRow() const;
57 const DenseBitRow& GetIsBasicBitRow() const;
58 const DenseBitRow& GetNotBasicBitRow() const;
60
61 // Returns the variable bounds.
62 const DenseRow& GetVariableLowerBounds() const { return lower_bound_; }
63 const DenseRow& GetVariableUpperBounds() const { return upper_bound_; }
64
65 const ColIndex GetNumberOfColumns() const { return matrix_.num_cols(); }
66
67 // Changes whether or not a non-basic boxed variable is 'relevant' and will be
68 // returned as such by GetIsRelevantBitRow().
70
71 // This is used in UpdateRow to decide whether to compute it using the
72 // row-wise or column-wise representation.
73 EntryIndex GetNumEntriesInRelevantColumns() const;
74
75 // Returns the distance between the upper and lower bound of the given column.
77 return upper_bound_[col] - lower_bound_[col];
78 }
79
80 private:
81 // Computes the variable type from its lower and upper bound.
82 VariableType ComputeVariableType(ColIndex col) const;
83
84 // Sets the column relevance and updates num_entries_in_relevant_columns_.
85 void SetRelevance(ColIndex col, bool relevance);
86
87 // Problem data that should be updated from outside.
88 const CompactSparseMatrix& matrix_;
89 const DenseRow& lower_bound_;
90 const DenseRow& upper_bound_;
91
92 // Array of variable statuses, indexed by column index.
93 VariableStatusRow variable_status_;
94
95 // Array of variable types, indexed by column index.
96 VariableTypeRow variable_type_;
97
98 // Indicates if a non-basic variable can move up or down while not increasing
99 // the primal infeasibility. Note that all combinaisons are possible for a
100 // variable according to its status: fixed, free, upper or lower bounded. This
101 // is always false for basic variable.
102 DenseBitRow can_increase_;
103 DenseBitRow can_decrease_;
104
105 // Indicates if we should consider this variable for entering the basis during
106 // the simplex algorithm. We never consider fixed variables and in the dual
107 // feasibility phase, we don't consider boxed variable.
108 DenseBitRow relevance_;
109
110 // Indicates if a variable is BASIC or not. There are currently two members
111 // because the DenseBitRow class only supports a nice range-based iteration on
112 // the non-zero positions and not on the others.
113 DenseBitRow is_basic_;
114 DenseBitRow not_basic_;
115
116 // Set of boxed variables that are non-basic.
117 DenseBitRow non_basic_boxed_variables_;
118
119 // Number of entries for the relevant matrix columns (see relevance_).
120 EntryIndex num_entries_in_relevant_columns_;
121
122 // Whether or not a boxed variable should be considered relevant.
123 bool boxed_variables_are_relevant_;
124
125 DISALLOW_COPY_AND_ASSIGN(VariablesInfo);
126};
127
128} // namespace glop
129} // namespace operations_research
130
131#endif // OR_TOOLS_GLOP_VARIABLES_INFO_H_
const DenseBitRow & GetIsBasicBitRow() const
const DenseRow & GetVariableLowerBounds() const
const DenseBitRow & GetNonBasicBoxedVariables() const
Fractional GetBoundDifference(ColIndex col) const
const DenseBitRow & GetCanIncreaseBitRow() const
const DenseBitRow & GetCanDecreaseBitRow() const
const VariableTypeRow & GetTypeRow() const
void UpdateToNonBasicStatus(ColIndex col, VariableStatus status)
const DenseBitRow & GetNotBasicBitRow() const
VariablesInfo(const CompactSparseMatrix &matrix, const DenseRow &lower_bound, const DenseRow &upper_bound)
const VariableStatusRow & GetStatusRow() const
const DenseRow & GetVariableUpperBounds() const
const DenseBitRow & GetIsRelevantBitRow() const
const ColIndex GetNumberOfColumns() const
void Update(ColIndex col, VariableStatus status)
int64 value
ColIndex col
Definition: markowitz.cc:176
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...