29 : variables_info_(variables_info),
31 reduced_costs_(reduced_costs),
32 primal_edge_norms_(primal_edge_norms),
34 rule_(GlopParameters::DANTZIG),
42 const bool kNormalize =
true;
43 const bool kNested =
true;
44 const bool kSteepest =
true;
47 case GlopParameters::DANTZIG:
48 if (parameters_.use_nested_pricing()) {
52 if (parameters_.normalize_using_column_norm()) {
53 DantzigChooseEnteringColumn<kNormalize, kNested>(entering_col);
55 DantzigChooseEnteringColumn<!kNormalize, kNested>(entering_col);
58 unused_columns_.
Clear(*entering_col);
62 if (parameters_.normalize_using_column_norm()) {
63 DantzigChooseEnteringColumn<kNormalize, kNested>(entering_col);
65 DantzigChooseEnteringColumn<!kNormalize, kNested>(entering_col);
68 if (parameters_.normalize_using_column_norm()) {
69 DantzigChooseEnteringColumn<kNormalize, !kNested>(entering_col);
71 DantzigChooseEnteringColumn<!kNormalize, !kNested>(entering_col);
75 case GlopParameters::STEEPEST_EDGE:
76 NormalizedChooseEnteringColumn<kSteepest>(entering_col);
78 case GlopParameters::DEVEX:
79 NormalizedChooseEnteringColumn<!kSteepest>(entering_col);
82 LOG(DFATAL) <<
"Unknown pricing rule: "
83 << ProtoEnumToString<GlopParameters::PricingRule>(rule_)
84 <<
". Using steepest edge.";
85 NormalizedChooseEnteringColumn<kSteepest>(entering_col);
91 std::vector<ColIndex>* bound_flip_candidates, ColIndex* entering_col,
101 const Fractional threshold = parameters_.ratio_test_zero_threshold();
110 parameters_.harris_tolerance_ratio() *
118 const Fractional coeff = (cost_variation > 0.0) ? update_coefficient[
col]
119 : -update_coefficient[
col];
123 if (can_decrease.
IsSet(
col) && coeff > threshold) {
124 if (!is_boxed[
col]) {
125 if (-reduced_costs[
col] > harris_ratio * coeff)
continue;
127 harris_ratio, (-reduced_costs[
col] + harris_tolerance) / coeff);
128 harris_ratio =
std::max(0.0, harris_ratio);
130 breakpoints_.push_back(ColWithRatio(
col, -reduced_costs[
col], coeff));
136 if (can_increase.
IsSet(
col) && coeff < -threshold) {
137 if (!is_boxed[
col]) {
138 if (reduced_costs[
col] > harris_ratio * -coeff)
continue;
140 harris_ratio, (reduced_costs[
col] + harris_tolerance) / -coeff);
141 harris_ratio =
std::max(0.0, harris_ratio);
143 breakpoints_.push_back(ColWithRatio(
col, reduced_costs[
col], -coeff));
153 std::make_heap(breakpoints_.begin(), breakpoints_.end());
167 bound_flip_candidates->clear();
169 Fractional variation_magnitude = std::abs(cost_variation);
170 equivalent_entering_choices_.clear();
171 while (!breakpoints_.empty()) {
172 const ColWithRatio top = breakpoints_.front();
173 if (top.ratio > harris_ratio)
break;
186 if (variation_magnitude > threshold) {
187 if (is_boxed[top.col]) {
188 variation_magnitude -=
190 if (variation_magnitude > threshold) {
191 bound_flip_candidates->push_back(top.col);
192 std::pop_heap(breakpoints_.begin(), breakpoints_.end());
193 breakpoints_.pop_back();
202 if (top.coeff_magnitude >= best_coeff) {
207 harris_ratio, top.ratio + harris_tolerance / top.coeff_magnitude);
213 harris_ratio =
std::max(harris_ratio, 0.0);
215 if (top.coeff_magnitude == best_coeff && top.ratio == *step) {
217 equivalent_entering_choices_.push_back(top.col);
219 equivalent_entering_choices_.clear();
220 best_coeff = top.coeff_magnitude;
221 *entering_col = top.col;
231 std::pop_heap(breakpoints_.begin(), breakpoints_.end());
232 breakpoints_.pop_back();
236 if (!equivalent_entering_choices_.empty()) {
237 equivalent_entering_choices_.push_back(*entering_col);
239 equivalent_entering_choices_[std::uniform_int_distribution<int>(
240 0, equivalent_entering_choices_.size() - 1)(*random_)];
242 stats_.num_perfect_ties.Add(equivalent_entering_choices_.size()));
263 reduced_costs_->
ShiftCost(*entering_col);
279 breakpoints_.clear();
283 const Fractional threshold = parameters_.ratio_test_zero_threshold();
292 DCHECK_NE(variable_type[
col], VariableType::UPPER_AND_LOWER_BOUNDED);
298 if (std::abs(update_coefficient[
col]) < threshold)
continue;
306 const Fractional coeff = (cost_variation > 0.0) ? update_coefficient[
col]
307 : -update_coefficient[
col];
311 if (std::abs(reduced_costs[
col]) <= dual_feasibility_tolerance) {
313 if (coeff > 0 && !can_decrease.
IsSet(
col))
continue;
314 if (coeff < 0 && !can_increase.
IsSet(
col))
continue;
323 if (coeff * reduced_costs[
col] > 0)
continue;
327 breakpoints_.push_back(
328 ColWithRatio(
col, std::abs(reduced_costs[
col]), std::abs(coeff)));
332 std::make_heap(breakpoints_.begin(), breakpoints_.end());
343 Fractional improvement = std::abs(cost_variation);
344 while (!breakpoints_.empty()) {
345 const ColWithRatio top = breakpoints_.front();
348 DCHECK(top.ratio > *step ||
349 (top.ratio == *step && top.coeff_magnitude <= pivot_magnitude));
350 if (top.ratio > *step && top.coeff_magnitude >= pivot_magnitude) {
351 *entering_col = top.col;
353 pivot_magnitude = top.coeff_magnitude;
355 improvement -= top.coeff_magnitude;
360 if (can_decrease.
IsSet(top.col) && can_increase.
IsSet(top.col) &&
361 std::abs(reduced_costs[top.col]) > threshold) {
362 improvement -= top.coeff_magnitude;
365 if (improvement <= 0.0)
break;
366 std::pop_heap(breakpoints_.begin(), breakpoints_.end());
367 breakpoints_.pop_back();
383 if (unused_columns_.
size() != num_cols) {
389 for (ColIndex
col(0);
col < num_cols; ++
col) {
398 return &unused_columns_;
401 template <
bool normalize,
bool nested_pricing>
402 void EnteringVariable::DantzigChooseEnteringColumn(ColIndex* entering_col) {
404 const DenseRow& matrix_column_norms =
412 if (nested_pricing && !unused_columns_.
IsSet(
col))
continue;
413 const Fractional unormalized_price = std::abs(reduced_costs[
col]);
415 if (unormalized_price > best_price * matrix_column_norms[
col]) {
416 best_price = unormalized_price / matrix_column_norms[
col];
420 if (unormalized_price > best_price) {
421 best_price = unormalized_price;
433 template <
bool use_steepest_edge>
434 void EnteringVariable::NormalizedChooseEnteringColumn(ColIndex* entering_col) {
435 const DenseRow& weights = use_steepest_edge
443 equivalent_entering_choices_.clear();
445 if (use_steepest_edge) {
448 if (squared_reduced_cost >= best_price * weights[
col]) {
449 if (squared_reduced_cost == best_price * weights[
col]) {
450 equivalent_entering_choices_.push_back(
col);
453 equivalent_entering_choices_.clear();
454 best_price = squared_reduced_cost / weights[
col];
458 const Fractional positive_reduced_cost = std::abs(reduced_costs[
col]);
459 if (positive_reduced_cost >= best_price * weights[
col]) {
460 if (positive_reduced_cost == best_price * weights[
col]) {
461 equivalent_entering_choices_.push_back(
col);
464 equivalent_entering_choices_.clear();
465 best_price = positive_reduced_cost / weights[
col];
471 if (!equivalent_entering_choices_.empty()) {
472 equivalent_entering_choices_.push_back(*entering_col);
474 equivalent_entering_choices_[std::uniform_int_distribution<int>(
475 0, equivalent_entering_choices_.size() - 1)(*random_)];
477 stats_.num_perfect_ties.Add(equivalent_entering_choices_.size()));