| 2777 | } |
| 2778 | |
| 2779 | bool HEkkDual::reachedExactObjectiveBound() { |
| 2780 | // Solving a minimization in dual simplex phase 2, and dual |
| 2781 | // objective exceeds the prescribed upper bound. However, costs |
| 2782 | // will be perturbed, so need to check whether exact dual |
| 2783 | // objective value exceeds the prescribed upper bound. This can be |
| 2784 | // a relatively expensive calculation, so determine whether to do |
| 2785 | // it according to the sparsity of the pivotal row |
| 2786 | bool reached_exact_objective_bound = false; |
| 2787 | double use_row_ap_density = |
| 2788 | std::min(std::max(ekk_instance_.info_.row_ap_density, 0.01), 1.0); |
| 2789 | HighsInt check_frequency = 1.0 / use_row_ap_density; |
| 2790 | assert(check_frequency > 0); |
| 2791 | |
| 2792 | bool check_exact_dual_objective_value = |
| 2793 | ekk_instance_.info_.update_count % check_frequency == 0; |
| 2794 | |
| 2795 | if (check_exact_dual_objective_value) { |
| 2796 | const double objective_bound = ekk_instance_.options_->objective_bound; |
| 2797 | const double perturbed_dual_objective_value = |
| 2798 | ekk_instance_.info_.updated_dual_objective_value; |
| 2799 | const double perturbed_value_residual = |
| 2800 | perturbed_dual_objective_value - objective_bound; |
| 2801 | HVector dual_col; |
| 2802 | HVector dual_row; |
| 2803 | const double exact_dual_objective_value = |
| 2804 | computeExactDualObjectiveValue(dual_col, dual_row); |
| 2805 | const double exact_value_residual = |
| 2806 | exact_dual_objective_value - objective_bound; |
| 2807 | std::string action; |
| 2808 | if (exact_dual_objective_value > objective_bound) { |
| 2809 | highsLogDev( |
| 2810 | ekk_instance_.options_->log_options, HighsLogType::kDetailed, |
| 2811 | "HEkkDual::solvePhase2: %12g = Objective > ObjectiveUB = %12g\n", |
| 2812 | ekk_instance_.info_.updated_dual_objective_value, objective_bound); |
| 2813 | action = "Have DualUB bailout"; |
| 2814 | if (ekk_instance_.info_.costs_perturbed || |
| 2815 | ekk_instance_.info_.costs_shifted) { |
| 2816 | // Remove cost perturbation/shifting |
| 2817 | ekk_instance_.initialiseCost(SimplexAlgorithm::kDual, kSolvePhase2); |
| 2818 | } |
| 2819 | |
| 2820 | // Set the duals as computed in the computeExactDualObjective call |
| 2821 | for (HighsInt i = 0; i < solver_num_col; i++) |
| 2822 | ekk_instance_.info_.workDual_[i] = |
| 2823 | ekk_instance_.info_.workCost_[i] - dual_row.array[i]; |
| 2824 | for (HighsInt i = solver_num_col; i < solver_num_tot; i++) |
| 2825 | ekk_instance_.info_.workDual_[i] = -dual_col.array[i - solver_num_col]; |
| 2826 | |
| 2827 | // Since the computeExactDualObjectiveValue() call succeeded, if there are |
| 2828 | // any dual infeasibilities they can be removed by a bound flip |
| 2829 | force_phase2 = false; |
| 2830 | correctDualInfeasibilities(dualInfeasCount); |
| 2831 | |
| 2832 | // no shifts should have occurred |
| 2833 | assert(!ekk_instance_.info_.costs_shifted); |
| 2834 | reached_exact_objective_bound = true; |
| 2835 | ekk_instance_.model_status_ = HighsModelStatus::kObjectiveBound; |
| 2836 | } else { |
nothing calls this directly
no test coverage detected