25 : compact_matrix_(compact_matrix),
26 variables_info_(variables_info),
27 basis_factorization_(basis_factorization),
29 recompute_edge_squared_norms_(true),
30 reset_devex_weights_(true),
31 edge_squared_norms_(),
32 matrix_column_norms_(),
34 direction_left_inverse_(),
39 recompute_edge_squared_norms_ =
true;
40 reset_devex_weights_ =
true;
44 return recompute_edge_squared_norms_;
48 if (recompute_edge_squared_norms_) ComputeEdgeSquaredNorms();
49 return edge_squared_norms_;
53 if (reset_devex_weights_) ResetDevexWeights();
54 return devex_weights_;
58 if (matrix_column_norms_.
empty()) ComputeMatrixColumnNorms();
59 return matrix_column_norms_;
64 if (!recompute_edge_squared_norms_) {
69 const Fractional old_squared_norm = edge_squared_norms_[entering_col];
71 edge_squared_norms_[entering_col] = precise_squared_norm;
73 const Fractional precise_norm = sqrt(precise_squared_norm);
74 const Fractional estimated_edges_norm_accuracy =
75 (precise_norm - sqrt(old_squared_norm)) / precise_norm;
76 stats_.edges_norm_accuracy.Add(estimated_edges_norm_accuracy);
77 if (std::abs(estimated_edges_norm_accuracy) >
78 parameters_.recompute_edges_norm_threshold()) {
79 VLOG(1) <<
"Recomputing edge norms: " << sqrt(precise_squared_norm)
80 <<
" vs " << sqrt(old_squared_norm);
81 recompute_edge_squared_norms_ =
true;
93 if (!recompute_edge_squared_norms_) {
95 ComputeDirectionLeftInverse(entering_col, direction);
96 UpdateEdgeSquaredNorms(entering_col, leaving_col, leaving_row,
97 direction.
values, *update_row);
99 if (!reset_devex_weights_) {
102 ++num_devex_updates_since_reset_;
103 if (num_devex_updates_since_reset_ >
104 parameters_.devex_weights_reset_period()) {
105 reset_devex_weights_ =
true;
108 UpdateDevexWeights(entering_col, leaving_col, leaving_row,
109 direction.
values, *update_row);
114 void PrimalEdgeNorms::ComputeMatrixColumnNorms() {
123 void PrimalEdgeNorms::ComputeEdgeSquaredNorms() {
136 recompute_edge_squared_norms_ =
false;
142 void PrimalEdgeNorms::ComputeDirectionLeftInverse(
143 ColIndex entering_col,
const ScatteredColumn& direction) {
149 const ColIndex size =
RowToColIndex(direction.values.size());
150 const double kThreshold = 0.05 * size.value();
151 if (!direction_left_inverse_.
non_zeros.empty() &&
152 (direction_left_inverse_.
non_zeros.size() + direction.non_zeros.size() <
155 for (
const auto e : direction) {
156 direction_left_inverse_[
RowToColIndex(e.row())] = e.coefficient();
160 direction_left_inverse_.
non_zeros.clear();
163 if (direction.non_zeros.size() < kThreshold) {
166 basis_factorization_.
LeftSolve(&direction_left_inverse_);
171 direction_left_inverse_.
values) -
184 void PrimalEdgeNorms::UpdateEdgeSquaredNorms(ColIndex entering_col,
185 ColIndex leaving_col,
186 RowIndex leaving_row,
188 const UpdateRow& update_row) {
194 const Fractional pivot = -direction[leaving_row];
199 const Fractional entering_squared_norm = edge_squared_norms_[entering_col];
203 int stat_lower_bounded_norms = 0;
205 for (
const ColIndex
col : update_row.GetNonZeroPositions()) {
214 edge_squared_norms_[
col] +=
215 coeff * (coeff * leaving_squared_norm + factor * scalar_product);
223 if (edge_squared_norms_[
col] < lower_bound) {
224 edge_squared_norms_[
col] = lower_bound;
225 ++stat_lower_bounded_norms;
228 edge_squared_norms_[leaving_col] = leaving_squared_norm;
229 stats_.lower_bounded_norms.Add(stat_lower_bounded_norms);
232 void PrimalEdgeNorms::UpdateDevexWeights(
233 ColIndex entering_col ,
234 ColIndex leaving_col , RowIndex leaving_row,
235 const DenseColumn& direction,
const UpdateRow& update_row) {
241 const Fractional pivot_magnitude = std::abs(direction[leaving_row]);
243 std::max(1.0, entering_norm / pivot_magnitude);
244 for (
const ColIndex
col : update_row.GetNonZeroPositions()) {
246 const Fractional update_vector_norm = std::abs(coeff) * leaving_norm;
247 devex_weights_[
col] =
std::max(devex_weights_[
col], update_vector_norm);
249 devex_weights_[leaving_col] = leaving_norm;
252 void PrimalEdgeNorms::ResetDevexWeights() {
254 if (parameters_.initialize_devex_with_column_norms()) {
259 num_devex_updates_since_reset_ = 0;
260 reset_devex_weights_ =
false;
#define DCHECK_NE(val1, val2)
#define DCHECK(condition)
#define VLOG(verboselevel)
Fractional RightSolveSquaredNorm(const ColumnView &a) const
bool IsRefactorized() const
void LeftSolve(ScatteredRow *y) const
EntryIndex num_entries() const
ColIndex num_cols() const
Fractional ColumnScalarProduct(ColIndex col, const DenseRow &vector) const
ColumnView column(ColIndex col) const
PrimalEdgeNorms(const CompactSparseMatrix &compact_matrix, const VariablesInfo &variables_info, const BasisFactorization &basis_factorization)
const DenseRow & GetMatrixColumnNorms()
const DenseRow & GetEdgeSquaredNorms()
const DenseRow & GetDevexWeights()
void UpdateBeforeBasisPivot(ColIndex entering_col, ColIndex leaving_col, RowIndex leaving_row, const ScatteredColumn &direction, UpdateRow *update_row)
void TestEnteringEdgeNormPrecision(ColIndex entering_col, const ScatteredColumn &direction)
bool NeedsBasisRefactorization() const
void resize(IntType size)
void assign(IntType size, const T &v)
void ComputeUpdateRow(RowIndex leaving_row)
const DenseBitRow & GetIsRelevantBitRow() const
Fractional Square(Fractional f)
Fractional PreciseSquaredNorm(const SparseColumn &v)
Fractional SquaredNorm(const SparseColumn &v)
double Density(const DenseRow &row)
ColIndex RowToColIndex(RowIndex row)
void ClearAndResizeVectorWithNonZeros(IndexType size, ScatteredRowOrCol *v)
const DenseRow & Transpose(const DenseColumn &col)
StrictITIVector< RowIndex, Fractional > DenseColumn
const ScatteredRow & TransposedView(const ScatteredColumn &c)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
#define IF_STATS_ENABLED(instructions)
#define SCOPED_TIME_STAT(stats)
std::vector< Index > non_zeros
StrictITIVector< Index, Fractional > values