Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
reduced_costs.cc
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
15
16#include <algorithm>
17#include <cstdlib>
18#include <random>
19
20#include "absl/log/check.h"
21#include "absl/log/log.h"
22#include "absl/random/bit_gen_ref.h"
32#include "ortools/util/bitset.h"
33#include "ortools/util/stats.h"
34
35namespace operations_research {
36namespace glop {
37
39 const DenseRow& objective,
40 const RowToColMapping& basis,
41 const VariablesInfo& variables_info,
42 const BasisFactorization& basis_factorization,
43 absl::BitGenRef random)
44 : matrix_(matrix),
45 objective_(objective),
46 basis_(basis),
47 variables_info_(variables_info),
48 basis_factorization_(basis_factorization),
49 random_(random),
50 parameters_(),
51 stats_(),
52 must_refactorize_basis_(false),
53 recompute_basic_objective_left_inverse_(true),
54 recompute_basic_objective_(true),
55 recompute_reduced_costs_(true),
56 are_reduced_costs_precise_(false),
57 are_reduced_costs_recomputed_(false),
58 basic_objective_(),
59 reduced_costs_(),
60 basic_objective_left_inverse_(),
61 dual_feasibility_tolerance_() {}
62
64 return must_refactorize_basis_;
65}
66
68 ColIndex entering_col, const ScatteredColumn& direction) {
69 SCOPED_TIME_STAT(&stats_);
70 if (recompute_basic_objective_) {
71 ComputeBasicObjective();
72 }
73 const Fractional old_reduced_cost = reduced_costs_[entering_col];
74 const Fractional precise_reduced_cost =
75 objective_[entering_col] + cost_perturbations_[entering_col] -
76 ScalarProduct(basic_objective_, direction);
77
78 // Update the reduced cost of the entering variable with the precise version.
79 reduced_costs_[entering_col] = precise_reduced_cost;
80
81 // At this point, we have an entering variable that will move the objective in
82 // the good direction. We check the precision of the reduced cost and edges
83 // norm, but even if they are imprecise, we finish this pivot and will
84 // recompute them during the next call to ChooseEnteringColumn().
85
86 // Estimate the accuracy of the reduced costs using the entering variable.
87 if (!recompute_reduced_costs_) {
88 const Fractional estimated_reduced_costs_accuracy =
89 old_reduced_cost - precise_reduced_cost;
90 const Fractional scale =
91 (std::abs(precise_reduced_cost) <= 1.0) ? 1.0 : precise_reduced_cost;
92 stats_.reduced_costs_accuracy.Add(estimated_reduced_costs_accuracy / scale);
93 if (std::abs(estimated_reduced_costs_accuracy) / scale >
94 parameters_.recompute_reduced_costs_threshold()) {
95 VLOG(1) << "Recomputing reduced costs, value = " << precise_reduced_cost
96 << " error = "
97 << std::abs(precise_reduced_cost - old_reduced_cost);
99 }
100 }
101
102 return precise_reduced_cost;
103}
104
106 SCOPED_TIME_STAT(&stats_);
107 Fractional dual_residual_error(0.0);
108 const RowIndex num_rows = matrix_.num_rows();
109 const DenseRow& dual_values = Transpose(GetDualValues());
110 for (RowIndex row(0); row < num_rows; ++row) {
111 const ColIndex basic_col = basis_[row];
112 const Fractional residual =
113 objective_[basic_col] + cost_perturbations_[basic_col] -
114 matrix_.ColumnScalarProduct(basic_col, dual_values);
115 dual_residual_error = std::max(dual_residual_error, std::abs(residual));
116 }
117 return dual_residual_error;
118}
119
121 SCOPED_TIME_STAT(&stats_);
122
123 // Trigger a recomputation if needed so that reduced_costs_ is valid.
125
126 Fractional maximum_dual_infeasibility = 0.0;
127 const DenseBitRow& can_decrease = variables_info_.GetCanDecreaseBitRow();
128 const DenseBitRow& can_increase = variables_info_.GetCanIncreaseBitRow();
129 for (const ColIndex col : variables_info_.GetIsRelevantBitRow()) {
130 const Fractional rc = reduced_costs_[col];
131 if ((can_increase.IsSet(col) && rc < 0.0) ||
132 (can_decrease.IsSet(col) && rc > 0.0)) {
133 maximum_dual_infeasibility =
134 std::max(maximum_dual_infeasibility, std::abs(rc));
135 }
136 }
137 return maximum_dual_infeasibility;
138}
139
141 SCOPED_TIME_STAT(&stats_);
142
143 // Trigger a recomputation if needed so that reduced_costs_ is valid.
145
146 Fractional maximum_dual_infeasibility = 0.0;
147 const DenseBitRow& can_decrease = variables_info_.GetCanDecreaseBitRow();
148 const DenseBitRow& can_increase = variables_info_.GetCanIncreaseBitRow();
149 const DenseBitRow& is_boxed = variables_info_.GetNonBasicBoxedVariables();
150 for (const ColIndex col : variables_info_.GetNotBasicBitRow()) {
151 if (is_boxed[col]) continue;
152 const Fractional rc = reduced_costs_[col];
153 if ((can_increase.IsSet(col) && rc < 0.0) ||
154 (can_decrease.IsSet(col) && rc > 0.0)) {
155 maximum_dual_infeasibility =
156 std::max(maximum_dual_infeasibility, std::abs(rc));
157 }
158 }
159 return maximum_dual_infeasibility;
160}
161
163 SCOPED_TIME_STAT(&stats_);
164
165 // Trigger a recomputation if needed so that reduced_costs_ is valid.
167
168 Fractional dual_infeasibility_sum = 0.0;
169 const DenseBitRow& can_decrease = variables_info_.GetCanDecreaseBitRow();
170 const DenseBitRow& can_increase = variables_info_.GetCanIncreaseBitRow();
171 for (const ColIndex col : variables_info_.GetIsRelevantBitRow()) {
172 const Fractional rc = reduced_costs_[col];
173 if ((can_increase.IsSet(col) && rc < 0.0) ||
174 (can_decrease.IsSet(col) && rc > 0.0)) {
175 dual_infeasibility_sum += std::abs(std::abs(rc));
176 }
177 }
178 return dual_infeasibility_sum;
179}
180
181void ReducedCosts::UpdateBeforeBasisPivot(ColIndex entering_col,
182 RowIndex leaving_row,
183 const ScatteredColumn& direction,
184 UpdateRow* update_row) {
185 SCOPED_TIME_STAT(&stats_);
186 const ColIndex leaving_col = basis_[leaving_row];
187 DCHECK(!variables_info_.GetIsBasicBitRow().IsSet(entering_col));
188 DCHECK(variables_info_.GetIsBasicBitRow().IsSet(leaving_col));
189
190 // If we are recomputing everything when requested, no need to update.
191 if (!recompute_reduced_costs_) {
192 UpdateReducedCosts(entering_col, leaving_col, leaving_row,
193 direction[leaving_row], update_row);
194 }
195
196 // Note that it is important to update basic_objective_ AFTER calling
197 // UpdateReducedCosts().
198 UpdateBasicObjective(entering_col, leaving_row);
199}
200
202 Fractional* current_cost) {
203 DCHECK_NE(variables_info_.GetStatusRow()[col], VariableStatus::BASIC);
204 DCHECK_EQ(current_cost, &objective_[col]);
205 reduced_costs_[col] -= objective_[col];
206 *current_cost = 0.0;
207}
208
210 parameters_ = parameters;
211}
212
214 SCOPED_TIME_STAT(&stats_);
215 recompute_basic_objective_ = true;
216 recompute_basic_objective_left_inverse_ = true;
217 are_reduced_costs_precise_ = false;
218 SetRecomputeReducedCostsAndNotifyWatchers();
219}
220
222 SCOPED_TIME_STAT(&stats_);
223 recompute_basic_objective_ = true;
224 recompute_basic_objective_left_inverse_ = true;
225}
226
228 SCOPED_TIME_STAT(&stats_);
229 if (are_reduced_costs_precise_) return;
230 must_refactorize_basis_ = true;
231 recompute_basic_objective_left_inverse_ = true;
232 SetRecomputeReducedCostsAndNotifyWatchers();
233}
234
236 SCOPED_TIME_STAT(&stats_);
237 VLOG(1) << "Perturbing the costs ... ";
238
239 Fractional max_cost_magnitude = 0.0;
240 const ColIndex structural_size =
241 matrix_.num_cols() - RowToColIndex(matrix_.num_rows());
242 for (ColIndex col(0); col < structural_size; ++col) {
243 max_cost_magnitude =
244 std::max(max_cost_magnitude, std::abs(objective_[col]));
245 }
246
247 cost_perturbations_.AssignToZero(matrix_.num_cols());
248 for (ColIndex col(0); col < structural_size; ++col) {
249 const Fractional objective = objective_[col];
250 const Fractional magnitude =
251 (1.0 + std::uniform_real_distribution<double>()(random_)) *
252 (parameters_.relative_cost_perturbation() * std::abs(objective) +
253 parameters_.relative_max_cost_perturbation() * max_cost_magnitude);
254 DCHECK_GE(magnitude, 0.0);
255
256 // The perturbation direction is such that a dual-feasible solution stays
257 // feasible. This is important.
258 const VariableType type = variables_info_.GetTypeRow()[col];
259 switch (type) {
261 break;
263 break;
265 cost_perturbations_[col] = magnitude;
266 break;
268 cost_perturbations_[col] = -magnitude;
269 break;
271 // Here we don't necessarily maintain the dual-feasibility of a dual
272 // feasible solution, however we can always shift the variable to its
273 // other bound (because it is boxed) to restore dual-feasibility. This
274 // is done by MakeBoxedVariableDualFeasible() at the end of the dual
275 // phase-I algorithm.
276 if (objective > 0.0) {
277 cost_perturbations_[col] = magnitude;
278 } else if (objective < 0.0) {
279 cost_perturbations_[col] = -magnitude;
280 }
281 break;
282 }
283 }
284}
285
286void ReducedCosts::ShiftCostIfNeeded(bool increasing_rc_is_needed,
287 ColIndex col) {
288 SCOPED_TIME_STAT(&stats_);
289
290 // We always want a minimum step size, so if we have a negative step or
291 // a step that is really small, we will shift the cost of the given column.
292 const Fractional minimum_delta =
293 parameters_.degenerate_ministep_factor() * dual_feasibility_tolerance_;
294 if (increasing_rc_is_needed && reduced_costs_[col] <= -minimum_delta) return;
295 if (!increasing_rc_is_needed && reduced_costs_[col] >= minimum_delta) return;
296
297 const Fractional delta =
298 increasing_rc_is_needed ? minimum_delta : -minimum_delta;
299 IF_STATS_ENABLED(stats_.cost_shift.Add(reduced_costs_[col] + delta));
300 cost_perturbations_[col] -= reduced_costs_[col] + delta;
301 reduced_costs_[col] = -delta;
302 has_cost_shift_ = true;
303}
304
305bool ReducedCosts::StepIsDualDegenerate(bool increasing_rc_is_needed,
306 ColIndex col) {
307 if (increasing_rc_is_needed && reduced_costs_[col] >= 0.0) return true;
308 if (!increasing_rc_is_needed && reduced_costs_[col] <= 0.0) return true;
309 return false;
310}
311
313 SCOPED_TIME_STAT(&stats_);
314 has_cost_shift_ = false;
315 cost_perturbations_.AssignToZero(matrix_.num_cols());
316 recompute_basic_objective_ = true;
317 recompute_basic_objective_left_inverse_ = true;
318 are_reduced_costs_precise_ = false;
319 SetRecomputeReducedCostsAndNotifyWatchers();
320}
321
323 SCOPED_TIME_STAT(&stats_);
324 if (!are_reduced_costs_recomputed_) {
325 SetRecomputeReducedCostsAndNotifyWatchers();
326 }
327 return GetReducedCosts();
328}
329
331 SCOPED_TIME_STAT(&stats_);
332 if (basis_factorization_.IsRefactorized()) {
333 must_refactorize_basis_ = false;
334 }
335 if (recompute_reduced_costs_) {
336 ComputeReducedCosts();
337 }
338 return reduced_costs_.const_view();
339}
340
342 SCOPED_TIME_STAT(&stats_);
343 ComputeBasicObjectiveLeftInverse();
344 return Transpose(basic_objective_left_inverse_.values);
345}
346
347void ReducedCosts::ComputeBasicObjective() {
348 SCOPED_TIME_STAT(&stats_);
349 const ColIndex num_cols_in_basis = RowToColIndex(matrix_.num_rows());
350 cost_perturbations_.resize(matrix_.num_cols(), 0.0);
351 basic_objective_.resize(num_cols_in_basis, 0.0);
352 for (ColIndex col(0); col < num_cols_in_basis; ++col) {
353 const ColIndex basis_col = basis_[ColToRowIndex(col)];
354 basic_objective_[col] =
355 objective_[basis_col] + cost_perturbations_[basis_col];
356 }
357 recompute_basic_objective_ = false;
358 recompute_basic_objective_left_inverse_ = true;
359}
360
361void ReducedCosts::ComputeReducedCosts() {
362 SCOPED_TIME_STAT(&stats_);
363 if (recompute_basic_objective_left_inverse_) {
364 ComputeBasicObjectiveLeftInverse();
365 }
366 Fractional dual_residual_error(0.0);
367 const ColIndex num_cols = matrix_.num_cols();
368 const ColIndex first_slack = num_cols - RowToColIndex(matrix_.num_rows());
369
370 reduced_costs_.resize(num_cols, 0.0);
371 const DenseBitRow& is_basic = variables_info_.GetIsBasicBitRow();
372 for (ColIndex col(0); col < first_slack; ++col) {
373 reduced_costs_[col] =
374 objective_[col] + cost_perturbations_[col] -
375 matrix_.ColumnScalarProduct(col, basic_objective_left_inverse_.values);
376
377 // We also compute the dual residual error y.B - c_B.
378 if (is_basic.IsSet(col)) {
379 dual_residual_error =
380 std::max(dual_residual_error, std::abs(reduced_costs_[col]));
381 }
382 }
383 for (ColIndex col(first_slack); col < num_cols; ++col) {
384 reduced_costs_[col] = objective_[col] + cost_perturbations_[col] -
385 basic_objective_left_inverse_[col - first_slack];
386
387 // We also compute the dual residual error y.B - c_B.
388 if (is_basic.IsSet(col)) {
389 dual_residual_error =
390 std::max(dual_residual_error, std::abs(reduced_costs_[col]));
391 }
392 }
393
394 deterministic_time_ +=
395 DeterministicTimeForFpOperations(matrix_.num_entries().value());
396 recompute_reduced_costs_ = false;
397 are_reduced_costs_recomputed_ = true;
398 are_reduced_costs_precise_ = basis_factorization_.IsRefactorized();
399
400 // It is not reasonable to have a dual tolerance lower than the current
401 // dual_residual_error, otherwise we may never terminate (This is happening on
402 // dfl001.mps with a low dual_feasibility_tolerance). Note that since we
403 // recompute the reduced costs with maximum precision before really exiting,
404 // it is fine to do a couple of iterations with a high zero tolerance.
405 dual_feasibility_tolerance_ = parameters_.dual_feasibility_tolerance();
406 if (dual_residual_error > dual_feasibility_tolerance_) {
407 VLOG(2) << "Changing dual_feasibility_tolerance to " << dual_residual_error;
408 dual_feasibility_tolerance_ = dual_residual_error;
409 }
410}
411
412void ReducedCosts::ComputeBasicObjectiveLeftInverse() {
413 SCOPED_TIME_STAT(&stats_);
414 if (recompute_basic_objective_) {
415 ComputeBasicObjective();
416 }
417 basic_objective_left_inverse_.values = basic_objective_;
418 basic_objective_left_inverse_.non_zeros.clear();
419 basis_factorization_.LeftSolve(&basic_objective_left_inverse_);
420 recompute_basic_objective_left_inverse_ = false;
421 IF_STATS_ENABLED(stats_.basic_objective_left_inverse_density.Add(
422 Density(basic_objective_left_inverse_.values)));
423
424 // TODO(user): Estimate its accuracy by a few scalar products, and refactorize
425 // if it is above a threshold?
426}
427
428// Note that the update is such than the entering reduced cost is always set to
429// 0.0. In particular, because of this we can step in the wrong direction for
430// the dual method if the reduced cost is slightly infeasible.
431void ReducedCosts::UpdateReducedCosts(ColIndex entering_col,
432 ColIndex leaving_col,
433 RowIndex leaving_row, Fractional pivot,
434 UpdateRow* update_row) {
435 DCHECK_NE(entering_col, leaving_col);
436 DCHECK_NE(pivot, 0.0);
437 if (recompute_reduced_costs_) return;
438
439 // Note that this is precise because of the CheckPrecision().
440 const Fractional entering_reduced_cost = reduced_costs_[entering_col];
441
442 // Nothing to do if the entering reduced cost is 0.0.
443 // This correspond to a dual degenerate pivot.
444 if (entering_reduced_cost == 0.0) {
445 VLOG(2) << "Reduced costs didn't change.";
446
447 // TODO(user): the reduced costs may still be "precise" in this case, but
448 // other parts of the code assume that if they are precise then the basis
449 // was just refactorized in order to recompute them which is not the case
450 // here. Clean this up.
451 are_reduced_costs_precise_ = false;
452 return;
453 }
454
455 are_reduced_costs_recomputed_ = false;
456 are_reduced_costs_precise_ = false;
457 update_row->ComputeUpdateRow(leaving_row);
458 SCOPED_TIME_STAT(&stats_);
459
460 // Update the leaving variable reduced cost.
461 // '-pivot' is the value of the entering_edge at 'leaving_row'.
462 // The edge of the 'leaving_col' in the new basis is equal to
463 // 'entering_edge / -pivot'.
464 const Fractional new_leaving_reduced_cost = entering_reduced_cost / -pivot;
465 auto rc = reduced_costs_.view();
466 auto update_coeffs = update_row->GetCoefficients().const_view();
467 for (const ColIndex col : update_row->GetNonZeroPositions()) {
468 rc[col] += new_leaving_reduced_cost * update_coeffs[col];
469 }
470 rc[leaving_col] = new_leaving_reduced_cost;
471
472 // In the dual, since we compute the update before selecting the entering
473 // variable, this cost is still in the update_position_list, so we make sure
474 // it is 0 here.
475 rc[entering_col] = 0.0;
476}
477
479 const Fractional reduced_cost = reduced_costs_[col];
480 const DenseBitRow& can_decrease = variables_info_.GetCanDecreaseBitRow();
481 const DenseBitRow& can_increase = variables_info_.GetCanIncreaseBitRow();
482 const Fractional tolerance = dual_feasibility_tolerance_;
483 return (can_increase.IsSet(col) && (reduced_cost < -tolerance)) ||
484 (can_decrease.IsSet(col) && (reduced_cost > tolerance));
485}
486
487void ReducedCosts::UpdateBasicObjective(ColIndex entering_col,
488 RowIndex leaving_row) {
489 SCOPED_TIME_STAT(&stats_);
490 basic_objective_[RowToColIndex(leaving_row)] =
491 objective_[entering_col] + cost_perturbations_[entering_col];
492 recompute_basic_objective_left_inverse_ = true;
493}
494
495void ReducedCosts::SetRecomputeReducedCostsAndNotifyWatchers() {
496 recompute_reduced_costs_ = true;
497 for (bool* watcher : watchers_) *watcher = true;
498}
499
500PrimalPrices::PrimalPrices(absl::BitGenRef random,
501 const VariablesInfo& variables_info,
502 PrimalEdgeNorms* primal_edge_norms,
503 ReducedCosts* reduced_costs)
504 : prices_(random),
505 variables_info_(variables_info),
506 primal_edge_norms_(primal_edge_norms),
507 reduced_costs_(reduced_costs) {
508 reduced_costs_->AddRecomputationWatcher(&recompute_);
509 primal_edge_norms->AddRecomputationWatcher(&recompute_);
510}
511
512void PrimalPrices::UpdateBeforeBasisPivot(ColIndex entering_col,
513 UpdateRow* update_row) {
514 // If we are recomputing everything when requested, no need to update.
515 if (recompute_) return;
516
517 // Note that the set of positions works because both the reduced costs
518 // and the primal edge norms are updated on the same positions which are
519 // given by the update_row.
520 UpdateEnteringCandidates</*from_clean_state=*/false>(
521 update_row->GetNonZeroPositions());
522
523 // This should be redundant with the call above, except in degenerate
524 // cases where the update_row has a zero position on the entering col!
525 prices_.Remove(entering_col);
526}
527
529 if (recompute_) return;
530 if (reduced_costs_->IsValidPrimalEnteringCandidate(col)) {
531 const DenseRow::ConstView squared_norms =
532 primal_edge_norms_->GetSquaredNorms();
533 const DenseRow::ConstView reduced_costs = reduced_costs_->GetReducedCosts();
534 DCHECK_NE(0.0, squared_norms[col]);
535 prices_.AddOrUpdate(col, Square(reduced_costs[col]) / squared_norms[col]);
536 } else {
537 prices_.Remove(col);
538 }
539}
540
542 // If we need a recomputation, we cannot assumes that the reduced costs are
543 // valid until we are about to recompute the prices.
544 if (recompute_) return;
545
546 DCHECK(!reduced_costs_->IsValidPrimalEnteringCandidate(col));
547 prices_.Remove(col);
548}
549
551 if (recompute_) {
552 const DenseRow::ConstView reduced_costs = reduced_costs_->GetReducedCosts();
553 prices_.ClearAndResize(reduced_costs.size());
554 UpdateEnteringCandidates</*from_clean_state=*/true>(
555 variables_info_.GetIsRelevantBitRow());
556 recompute_ = false;
557 }
558 return prices_.GetMaximum();
559}
560
561// A variable is an entering candidate if it can move in a direction that
562// minimizes the objective. That is, its value needs to increase if its
563// reduced cost is negative or it needs to decrease if its reduced cost is
564// positive (see the IsValidPrimalEnteringCandidate() function). Note that
565// this is the same as a dual-infeasible variable.
566template <bool from_clean_state, typename ColumnsToUpdate>
567void PrimalPrices::UpdateEnteringCandidates(const ColumnsToUpdate& cols) {
568 const Fractional tolerance = reduced_costs_->GetDualFeasibilityTolerance();
569 const DenseBitRow::ConstView can_decrease =
570 variables_info_.GetCanDecreaseBitRow().const_view();
571 const DenseBitRow::ConstView can_increase =
572 variables_info_.GetCanIncreaseBitRow().const_view();
573 const DenseRow::ConstView squared_norms =
574 primal_edge_norms_->GetSquaredNorms();
575 const DenseRow::ConstView reduced_costs = reduced_costs_->GetReducedCosts();
576 for (const ColIndex col : cols) {
577 const Fractional reduced_cost = reduced_costs[col];
578
579 // Optimization for speed (The function is about 30% faster than the code in
580 // IsValidPrimalEnteringCandidate() or a switch() on variable_status[col]).
581 // This relies on the fact that (double1 > double2) returns a 1 or 0 result
582 // when converted to an int. It also uses an XOR (which appears to be
583 // faster) since the two conditions on the reduced cost are exclusive.
584 const bool is_dual_infeasible = Bitset64<ColIndex>::ConditionalXorOfTwoBits(
585 col, reduced_cost > tolerance, can_decrease, reduced_cost < -tolerance,
586 can_increase);
587 if (is_dual_infeasible) {
588 DCHECK(reduced_costs_->IsValidPrimalEnteringCandidate(col));
589 const Fractional price = Square(reduced_cost) / squared_norms[col];
590 prices_.AddOrUpdate(col, price);
591 } else {
592 DCHECK(!reduced_costs_->IsValidPrimalEnteringCandidate(col));
593 if (!from_clean_state) prices_.Remove(col);
594 }
595 }
596}
597
598} // namespace glop
599} // namespace operations_research
bool IsSet(IndexType i) const
Returns true if the bit at position i is set.
Definition bitset.h:533
static uint64_t ConditionalXorOfTwoBits(IndexType i, uint64_t use1, Bitset64< IndexType >::ConstView set1, uint64_t use2, Bitset64< IndexType >::ConstView set2)
Definition bitset.h:708
ConstView const_view() const
Definition bitset.h:459
void Remove(Index position)
Removes the given index from the set of candidates.
Definition pricing.h:171
void AddOrUpdate(Index position, Fractional value)
Definition pricing.h:192
void RecomputePriceAt(ColIndex col)
Triggers a recomputation of the price at the given column only.
void SetAndDebugCheckThatColumnIsDualFeasible(ColIndex col)
void UpdateBeforeBasisPivot(ColIndex entering_col, UpdateRow *update_row)
PrimalPrices(absl::BitGenRef random, const VariablesInfo &variables_info, PrimalEdgeNorms *primal_edge_norms, ReducedCosts *reduced_costs)
void SetNonBasicVariableCostToZero(ColIndex col, Fractional *current_cost)
Fractional ComputeMaximumDualInfeasibilityOnNonBoxedVariables()
Fractional GetDualFeasibilityTolerance() const
Returns the current dual feasibility tolerance.
void SetParameters(const GlopParameters &parameters)
Sets the pricing parameters. This does not change the pricing rule.
bool StepIsDualDegenerate(bool increasing_rc_is_needed, ColIndex col)
Fractional TestEnteringReducedCostPrecision(ColIndex entering_col, const ScatteredColumn &direction)
bool IsValidPrimalEnteringCandidate(ColIndex col) const
Does basic checking of an entering candidate.
void UpdateDataOnBasisPermutation()
Invalidates the data that depends on the order of the column in basis_.
ReducedCosts(const CompactSparseMatrix &matrix_, const DenseRow &objective, const RowToColMapping &basis, const VariablesInfo &variables_info, const BasisFactorization &basis_factorization, absl::BitGenRef random)
Takes references to the linear program data we need.
const DenseColumn & GetDualValues()
Returns the dual values associated to the current basis.
void ShiftCostIfNeeded(bool increasing_rc_is_needed, ColIndex col)
void UpdateBeforeBasisPivot(ColIndex entering_col, RowIndex leaving_row, const ScatteredColumn &direction, UpdateRow *update_row)
void ResetForNewObjective()
Invalidates all internal structure that depends on the objective function.
StrictITISpan< ColIndex, const Fractional > ConstView
Definition lp_types.h:291
absl::Span< const ColIndex > GetNonZeroPositions() const
const DenseBitRow & GetCanDecreaseBitRow() const
const DenseBitRow & GetCanIncreaseBitRow() const
double Density(const DenseRow &row)
Definition lp_utils.cc:176
StrictITIVector< RowIndex, ColIndex > RowToColMapping
Definition lp_types.h:394
Fractional Square(Fractional f)
Definition lp_utils.h:41
Fractional ScalarProduct(const DenseRowOrColumn1 &u, const DenseRowOrColumn2 &v)
Definition lp_utils.h:52
Bitset64< ColIndex > DenseBitRow
Row of bits.
Definition lp_types.h:375
const DenseRow & Transpose(const DenseColumn &col)
Similar comment as the other Transpose() implementation above.
Definition lp_utils.h:199
ColIndex RowToColIndex(RowIndex row)
Get the ColIndex corresponding to the column # row.
Definition lp_types.h:54
VariableType
Different types of variables.
Definition lp_types.h:178
RowIndex ColToRowIndex(ColIndex col)
Get the RowIndex corresponding to the row # col.
Definition lp_types.h:57
StrictITIVector< RowIndex, Fractional > DenseColumn
Column-vector types. Column-vector types are indexed by a row index.
Definition lp_types.h:380
StrictITIVector< ColIndex, Fractional > DenseRow
Row-vector types. Row-vector types are indexed by a column index.
Definition lp_types.h:351
static double DeterministicTimeForFpOperations(int64_t n)
Definition lp_types.h:433
In SWIG mode, we don't want anything besides these top-level includes.
#define IF_STATS_ENABLED(instructions)
Definition stats.h:414
#define SCOPED_TIME_STAT(stats)
Definition stats.h:421