21 #include "absl/container/flat_hash_map.h"
22 #include "absl/strings/str_cat.h"
23 #include "absl/strings/str_format.h"
39 DCHECK(!std::isnan(lower_bound));
40 DCHECK(!std::isnan(upper_bound));
52 lower_bound != upper_bound) {
58 template <
class I,
class T>
60 const size_t size = v.
size();
64 for (I i(0); i < size; ++i) {
65 if (v[i] == 0.0)
continue;
67 sum +=
static_cast<double>(v[i].value());
69 return n == 0.0 ? 0.0 : sum / n;
72 template <
class I,
class T>
74 const size_t size = v.
size();
76 double sigma_square = 0.0;
78 for (I i(0); i < size; ++i) {
79 double sample =
static_cast<double>(v[i].value());
80 if (sample == 0.0)
continue;
81 sigma_square += sample * sample;
85 return n == 0.0 ? 0.0 : sqrt((sigma_square - sigma * sigma / n) / n);
89 template <
class I,
class T>
91 const size_t size = v.
size();
96 T max_index = v[I(0)];
97 for (I i(1); i < size; ++i) {
98 if (max_index < v[i]) {
113 constraint_lower_bounds_(),
114 constraint_upper_bounds_(),
116 objective_coefficients_(),
117 variable_lower_bounds_(),
118 variable_upper_bounds_(),
121 integer_variables_list_(),
124 objective_offset_(0.0),
125 objective_scaling_factor_(1.0),
127 columns_are_known_to_be_clean_(true),
128 transpose_matrix_is_consistent_(true),
129 integer_variables_list_is_consistent_(true),
135 transpose_matrix_.
Clear();
137 constraint_lower_bounds_.
clear();
138 constraint_upper_bounds_.
clear();
139 constraint_names_.
clear();
141 objective_coefficients_.
clear();
142 variable_lower_bounds_.
clear();
143 variable_upper_bounds_.
clear();
144 variable_types_.
clear();
145 integer_variables_list_.clear();
146 variable_names_.
clear();
148 constraint_table_.clear();
149 variable_table_.clear();
152 objective_offset_ = 0.0;
153 objective_scaling_factor_ = 1.0;
154 columns_are_known_to_be_clean_ =
true;
155 transpose_matrix_is_consistent_ =
true;
156 integer_variables_list_is_consistent_ =
true;
163 <<
"New variables can't be added to programs that already have slack "
164 "variables. Consider calling LinearProgram::DeleteSlackVariables() "
165 "before adding new variables to the problem.";
171 transpose_matrix_is_consistent_ =
false;
178 const std::string&
name) {
180 variable_lower_bounds_.
push_back(lower_bound);
181 variable_upper_bounds_.
push_back(upper_bound);
182 variable_types_.
push_back(is_integer_slack_variable
186 transpose_matrix_is_consistent_ =
false;
192 <<
"New constraints can't be added to programs that already have slack "
193 "variables. Consider calling LinearProgram::DeleteSlackVariables() "
194 "before adding new variables to the problem.";
195 const RowIndex
row(constraint_names_.
size());
200 transpose_matrix_is_consistent_ =
false;
205 const absl::flat_hash_map<std::string, ColIndex>::iterator it =
206 variable_table_.find(variable_id);
207 if (it != variable_table_.end()) {
211 variable_names_[
col] = variable_id;
212 variable_table_[variable_id] =
col;
218 const std::string& constraint_id) {
219 const absl::flat_hash_map<std::string, RowIndex>::iterator it =
220 constraint_table_.find(constraint_id);
221 if (it != constraint_table_.end()) {
225 constraint_names_[
row] = constraint_id;
226 constraint_table_[constraint_id] =
row;
232 variable_names_[
col] = std::string(
name);
237 variable_types_[
col] = type;
239 if (var_is_integer != var_was_integer) {
240 integer_variables_list_is_consistent_ =
false;
245 constraint_names_[
row] = std::string(
name);
250 if (dcheck_bounds_) DebugCheckBoundsValid(lower_bound, upper_bound);
252 variable_lower_bounds_[
col] = lower_bound;
253 variable_upper_bounds_[
col] = upper_bound;
255 if (var_is_binary != var_was_binary) {
256 integer_variables_list_is_consistent_ =
false;
260 void LinearProgram::UpdateAllIntegerVariableLists()
const {
261 if (integer_variables_list_is_consistent_)
return;
262 integer_variables_list_.clear();
263 binary_variables_list_.clear();
264 non_binary_variables_list_.clear();
266 for (ColIndex
col(0);
col < num_cols; ++
col) {
268 integer_variables_list_.push_back(
col);
270 binary_variables_list_.push_back(
col);
272 non_binary_variables_list_.push_back(
col);
276 integer_variables_list_is_consistent_ =
true;
280 UpdateAllIntegerVariableLists();
281 return integer_variables_list_;
285 UpdateAllIntegerVariableLists();
286 return binary_variables_list_;
290 UpdateAllIntegerVariableLists();
291 return non_binary_variables_list_;
305 (variable_upper_bounds_[
col] < 2);
310 if (dcheck_bounds_) DebugCheckBoundsValid(lower_bound, upper_bound);
311 ResizeRowsIfNeeded(
row);
312 constraint_lower_bounds_[
row] = lower_bound;
313 constraint_upper_bounds_[
row] = upper_bound;
319 ResizeRowsIfNeeded(
row);
320 columns_are_known_to_be_clean_ =
false;
321 transpose_matrix_is_consistent_ =
false;
327 objective_coefficients_[
col] =
value;
343 maximize_ = maximize;
347 if (columns_are_known_to_be_clean_)
return;
349 columns_are_known_to_be_clean_ =
true;
350 transpose_matrix_is_consistent_ =
false;
354 if (columns_are_known_to_be_clean_)
return true;
355 columns_are_known_to_be_clean_ = matrix_.
IsCleanedUp();
356 return columns_are_known_to_be_clean_;
361 ? absl::StrFormat(
"c%d",
col.value())
362 : variable_names_[
col];
366 return row >= constraint_names_.
size() || constraint_names_[
row].
empty()
367 ? absl::StrFormat(
"r%d",
row.value())
368 : constraint_names_[
row];
372 return variable_types_[
col];
376 if (!transpose_matrix_is_consistent_) {
378 transpose_matrix_is_consistent_ =
true;
382 return transpose_matrix_;
386 if (!transpose_matrix_is_consistent_) {
392 transpose_matrix_is_consistent_ =
false;
393 return &transpose_matrix_;
400 transpose_matrix_is_consistent_ =
true;
404 transpose_matrix_.
Clear();
405 transpose_matrix_is_consistent_ =
false;
413 columns_are_known_to_be_clean_ =
false;
414 transpose_matrix_is_consistent_ =
false;
419 ColIndex
col)
const {
428 return absl::StrFormat(
429 "%d rows, %d columns, %d entries with magnitude in [%e, %e]",
437 template <
typename FractionalValues>
438 void UpdateStats(
const FractionalValues& values,
int64* num_non_zeros,
442 *min_value =
std::min(*min_value, v);
443 *max_value =
std::max(*max_value, v);
451 int64 num_non_zeros = 0;
454 UpdateStats(objective_coefficients_, &num_non_zeros, &min_value, &max_value);
455 if (num_non_zeros == 0) {
456 return "No objective term. This is a pure feasibility problem.";
458 return absl::StrFormat(
"%d non-zeros, range [%e, %e]", num_non_zeros,
459 min_value, max_value);
464 int64 num_non_zeros = 0;
467 UpdateStats(variable_lower_bounds_, &num_non_zeros, &min_value, &max_value);
468 UpdateStats(variable_upper_bounds_, &num_non_zeros, &min_value, &max_value);
469 UpdateStats(constraint_lower_bounds_, &num_non_zeros, &min_value, &max_value);
470 UpdateStats(constraint_upper_bounds_, &num_non_zeros, &min_value, &max_value);
471 if (num_non_zeros == 0) {
472 return "All variables/constraints bounds are zero or +/- infinity.";
474 return absl::StrFormat(
"%d non-zeros, range [%e, %e]", num_non_zeros,
475 min_value, max_value);
484 for (ColIndex
col = ColIndex(0);
col < num_cols; ++
col) {
488 if (lb_error > absolute_tolerance || ub_error > absolute_tolerance) {
502 for (RowIndex
row = RowIndex(0);
row < num_rows; ++
row) {
508 if (lb_error > absolute_tolerance || ub_error > absolute_tolerance) {
521 const Fractional fractionality = fabs(solution[
col] - round(solution[
col]));
522 if (fractionality > absolute_tolerance)
return false;
534 CHECK(solution !=
nullptr);
539 for (RowIndex
row = RowIndex(0);
row < num_rows; ++
row) {
544 (*solution)[slack_variable] = -sum;
560 std::string output = maximize_ ?
"max:" :
"min:";
561 if (objective_offset_ != 0.0) {
565 for (ColIndex
col(0);
col < num_cols; ++
col) {
571 output.append(
";\n");
575 for (RowIndex
row(0);
row < num_rows; ++
row) {
580 if (AreBoundsFreeOrBoxed(lower_bound, upper_bound)) {
585 for (ColIndex
col(0);
col < num_cols; ++
col) {
589 if (AreBoundsFreeOrBoxed(lower_bound, upper_bound)) {
592 }
else if (lower_bound == upper_bound) {
606 for (ColIndex
col(0);
col < num_cols; ++
col) {
609 if (AreBoundsFreeOrBoxed(lower_bound, upper_bound)) {
614 if (AreBoundsFreeOrBoxed(lower_bound, upper_bound)) {
617 }
else if (lower_bound == upper_bound) {
633 if (!integer_variables.empty()) {
635 for (ColIndex
col : integer_variables) {
649 if (!output.empty()) absl::StrAppend(&output,
", ");
651 (variable_values[
col]));
657 return ProblemStatFormatter(
658 "%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,"
663 return ProblemStatFormatter(
664 "Number of rows : %d\n"
665 "Number of variables in file : %d\n"
666 "Number of entries (non-zeros) : %d\n"
667 "Number of entries in the objective : %d\n"
668 "Number of entries in the right-hand side : %d\n"
669 "Number of <= constraints : %d\n"
670 "Number of >= constraints : %d\n"
671 "Number of = constraints : %d\n"
672 "Number of range constraints : %d\n"
673 "Number of non-negative variables : %d\n"
674 "Number of boxed variables : %d\n"
675 "Number of free variables : %d\n"
676 "Number of fixed variables : %d\n"
677 "Number of other variables : %d\n"
678 "Number of integer variables : %d\n"
679 "Number of binary variables : %d\n"
680 "Number of non-binary integer variables : %d\n"
681 "Number of continuous variables : %d\n");
685 return NonZeroStatFormatter(
"%.2f%%,%d,%.2f,%.2f,%d,%.2f,%.2f");
689 return NonZeroStatFormatter(
690 "Fill rate : %.2f%%\n"
691 "Entries in row (Max / average / std. dev.) : %d / %.2f / %.2f\n"
692 "Entries in column (Max / average / std. dev.): %d / %.2f / %.2f\n");
696 bool detect_integer_constraints) {
712 detect_integer_constraints);
713 if (detect_integer_constraints) {
718 const RowIndex
row = entry.row();
719 has_integer_slack_variable[
row] =
720 has_integer_slack_variable[
row] && is_integer_variable &&
721 round(entry.coefficient()) == entry.coefficient();
731 slack_variable_index < original_num_variables) {
736 has_integer_slack_variable[
row], -constraint_upper_bounds_[
row],
737 -constraint_lower_bounds_[
row], absl::StrCat(
"s",
row.value()));
742 columns_are_known_to_be_clean_ =
true;
743 transpose_matrix_is_consistent_ =
false;
745 first_slack_variable_ = original_num_variables;
750 return first_slack_variable_;
780 for (RowIndex dual_row(0); dual_row < dual_num_constraints; ++dual_row) {
785 if (lower_bound == upper_bound) {
798 LOG(DFATAL) <<
"PopulateFromDual() was called with a program "
799 <<
"containing free constraints.";
803 for (ColIndex dual_col(0); dual_col < dual_num_variables; ++dual_col) {
814 for (ColIndex dual_col(0); dual_col < dual_num_variables; ++dual_col) {
825 for (ColIndex dual_col(0); dual_col < dual_num_variables; ++dual_col) {
831 const RowIndex dual_row = e.row();
839 for (RowIndex dual_row(0); dual_row < dual_num_constraints; ++dual_row) {
842 if (AreBoundsFreeOrBoxed(lower_bound, upper_bound)) {
851 (*duplicated_rows)[dual_row] =
col;
856 columns_are_known_to_be_clean_ =
true;
857 transpose_matrix_is_consistent_ =
false;
863 if (linear_program.transpose_matrix_is_consistent_) {
864 transpose_matrix_is_consistent_ =
true;
866 linear_program.transpose_matrix_);
868 transpose_matrix_is_consistent_ =
false;
869 transpose_matrix_.
Clear();
872 constraint_lower_bounds_ = linear_program.constraint_lower_bounds_;
873 constraint_upper_bounds_ = linear_program.constraint_upper_bounds_;
874 constraint_names_ = linear_program.constraint_names_;
875 constraint_table_.clear();
877 PopulateNameObjectiveAndVariablesFromLinearProgram(linear_program);
878 first_slack_variable_ = linear_program.first_slack_variable_;
894 inverse_col_permutation);
899 &constraint_lower_bounds_);
901 &constraint_upper_bounds_);
905 &objective_coefficients_);
907 &variable_lower_bounds_);
909 &variable_upper_bounds_);
911 integer_variables_list_is_consistent_ =
false;
917 const RowIndex new_row = row_permutation[old_row];
918 constraint_names_[new_row] = lp.constraint_names_[old_row];
921 for (ColIndex old_col(0); old_col < lp.
num_variables(); ++old_col) {
922 const ColIndex new_col = col_permutation[old_col];
923 variable_names_[new_col] = lp.variable_names_[old_col];
927 maximize_ = lp.maximize_;
928 objective_offset_ = lp.objective_offset_;
929 objective_scaling_factor_ = lp.objective_scaling_factor_;
937 transpose_matrix_is_consistent_ =
false;
938 transpose_matrix_.
Clear();
940 constraint_lower_bounds_.
clear();
941 constraint_upper_bounds_.
clear();
942 constraint_names_.
clear();
943 constraint_table_.clear();
945 PopulateNameObjectiveAndVariablesFromLinearProgram(linear_program);
948 void LinearProgram::PopulateNameObjectiveAndVariablesFromLinearProgram(
950 objective_coefficients_ = linear_program.objective_coefficients_;
951 variable_lower_bounds_ = linear_program.variable_lower_bounds_;
952 variable_upper_bounds_ = linear_program.variable_upper_bounds_;
953 variable_names_ = linear_program.variable_names_;
954 variable_types_ = linear_program.variable_types_;
955 integer_variables_list_is_consistent_ =
956 linear_program.integer_variables_list_is_consistent_;
957 integer_variables_list_ = linear_program.integer_variables_list_;
958 binary_variables_list_ = linear_program.binary_variables_list_;
959 non_binary_variables_list_ = linear_program.non_binary_variables_list_;
960 variable_table_.clear();
962 maximize_ = linear_program.maximize_;
963 objective_offset_ = linear_program.objective_offset_;
964 objective_scaling_factor_ = linear_program.objective_scaling_factor_;
965 columns_are_known_to_be_clean_ =
966 linear_program.columns_are_known_to_be_clean_;
967 name_ = linear_program.name_;
974 const RowIndex num_new_constraints =
coefficients.num_rows();
981 transpose_matrix_is_consistent_ =
false;
982 transpose_matrix_.
Clear();
983 columns_are_known_to_be_clean_ =
false;
986 constraint_lower_bounds_.
insert(constraint_lower_bounds_.
end(),
987 left_hand_sides.
begin(),
988 left_hand_sides.
end());
989 constraint_upper_bounds_.
insert(constraint_upper_bounds_.
end(),
990 right_hand_sides.
begin(),
991 right_hand_sides.
end());
999 bool detect_integer_constraints_for_slack) {
1005 const DenseRow& variable_lower_bounds,
1006 const DenseRow& variable_upper_bounds) {
1011 DenseRow new_lower_bounds(num_vars, 0);
1012 DenseRow new_upper_bounds(num_vars, 0);
1013 for (ColIndex i(0); i < num_vars; ++i) {
1018 if (new_lower_bound > new_upper_bound) {
1021 new_lower_bounds[i] = new_lower_bound;
1022 new_upper_bounds[i] = new_upper_bound;
1024 variable_lower_bounds_.
swap(new_lower_bounds);
1025 variable_upper_bounds_.
swap(new_upper_bounds);
1030 matrix_.
Swap(&linear_program->matrix_);
1031 transpose_matrix_.
Swap(&linear_program->transpose_matrix_);
1033 constraint_lower_bounds_.
swap(linear_program->constraint_lower_bounds_);
1034 constraint_upper_bounds_.
swap(linear_program->constraint_upper_bounds_);
1035 constraint_names_.
swap(linear_program->constraint_names_);
1037 objective_coefficients_.
swap(linear_program->objective_coefficients_);
1038 variable_lower_bounds_.
swap(linear_program->variable_lower_bounds_);
1039 variable_upper_bounds_.
swap(linear_program->variable_upper_bounds_);
1040 variable_names_.
swap(linear_program->variable_names_);
1041 variable_types_.
swap(linear_program->variable_types_);
1042 integer_variables_list_.swap(linear_program->integer_variables_list_);
1043 binary_variables_list_.swap(linear_program->binary_variables_list_);
1044 non_binary_variables_list_.swap(linear_program->non_binary_variables_list_);
1046 variable_table_.swap(linear_program->variable_table_);
1047 constraint_table_.swap(linear_program->constraint_table_);
1049 std::swap(maximize_, linear_program->maximize_);
1050 std::swap(objective_offset_, linear_program->objective_offset_);
1051 std::swap(objective_scaling_factor_,
1052 linear_program->objective_scaling_factor_);
1053 std::swap(columns_are_known_to_be_clean_,
1054 linear_program->columns_are_known_to_be_clean_);
1055 std::swap(transpose_matrix_is_consistent_,
1056 linear_program->transpose_matrix_is_consistent_);
1057 std::swap(integer_variables_list_is_consistent_,
1058 linear_program->integer_variables_list_is_consistent_);
1059 name_.swap(linear_program->name_);
1060 std::swap(first_slack_variable_, linear_program->first_slack_variable_);
1064 if (columns_to_delete.
empty())
return;
1065 integer_variables_list_is_consistent_ =
false;
1068 ColIndex new_index(0);
1069 for (ColIndex
col(0);
col < num_cols; ++
col) {
1070 permutation[
col] = new_index;
1071 if (
col >= columns_to_delete.
size() || !columns_to_delete[
col]) {
1072 objective_coefficients_[new_index] = objective_coefficients_[
col];
1073 variable_lower_bounds_[new_index] = variable_lower_bounds_[
col];
1074 variable_upper_bounds_[new_index] = variable_upper_bounds_[
col];
1075 variable_names_[new_index] = variable_names_[
col];
1076 variable_types_[new_index] = variable_types_[
col];
1084 objective_coefficients_.
resize(new_index, 0.0);
1085 variable_lower_bounds_.
resize(new_index, 0.0);
1086 variable_upper_bounds_.
resize(new_index, 0.0);
1088 variable_names_.
resize(new_index,
"");
1091 absl::flat_hash_map<std::string, ColIndex>::iterator it =
1092 variable_table_.begin();
1093 while (it != variable_table_.end()) {
1094 const ColIndex
col = it->second;
1095 if (
col >= columns_to_delete.
size() || !columns_to_delete[
col]) {
1096 it->second = permutation[
col];
1100 variable_table_.erase(it++);
1105 if (transpose_matrix_is_consistent_) {
1116 for (ColIndex slack_variable = first_slack_variable_;
1117 slack_variable < matrix_.
num_cols(); ++slack_variable) {
1123 const RowIndex
row = column.
EntryRow(EntryIndex(0));
1127 -variable_lower_bounds_[slack_variable]);
1128 slack_variables[slack_variable] =
true;
1139 template <
typename FractionalRange>
1140 void UpdateMinAndMaxMagnitude(
const FractionalRange& range,
1145 if (magnitude == 0 || magnitude ==
kInfinity)
continue;
1146 *min_magnitude =
std::min(*min_magnitude, magnitude);
1147 *max_magnitude =
std::max(*max_magnitude, magnitude);
1152 std::vector<Fractional> median;
1154 if (
value == 0.0)
continue;
1155 median.push_back(std::abs(
value));
1157 if (median.empty())
return 1.0;
1158 std::sort(median.begin(), median.end());
1159 return median[median.size() / 2];
1164 int num_non_zeros = 0;
1166 if (
value == 0.0)
continue;
1168 mean += std::abs(
value);
1170 if (num_non_zeros == 0.0)
return 1.0;
1171 return mean /
static_cast<Fractional>(num_non_zeros);
1176 if (min_magnitude > 1.0 && min_magnitude <
kInfinity) {
1177 return min_magnitude;
1178 }
else if (max_magnitude > 0.0 && max_magnitude < 1.0) {
1179 return max_magnitude;
1187 GlopParameters::CostScalingAlgorithm method) {
1194 case GlopParameters::NO_COST_SCALING:
1196 case GlopParameters::CONTAIN_ONE_COST_SCALING:
1197 cost_scaling_factor =
1198 ComputeDivisorSoThatRangeContainsOne(min_magnitude, max_magnitude);
1200 case GlopParameters::MEAN_COST_SCALING:
1203 case GlopParameters::MEDIAN_COST_SCALING:
1207 if (cost_scaling_factor != 1.0) {
1216 VLOG(1) <<
"Objective magnitude range is [" << min_magnitude <<
", "
1217 << max_magnitude <<
"] (dividing by " << cost_scaling_factor <<
").";
1218 return cost_scaling_factor;
1233 ComputeDivisorSoThatRangeContainsOne(min_magnitude, max_magnitude);
1234 if (bound_scaling_factor != 1.0) {
1236 bound_scaling_factor);
1250 VLOG(1) <<
"Bounds magnitude range is [" << min_magnitude <<
", "
1251 << max_magnitude <<
"] (dividing bounds by " << bound_scaling_factor
1253 return bound_scaling_factor;
1257 if (rows_to_delete.
empty())
return;
1263 RowIndex new_index(0);
1264 for (RowIndex
row(0);
row < num_rows; ++
row) {
1265 if (
row >= rows_to_delete.
size() || !rows_to_delete[
row]) {
1266 constraint_lower_bounds_[new_index] = constraint_lower_bounds_[
row];
1267 constraint_upper_bounds_[new_index] = constraint_upper_bounds_[
row];
1268 constraint_names_[new_index].
swap(constraint_names_[
row]);
1269 permutation[
row] = new_index;
1275 constraint_lower_bounds_.
resize(new_index, 0.0);
1276 constraint_upper_bounds_.
resize(new_index, 0.0);
1277 constraint_names_.
resize(new_index,
"");
1283 absl::flat_hash_map<std::string, RowIndex>::iterator it =
1284 constraint_table_.begin();
1285 while (it != constraint_table_.end()) {
1286 const RowIndex
row = it->second;
1288 it->second = permutation[
row];
1292 constraint_table_.erase(it++);
1297 if (transpose_matrix_is_consistent_) {
1304 if (!
IsFinite(objective_offset_))
return false;
1305 if (!
IsFinite(objective_scaling_factor_))
return false;
1306 if (objective_scaling_factor_ == 0.0)
return false;
1308 for (ColIndex
col(0);
col < num_cols; ++
col) {
1317 if (!
IsFinite(e.coefficient()))
return false;
1320 if (constraint_upper_bounds_.
size() != constraint_lower_bounds_.
size()) {
1323 for (RowIndex
row(0);
row < constraint_lower_bounds_.
size(); ++
row) {
1332 std::string LinearProgram::ProblemStatFormatter(
1333 const absl::string_view format)
const {
1334 int num_objective_non_zeros = 0;
1335 int num_non_negative_variables = 0;
1336 int num_boxed_variables = 0;
1337 int num_free_variables = 0;
1338 int num_fixed_variables = 0;
1339 int num_other_variables = 0;
1341 for (ColIndex
col(0);
col < num_cols; ++
col) {
1343 ++num_objective_non_zeros;
1348 const bool lower_bounded = (lower_bound != -
kInfinity);
1349 const bool upper_bounded = (upper_bound !=
kInfinity);
1351 if (!lower_bounded && !upper_bounded) {
1352 ++num_free_variables;
1353 }
else if (lower_bound == 0.0 && !upper_bounded) {
1354 ++num_non_negative_variables;
1355 }
else if (!upper_bounded || !lower_bounded) {
1356 ++num_other_variables;
1357 }
else if (lower_bound == upper_bound) {
1358 ++num_fixed_variables;
1360 ++num_boxed_variables;
1364 int num_range_constraints = 0;
1365 int num_less_than_constraints = 0;
1366 int num_greater_than_constraints = 0;
1367 int num_equal_constraints = 0;
1368 int num_rhs_non_zeros = 0;
1370 for (RowIndex
row(0);
row < num_rows; ++
row) {
1373 if (AreBoundsFreeOrBoxed(lower_bound, upper_bound)) {
1376 ++num_range_constraints;
1379 if (lower_bound == upper_bound) {
1380 ++num_equal_constraints;
1381 if (lower_bound != 0) {
1382 ++num_rhs_non_zeros;
1387 ++num_less_than_constraints;
1388 if (upper_bound != 0) {
1389 ++num_rhs_non_zeros;
1394 ++num_greater_than_constraints;
1395 if (lower_bound != 0) {
1396 ++num_rhs_non_zeros;
1400 LOG(DFATAL) <<
"There is a bug since all possible cases for the row bounds "
1401 "should have been accounted for. row="
1408 const int num_continuous_variables =
1410 auto format_runtime =
1411 absl::ParsedFormat<
'd',
'd',
'd',
'd',
'd',
'd',
'd',
'd',
'd',
'd',
'd',
1412 'd',
'd',
'd',
'd',
'd',
'd',
'd'>::New(format);
1413 CHECK(format_runtime);
1414 return absl::StrFormat(
1417 num_objective_non_zeros, num_rhs_non_zeros, num_less_than_constraints,
1418 num_greater_than_constraints, num_equal_constraints,
1419 num_range_constraints, num_non_negative_variables, num_boxed_variables,
1420 num_free_variables, num_fixed_variables, num_other_variables,
1421 num_integer_variables, num_binary_variables, num_non_binary_variables,
1422 num_continuous_variables);
1425 std::string LinearProgram::NonZeroStatFormatter(
1426 const absl::string_view format)
const {
1427 StrictITIVector<RowIndex, EntryIndex> num_entries_in_row(
num_constraints(),
1429 StrictITIVector<ColIndex, EntryIndex> num_entries_in_column(
num_variables(),
1433 for (ColIndex
col(0);
col < num_cols; ++
col) {
1436 num_entries_in_column[
col] = sparse_column.num_entries();
1438 ++num_entries_in_row[e.row()];
1446 const double fill_rate = 100.0 *
static_cast<double>(
num_entries.value()) /
1447 static_cast<double>(height * width);
1449 auto format_runtime =
1450 absl::ParsedFormat<'f', 'd', 'f', 'f', 'd', 'f', 'f'>::New(format);
1451 return absl::StrFormat(
1452 *format_runtime, fill_rate, GetMaxElement(num_entries_in_row).
value(),
1453 Average(num_entries_in_row), StandardDeviation(num_entries_in_row),
1454 GetMaxElement(num_entries_in_column).
value(),
1455 Average(num_entries_in_column), StandardDeviation(num_entries_in_column));
1458 void LinearProgram::ResizeRowsIfNeeded(RowIndex
row) {
1461 transpose_matrix_is_consistent_ =
false;
1470 for (RowIndex constraint(0); constraint <
num_constraints(); ++constraint) {
1471 if (constraint_lower_bounds_[constraint] != 0.0 ||
1472 constraint_upper_bounds_[constraint] != 0.0) {
1476 const ColIndex num_slack_variables =
1489 VLOG(1) <<
"Bounds of variable " <<
col.value() <<
" are non-integer ("
1490 << variable_lower_bounds_[
col] <<
", "
1491 << variable_upper_bounds_[
col] <<
").";
1505 bool integer_constraint =
true;
1508 integer_constraint =
false;
1512 integer_constraint =
false;
1516 if (integer_constraint) {
1523 VLOG(1) <<
"Bounds of constraint " <<
row.value()
1524 <<
" are non-integer (" << constraint_lower_bounds_[
row] <<
", "
1525 << constraint_upper_bounds_[
row] <<
").";
1539 absl::StrAppendFormat(&s,
"\n Var #%d: %s %g",
col.value(),
1543 s +=
"\n------------------------------";
1545 absl::StrAppendFormat(&s,
"\n Constraint #%d: %s %g",
row.value(),
#define DCHECK_LE(val1, val2)
#define DCHECK_NE(val1, val2)
#define CHECK_EQ(val1, val2)
#define DCHECK_GE(val1, val2)
#define CHECK_NE(val1, val2)
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
#define VLOG(verboselevel)
iterator insert(const_iterator pos, const value_type &x)
void push_back(const value_type &x)
void swap(StrongVector &x)
SparseMatrix * GetMutableTransposeSparseMatrix()
std::string GetObjectiveStatsString() const
void SetObjectiveScalingFactor(Fractional objective_scaling_factor)
void PopulateFromPermutedLinearProgram(const LinearProgram &lp, const RowPermutation &row_permutation, const ColumnPermutation &col_permutation)
void SetVariableBounds(ColIndex col, Fractional lower_bound, Fractional upper_bound)
std::string GetVariableName(ColIndex col) const
void SetConstraintName(RowIndex row, absl::string_view name)
const SparseMatrix & GetTransposeSparseMatrix() const
bool SolutionIsWithinVariableBounds(const DenseRow &solution, Fractional absolute_tolerance) const
bool BoundsOfIntegerConstraintsAreInteger(Fractional tolerance) const
bool IsInEquationForm() const
void SetObjectiveOffset(Fractional objective_offset)
void PopulateFromLinearProgram(const LinearProgram &linear_program)
std::string GetPrettyProblemStats() const
bool SolutionIsMIPFeasible(const DenseRow &solution, Fractional absolute_tolerance) const
void SetCoefficient(RowIndex row, ColIndex col, Fractional value)
std::string GetNonZeroStats() const
ColIndex GetFirstSlackVariable() const
bool BoundsOfIntegerVariablesAreInteger(Fractional tolerance) const
void ClearTransposeMatrix()
void SetVariableName(ColIndex col, absl::string_view name)
std::string DumpSolution(const DenseRow &variable_values) const
ColIndex GetSlackVariable(RowIndex row) const
const DenseRow & variable_lower_bounds() const
ColIndex FindOrCreateVariable(const std::string &variable_id)
const DenseColumn & constraint_lower_bounds() const
std::string GetBoundsStatsString() const
Fractional ScaleObjective(GlopParameters::CostScalingAlgorithm method)
const std::vector< ColIndex > & BinaryVariablesList() const
const DenseRow & objective_coefficients() const
Fractional RemoveObjectiveScalingAndOffset(Fractional value) const
const std::vector< ColIndex > & IntegerVariablesList() const
Fractional GetObjectiveCoefficientForMinimizationVersion(ColIndex col) const
void SetConstraintBounds(RowIndex row, Fractional lower_bound, Fractional upper_bound)
ColIndex CreateNewVariable()
ColIndex CreateNewSlackVariable(bool is_integer_slack_variable, Fractional lower_bound, Fractional upper_bound, const std::string &name)
VariableType GetVariableType(ColIndex col) const
RowIndex FindOrCreateConstraint(const std::string &constraint_id)
void Swap(LinearProgram *linear_program)
void AddConstraints(const SparseMatrix &coefficients, const DenseColumn &left_hand_sides, const DenseColumn &right_hand_sides, const StrictITIVector< RowIndex, std::string > &names)
std::string GetPrettyNonZeroStats() const
void SetVariableType(ColIndex col, VariableType type)
Fractional objective_offset() const
const std::vector< ColIndex > & NonBinaryVariablesList() const
bool SolutionIsInteger(const DenseRow &solution, Fractional absolute_tolerance) const
SparseColumn * GetMutableSparseColumn(ColIndex col)
std::string GetConstraintName(RowIndex row) const
void UseTransposeMatrixAsReference()
void AddSlackVariablesWhereNecessary(bool detect_integer_constraints)
const DenseColumn & constraint_upper_bounds() const
void ComputeSlackVariableValues(DenseRow *solution) const
bool SolutionIsLPFeasible(const DenseRow &solution, Fractional absolute_tolerance) const
bool IsVariableInteger(ColIndex col) const
void SetObjectiveCoefficient(ColIndex col, Fractional value)
bool IsVariableBinary(ColIndex col) const
Fractional ApplyObjectiveScalingAndOffset(Fractional value) const
void DeleteRows(const DenseBooleanColumn &rows_to_delete)
void DeleteColumns(const DenseBooleanRow &columns_to_delete)
const DenseRow & variable_upper_bounds() const
std::string GetProblemStats() const
ColIndex num_variables() const
bool UpdateVariableBoundsToIntersection(const DenseRow &variable_lower_bounds, const DenseRow &variable_upper_bounds)
void PopulateFromDual(const LinearProgram &dual, RowToColMapping *duplicated_rows)
void DeleteSlackVariables()
const std::string & name() const
RowIndex CreateNewConstraint()
void PopulateFromLinearProgramVariables(const LinearProgram &linear_program)
std::string GetDimensionString() const
Fractional objective_scaling_factor() const
void SetMaximizationProblem(bool maximize)
void AddConstraintsWithSlackVariables(const SparseMatrix &coefficients, const DenseColumn &left_hand_sides, const DenseColumn &right_hand_sides, const StrictITIVector< RowIndex, std::string > &names, bool detect_integer_constraints_for_slack)
const StrictITIVector< ColIndex, VariableType > variable_types() const
const SparseColumn & GetSparseColumn(ColIndex col) const
EntryIndex num_entries() const
RowIndex num_constraints() const
void PopulateFromInverse(const Permutation &inverse)
RowIndex EntryRow(EntryIndex i) const
SparseColumn * mutable_column(ColIndex col)
void PopulateFromPermutedMatrix(const Matrix &a, const RowPermutation &row_perm, const ColumnPermutation &inverse_col_perm)
void PopulateFromTranspose(const Matrix &input)
ColIndex num_cols() const
void SetNumRows(RowIndex num_rows)
Fractional LookUpValue(RowIndex row, ColIndex col) const
void Swap(SparseMatrix *matrix)
void ComputeMinAndMaxMagnitudes(Fractional *min_magnitude, Fractional *max_magnitude) const
void DeleteRows(RowIndex num_rows, const RowPermutation &permutation)
ColIndex AppendEmptyColumn()
RowIndex num_rows() const
bool AppendRowsFromSparseMatrix(const SparseMatrix &matrix)
void DeleteColumns(const DenseBooleanRow &columns_to_delete)
void PopulateFromSparseMatrix(const SparseMatrix &matrix)
const SparseColumn & column(ColIndex col) const
void PopulateFromZero(RowIndex num_rows, ColIndex num_cols)
EntryIndex num_entries() const
typename Iterator::Entry Entry
void SetCoefficient(Index index, Fractional value)
void PopulateFromSparseVector(const SparseVector &sparse_vector)
EntryIndex num_entries() const
void resize(IntType size)
void assign(IntType size, const T &v)
std::string StringifyMonomial(const Fractional a, const std::string &x, bool fraction)
bool IsRightMostSquareMatrixIdentity(const SparseMatrix &matrix)
bool AreBoundsValid(Fractional lower_bound, Fractional upper_bound)
const RowIndex kInvalidRow(-1)
std::string Stringify(const Fractional x, bool fraction)
Fractional ScalarProduct(const DenseRowOrColumn1 &u, const DenseRowOrColumn2 &v)
StrictITIVector< ColIndex, Fractional > DenseRow
std::string GetProblemStatusString(ProblemStatus problem_status)
Index ColToIntIndex(ColIndex col)
std::string GetConstraintStatusString(ConstraintStatus status)
ColIndex RowToColIndex(RowIndex row)
bool IsFinite(Fractional value)
RowIndex ColToRowIndex(ColIndex col)
void ApplyPermutation(const Permutation< IndexType > &perm, const ITIVectorType &b, ITIVectorType *result)
Fractional PartialScalarProduct(const DenseRowOrColumn &u, const SparseColumn &v, int max_index)
std::string GetVariableStatusString(VariableStatus status)
Index RowToIntIndex(RowIndex row)
const ColIndex kInvalidCol(-1)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
bool IsIntegerWithinTolerance(FloatType x, FloatType tolerance)
std::vector< double > coefficients
std::string DebugString() const
VariableStatusRow variable_statuses
ConstraintStatusColumn constraint_statuses