highs-sys 1.14.2

Rust binding for the HiGHS linear programming solver. See http://highs.dev.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/*                                                                       */
/*    This file is part of the HiGHS linear optimization suite           */
/*                                                                       */
/*    Available as open-source under the MIT License                     */
/*                                                                       */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/**@file simplex/HEkkControl.cpp
 * @brief
 */

#include "simplex/HEkk.h"

void HEkk::initialiseControl() {
  // Copy tolerances from options
  info_.allow_dual_steepest_edge_to_devex_switch =
      options_->simplex_dual_edge_weight_strategy ==
      kSimplexEdgeWeightStrategyChoose;
  info_.dual_steepest_edge_weight_log_error_threshold =
      options_->dual_steepest_edge_weight_log_error_threshold;
  info_.control_iteration_count0 = iteration_count_;
  // Initialise the densities
  info_.col_aq_density = 0;
  info_.row_ep_density = 0;
  info_.row_ap_density = 0;
  info_.row_DSE_density = 0;
  info_.col_steepest_edge_density = 0;
  info_.col_basic_feasibility_change_density = 0;
  info_.row_basic_feasibility_change_density = 0;
  info_.col_BFRT_density = 0;
  info_.primal_col_density = 0;
  // Set the row_dual_density to 1 since it's assumed all costs are at
  // least perturbed from zero, if not initially nonzero
  info_.dual_col_density = 1;
  // Initialise the data used to determine the switch from DSE to
  // Devex
  info_.costly_DSE_frequency = 0;
  info_.num_costly_DSE_iteration = 0;
  info_.costly_DSE_measure = 0;
  info_.average_log_low_DSE_weight_error = 0;
  info_.average_log_high_DSE_weight_error = 0;
}

void HEkk::updateOperationResultDensity(const double local_density,
                                        double& density) const {
  density = (1 - kRunningAverageMultiplier) * density +
            kRunningAverageMultiplier * local_density;
}

void HEkk::assessDSEWeightError(const double computed_edge_weight,
                                const double updated_edge_weight) {
  // Compute the (relative) dual steepest edge weight error for
  // analysis and debugging
  edge_weight_error_ = std::fabs(updated_edge_weight - computed_edge_weight) /
                       std::max(1.0, computed_edge_weight);
  if (edge_weight_error_ > options_->dual_steepest_edge_weight_error_tolerance)
    highsLogDev(options_->log_options, HighsLogType::kInfo,
                "Dual steepest edge weight error is %g\n", edge_weight_error_);
  // Compute the relative deviation in the updated weight compared
  // with the computed weight
  double weight_relative_deviation;
  if (updated_edge_weight < computed_edge_weight) {
    // Updated weight is low
    weight_relative_deviation = computed_edge_weight / updated_edge_weight;
    info_.average_log_low_DSE_weight_error =
        0.99 * info_.average_log_low_DSE_weight_error +
        0.01 * log(weight_relative_deviation);
  } else {
    // Updated weight is correct or high
    weight_relative_deviation = updated_edge_weight / computed_edge_weight;
    info_.average_log_high_DSE_weight_error =
        0.99 * info_.average_log_high_DSE_weight_error +
        0.01 * log(weight_relative_deviation);
  }
}

bool HEkk::switchToDevex() {
  // Parameters controlling switch from DSE to Devex on cost
  const double kCostlyDseMeasureLimit = 1000.0;
  const double kCostlyDseMinimumDensity = 0.01;
  const double kCostlyDseFractionNumTotalIterationBeforeSwitch = 0.1;
  const double kCostlyDseFractionNumCostlyDseIterationBeforeSwitch = 0.05;
  bool switch_to_devex = false;
  // Firstly consider switching on the basis of NLA cost
  double costly_DSE_measure_denominator;
  costly_DSE_measure_denominator = max(
      max(info_.row_ep_density, info_.col_aq_density), info_.row_ap_density);
  if (costly_DSE_measure_denominator > 0) {
    info_.costly_DSE_measure =
        info_.row_DSE_density / costly_DSE_measure_denominator;
    info_.costly_DSE_measure =
        info_.costly_DSE_measure * info_.costly_DSE_measure;
  } else {
    info_.costly_DSE_measure = 0;
  }
  bool costly_DSE_iteration =
      info_.costly_DSE_measure > kCostlyDseMeasureLimit &&
      info_.row_DSE_density > kCostlyDseMinimumDensity;
  info_.costly_DSE_frequency =
      (1 - kRunningAverageMultiplier) * info_.costly_DSE_frequency;
  if (costly_DSE_iteration) {
    info_.num_costly_DSE_iteration++;
    info_.costly_DSE_frequency += kRunningAverageMultiplier * 1.0;
    // What if non-dual iterations have been performed: need to think about this
    HighsInt local_iteration_count =
        iteration_count_ - info_.control_iteration_count0;
    HighsInt local_num_tot = lp_.num_col_ + lp_.num_row_;
    // Switch to Devex if at least 5% of the (at least) 0.1NumTot iterations
    // have been costly
    switch_to_devex =
        info_.allow_dual_steepest_edge_to_devex_switch &&
        (info_.num_costly_DSE_iteration >
         local_iteration_count *
             kCostlyDseFractionNumCostlyDseIterationBeforeSwitch) &&
        (local_iteration_count >
         kCostlyDseFractionNumTotalIterationBeforeSwitch * local_num_tot);

    if (switch_to_devex) {
      highsLogDev(options_->log_options, HighsLogType::kInfo,
                  "Switch from DSE to Devex after %" HIGHSINT_FORMAT
                  " costly DSE iterations of %" HIGHSINT_FORMAT
                  " with "
                  "densities C_Aq = %11.4g; R_Ep = %11.4g; R_Ap = "
                  "%11.4g; DSE = %11.4g\n",
                  info_.num_costly_DSE_iteration, local_iteration_count,
                  info_.col_aq_density, info_.row_ep_density,
                  info_.row_ap_density, info_.row_DSE_density);
    }
  }
  if (!switch_to_devex) {
    // Secondly consider switching on the basis of weight accuracy
    double local_measure = info_.average_log_low_DSE_weight_error +
                           info_.average_log_high_DSE_weight_error;
    double local_threshold =
        info_.dual_steepest_edge_weight_log_error_threshold;
    switch_to_devex = info_.allow_dual_steepest_edge_to_devex_switch &&
                      local_measure > local_threshold;
    if (switch_to_devex) {
      highsLogDev(options_->log_options, HighsLogType::kInfo,
                  "Switch from DSE to Devex with log error measure of %g > "
                  "%g = threshold\n",
                  local_measure, local_threshold);
    }
  }
  return switch_to_devex;
}