Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
dual_edge_norms.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_GLOP_DUAL_EDGE_NORMS_H_
15#define OR_TOOLS_GLOP_DUAL_EDGE_NORMS_H_
16
17#include <string>
18
20#include "ortools/glop/parameters.pb.h"
25#include "ortools/util/stats.h"
27
28namespace operations_research {
29namespace glop {
30
31// This class maintains the dual edge squared norms to be used in the
32// dual steepest edge pricing. The dual edge u_i associated with a basic
33// variable of row index i is such that u_i.B = e_i where e_i is the unit row
34// vector with a 1.0 at position i and B the current basis. We call such vector
35// u_i an unit row left inverse, and it can be computed by
36//
37// basis_factorization.LeftSolveForUnitRow(i, &u_i);
38//
39// Instead of computing each ||u_i|| at every iteration, it is more efficient to
40// update them incrementally for each basis pivot applied to B. See the code or
41// the papers below for details:
42//
43// J.J. Forrest, D. Goldfarb, "Steepest-edge simplex algorithms for linear
44// programming", Mathematical Programming 57 (1992) 341-374, North-Holland.
45// http://www.springerlink.com/content/q645w3t2q229m248/
46//
47// Achim Koberstein, "The dual simplex method, techniques for a fast and stable
48// implementation", PhD, Paderborn, Univ., 2005.
49// http://digital.ub.uni-paderborn.de/hs/download/pdf/3885?originalFilename=true
51 public:
52 // Takes references to the linear program data we need.
53 explicit DualEdgeNorms(const BasisFactorization& basis_factorization);
54
55 // This type is neither copyable nor movable.
56 DualEdgeNorms(const DualEdgeNorms&) = delete;
58
59 // Clears, i.e. reset the object to its initial value. This will trigger a
60 // full norm recomputation on the next GetEdgeSquaredNorms().
61 void Clear();
62
63 // When we just add new constraints to the matrix and use an incremental
64 // solve, we do not need to recompute the norm of the old rows, and the norm
65 // of the new ones can be just set to 1 as long as we use identity columns for
66 // these.
67 void ResizeOnNewRows(RowIndex new_size);
68
69 // If this is true, then the caller must re-factorize the basis before the
70 // next call to GetEdgeSquaredNorms(). This is because the latter will
71 // recompute the norms from scratch and therefore needs a hightened precision
72 // and speed. This also indicates if GetEdgeSquaredNorms() will trigger a
73 // recomputation.
74 bool NeedsBasisRefactorization() const;
75
76 // Returns the dual edge squared norms. This is only valid if the caller
77 // properly called UpdateBeforeBasisPivot() before each basis pivot, or just
78 // called Clear().
80
81 // Updates the norms if the columns of the basis where permuted.
83
84 // Computes exactly the norm of the given leaving row, and returns true if it
85 // is good enough compared to our current norm. In both case update the
86 // current norm with its precise version and decide if we should recompute
87 // norms on the next GetEdgeSquaredNorms().
88 bool TestPrecision(RowIndex leaving_row,
89 const ScatteredRow& unit_row_left_inverse);
90
91 // Updates the norms just before a basis pivot is applied:
92 // - The column at leaving_row will leave the basis and the column at
93 // entering_col will enter it.
94 // - direction is the right inverse of the entering column.
95 // - unit_row_left_inverse is the left inverse of the unit row with index
96 // given by the leaving_row. This is also the leaving dual edge.
97 void UpdateBeforeBasisPivot(ColIndex entering_col, RowIndex leaving_row,
98 const ScatteredColumn& direction,
99 const ScatteredRow& unit_row_left_inverse);
100
101 // Sets the algorithm parameters.
102 void SetParameters(const GlopParameters& parameters) {
103 parameters_ = parameters;
104 }
105
106 void SetTimeLimit(TimeLimit* time_limit) { time_limit_ = time_limit; }
107
108 // Stats related functions.
109 std::string StatString() const { return stats_.StatString(); }
110
111 private:
112 // Recomputes the dual edge squared norms from scratch with maximum precision.
113 // The matrix must have been refactorized before because we will do a lot of
114 // inversions. See NeedsBasisRefactorization(). This is checked in debug mode.
115 void ComputeEdgeSquaredNorms();
116
117 // Computes the vector tau needed to update the norms using a right solve:
118 // B.tau = (u_i)^T, u_i.B = e_i for i = leaving_row.
119 const DenseColumn& ComputeTau(const ScatteredColumn& unit_row_left_inverse);
120
121 // Statistics.
122 struct Stats : public StatsGroup {
123 Stats()
124 : StatsGroup("DualEdgeNorms"),
125 tau_density("tau_density", this),
126 edge_norms_accuracy("edge_norms_accuracy", this),
127 lower_bounded_norms("lower_bounded_norms", this) {}
128 RatioDistribution tau_density;
129 DoubleDistribution edge_norms_accuracy;
130 IntegerDistribution lower_bounded_norms;
131 };
132 Stats stats_;
133
134 // Parameters.
135 GlopParameters parameters_;
136 TimeLimit* time_limit_ = nullptr;
137
138 // Problem data that should be updated from outside.
139 const BasisFactorization& basis_factorization_;
140
141 // The dual edge norms.
142 DenseColumn edge_squared_norms_;
143 DenseColumn tmp_edge_squared_norms_;
144
145 // Whether we should recompute the norm from scratch.
146 bool recompute_edge_squared_norms_;
147};
148
149} // namespace glop
150} // namespace operations_research
151
152#endif // OR_TOOLS_GLOP_DUAL_EDGE_NORMS_H_
Statistic on the distribution of a sequence of doubles.
Definition stats.h:276
Statistic on the distribution of a sequence of integers.
Definition stats.h:288
Statistic on the distribution of a sequence of ratios, displayed as %.
Definition stats.h:265
Base class to print a nice summary of a group of statistics.
Definition stats.h:128
DenseColumn::ConstView GetEdgeSquaredNorms()
DualEdgeNorms & operator=(const DualEdgeNorms &)=delete
std::string StatString() const
Stats related functions.
DualEdgeNorms(const BasisFactorization &basis_factorization)
Takes references to the linear program data we need.
void UpdateDataOnBasisPermutation(const ColumnPermutation &col_perm)
Updates the norms if the columns of the basis where permuted.
DualEdgeNorms(const DualEdgeNorms &)=delete
This type is neither copyable nor movable.
void UpdateBeforeBasisPivot(ColIndex entering_col, RowIndex leaving_row, const ScatteredColumn &direction, const ScatteredRow &unit_row_left_inverse)
void SetTimeLimit(TimeLimit *time_limit)
void SetParameters(const GlopParameters &parameters)
Sets the algorithm parameters.
bool TestPrecision(RowIndex leaving_row, const ScatteredRow &unit_row_left_inverse)
StrictITISpan< RowIndex, const Fractional > ConstView
Definition lp_types.h:291
time_limit
Definition solve.cc:22
Permutation< ColIndex > ColumnPermutation
StrictITIVector< RowIndex, Fractional > DenseColumn
Column-vector types. Column-vector types are indexed by a row index.
Definition lp_types.h:380
In SWIG mode, we don't want anything besides these top-level includes.