OR-Tools  8.2
entering_variable.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_ENTERING_VARIABLE_H_
15#define OR_TOOLS_GLOP_ENTERING_VARIABLE_H_
16
18#include "ortools/glop/parameters.pb.h"
21#include "ortools/glop/status.h"
26#include "ortools/util/bitset.h"
28#include "ortools/util/stats.h"
29
30#if !SWIG
31
32namespace operations_research {
33namespace glop {
34
35// This class contains the primal and dual algorithms that choose the entering
36// column (i.e. variable) during a simplex iteration.
37//
38// The goal of this component is, given a matrix A (matrix_), a subset of
39// columns (basis_) that form a basis B and a cost (objective_) associated to
40// each column of A, to choose a "good" non-basic column to enter the basis
41// B. Note that this choice does not depend on the current variable values
42// (except for the direction in which each variable is allowed to change given
43// by variable_status_).
44//
45// Terminology:
46// - The entering edge is the edge we are following during a simplex step,
47// and we call "direction" the reverse of this edge restricted to the
48// basic variables, i.e. the right inverse of the entering column.
49//
50// Papers:
51// - Ping-Qi Pan, "Efficient nested pricing in the simplex algorithm",
52// http://www.optimization-online.org/DB_FILE/2007/10/1810.pdf
54 public:
55 // Takes references to the linear program data we need.
56 EnteringVariable(const VariablesInfo& variables_info, random_engine_t* random,
57 ReducedCosts* reduced_costs,
58 PrimalEdgeNorms* primal_edge_norms);
59
60 // Returns the index of a valid primal entering column (see
61 // IsValidPrimalEnteringCandidate() for more details) or kInvalidCol if no
62 // such column exists. This latter case means that the primal algorithm has
63 // terminated: the optimal has been reached.
64 ABSL_MUST_USE_RESULT Status
65 PrimalChooseEnteringColumn(ColIndex* entering_col);
66
67 // Dual optimization phase (i.e. phase II) ratio test.
68 // Returns the index of the entering column given that we want to move along
69 // the "update" row vector in the direction given by the sign of
70 // cost_variation. Computes the smallest step that keeps the dual feasibility
71 // for all the columns.
72 ABSL_MUST_USE_RESULT Status DualChooseEnteringColumn(
73 const UpdateRow& update_row, Fractional cost_variation,
74 std::vector<ColIndex>* bound_flip_candidates, ColIndex* entering_col,
75 Fractional* step);
76
77 // Dual feasibility phase (i.e. phase I) ratio test.
78 // Similar to the optimization phase test, but allows a step that increases
79 // the infeasibility of an already infeasible column. The step magnitude is
80 // the one that minimize the sum of infeasibilities when applied.
81 ABSL_MUST_USE_RESULT Status DualPhaseIChooseEnteringColumn(
82 const UpdateRow& update_row, Fractional cost_variation,
83 ColIndex* entering_col, Fractional* step);
84
85 // Sets the pricing parameters. This does not change the pricing rule.
86 void SetParameters(const GlopParameters& parameters);
87
88 // Sets the pricing rule.
89 void SetPricingRule(GlopParameters::PricingRule rule);
90
91 // Stats related functions.
92 std::string StatString() const { return stats_.StatString(); }
93
94 // Recomputes the set of unused columns used during nested pricing.
95 // Visible for testing (the returns value is also there for testing).
97
98 private:
99 // Dantzig selection rule: choose the variable with the best reduced cost.
100 // If normalize is true, we normalize the costs by the column norms.
101 // If nested_pricing is true, we use nested pricing (see parameters.proto).
102 template <bool normalize, bool nested_pricing>
103 void DantzigChooseEnteringColumn(ColIndex* entering_col);
104
105 // Steepest edge rule: the reduced costs are normalized by the edges norm.
106 // Devex rule: the reduced costs are normalized by an approximation of the
107 // edges norm.
108 template <bool use_steepest_edge>
109 void NormalizedChooseEnteringColumn(ColIndex* entering_col);
110
111 // Problem data that should be updated from outside.
112 const VariablesInfo& variables_info_;
113
114 random_engine_t* random_;
115 ReducedCosts* reduced_costs_;
116 PrimalEdgeNorms* primal_edge_norms_;
117
118 // Internal data.
119 GlopParameters parameters_;
120 GlopParameters::PricingRule rule_;
121
122 // Stats.
123 struct Stats : public StatsGroup {
124 Stats()
125 : StatsGroup("EnteringVariable"),
126 num_perfect_ties("num_perfect_ties", this) {}
127 IntegerDistribution num_perfect_ties;
128 };
129 Stats stats_;
130
131 // This is used for nested pricing. It is denoted J in Ping-Qi Pan's paper.
132 // At a given step, it is true for the variable that should be considered for
133 // entering the basis.
134 DenseBitRow unused_columns_;
135
136 // Temporary vector used to hold the best entering column candidates that are
137 // tied using the current choosing criteria. We actually only store the tied
138 // candidate #2, #3, ...; because the first tied candidate is remembered
139 // anyway.
140 std::vector<ColIndex> equivalent_entering_choices_;
141
142 // Store a column with its update coefficient and ratio.
143 // This is used during the dual phase I & II ratio tests.
144 struct ColWithRatio {
145 ColWithRatio(ColIndex _col, Fractional reduced_cost, Fractional coeff_m)
146 : col(_col), ratio(reduced_cost / coeff_m), coeff_magnitude(coeff_m) {}
147
148 // Returns false if "this" is before "other" in a priority queue.
149 bool operator<(const ColWithRatio& other) const {
150 if (ratio == other.ratio) {
151 if (coeff_magnitude == other.coeff_magnitude) {
152 return col > other.col;
153 }
154 return coeff_magnitude < other.coeff_magnitude;
155 }
156 return ratio > other.ratio;
157 }
158
159 ColIndex col;
162 };
163
164 // Temporary vector used to hold breakpoints.
165 std::vector<ColWithRatio> breakpoints_;
166
167 DISALLOW_COPY_AND_ASSIGN(EnteringVariable);
168};
169
170} // namespace glop
171} // namespace operations_research
172
173#endif // SWIG
174#endif // OR_TOOLS_GLOP_ENTERING_VARIABLE_H_
ABSL_MUST_USE_RESULT Status PrimalChooseEnteringColumn(ColIndex *entering_col)
ABSL_MUST_USE_RESULT Status DualChooseEnteringColumn(const UpdateRow &update_row, Fractional cost_variation, std::vector< ColIndex > *bound_flip_candidates, ColIndex *entering_col, Fractional *step)
EnteringVariable(const VariablesInfo &variables_info, random_engine_t *random, ReducedCosts *reduced_costs, PrimalEdgeNorms *primal_edge_norms)
ABSL_MUST_USE_RESULT Status DualPhaseIChooseEnteringColumn(const UpdateRow &update_row, Fractional cost_variation, ColIndex *entering_col, Fractional *step)
void SetPricingRule(GlopParameters::PricingRule rule)
void SetParameters(const GlopParameters &parameters)
SatParameters parameters
ColIndex col
Definition: markowitz.cc:176
Bitset64< ColIndex > DenseBitRow
Definition: lp_types.h:323
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
std::mt19937 random_engine_t
Definition: random_engine.h:23
Fractional coeff_magnitude
Fractional ratio