24 #include "absl/strings/str_cat.h"
29 #include "ortools/glop/parameters.pb.h"
45 using operations_research::MPConstraintProto;
46 using operations_research::MPModelProto;
47 using operations_research::MPVariableProto;
51 void ScaleConstraint(
const std::vector<double>& var_scaling,
52 MPConstraintProto* mp_constraint) {
53 const int num_terms = mp_constraint->coefficient_size();
54 for (
int i = 0; i < num_terms; ++i) {
55 const int var_index = mp_constraint->var_index(i);
56 mp_constraint->set_coefficient(
57 i, mp_constraint->coefficient(i) / var_scaling[var_index]);
61 void ApplyVarScaling(
const std::vector<double> var_scaling,
62 MPModelProto* mp_model) {
63 const int num_variables = mp_model->variable_size();
64 for (
int i = 0; i < num_variables; ++i) {
65 const double scaling = var_scaling[i];
66 const MPVariableProto& mp_var = mp_model->variable(i);
67 const double old_lb = mp_var.lower_bound();
68 const double old_ub = mp_var.upper_bound();
69 const double old_obj = mp_var.objective_coefficient();
70 mp_model->mutable_variable(i)->set_lower_bound(old_lb * scaling);
71 mp_model->mutable_variable(i)->set_upper_bound(old_ub * scaling);
72 mp_model->mutable_variable(i)->set_objective_coefficient(old_obj / scaling);
74 for (MPConstraintProto& mp_constraint : *mp_model->mutable_constraint()) {
75 ScaleConstraint(var_scaling, &mp_constraint);
77 for (MPGeneralConstraintProto& general_constraint :
78 *mp_model->mutable_general_constraint()) {
79 switch (general_constraint.general_constraint_case()) {
80 case MPGeneralConstraintProto::kIndicatorConstraint:
81 ScaleConstraint(var_scaling,
82 general_constraint.mutable_indicator_constraint()
83 ->mutable_constraint());
85 case MPGeneralConstraintProto::kAndConstraint:
86 case MPGeneralConstraintProto::kOrConstraint:
91 LOG(
FATAL) <<
"Scaling unsupported for general constraint of type "
92 << general_constraint.general_constraint_case();
100 MPModelProto* mp_model) {
101 const int num_variables = mp_model->variable_size();
102 std::vector<double> var_scaling(num_variables, 1.0);
103 for (
int i = 0; i < num_variables; ++i) {
104 if (mp_model->variable(i).is_integer())
continue;
105 const double lb = mp_model->variable(i).lower_bound();
106 const double ub = mp_model->variable(i).upper_bound();
107 const double magnitude =
std::max(std::abs(lb), std::abs(ub));
108 if (magnitude == 0 || magnitude > max_bound)
continue;
109 var_scaling[i] =
std::min(scaling, max_bound / magnitude);
111 ApplyVarScaling(var_scaling, mp_model);
119 const double initial_x = x;
125 if (std::abs(q * initial_x - std::round(q * initial_x)) < q * tolerance) {
129 const int new_q = prev_q +
static_cast<int>(std::floor(x)) * q;
143 double GetIntegralityMultiplier(
const MPModelProto& mp_model,
144 const std::vector<double>& var_scaling,
int var,
145 int ct_index,
double tolerance) {
146 DCHECK(!mp_model.variable(
var).is_integer());
147 const MPConstraintProto&
ct = mp_model.constraint(ct_index);
148 double multiplier = 1.0;
149 double var_coeff = 0.0;
150 const double max_multiplier = 1e4;
151 for (
int i = 0; i <
ct.var_index().size(); ++i) {
152 if (
var ==
ct.var_index(i)) {
153 var_coeff =
ct.coefficient(i);
157 DCHECK(mp_model.variable(
ct.var_index(i)).is_integer());
161 multiplier *
ct.coefficient(i) / var_scaling[
ct.var_index(i)];
164 if (multiplier == 0 || multiplier > max_multiplier)
return 0.0;
169 for (
const double bound : {
ct.lower_bound(),
ct.upper_bound()}) {
170 if (!std::isfinite(
bound))
continue;
171 if (std::abs(std::round(
bound * multiplier) -
bound * multiplier) >
172 tolerance * multiplier) {
176 return std::abs(multiplier * var_coeff);
182 const int num_variables = mp_model->variable_size();
187 std::vector<double> max_bounds(num_variables);
188 for (
int i = 0; i < num_variables; ++i) {
189 double value = std::abs(mp_model->variable(i).lower_bound());
192 max_bounds[i] =
value;
200 int64 num_removed = 0;
201 double largest_removed = 0.0;
202 const int num_constraints = mp_model->constraint_size();
203 for (
int c = 0; c < num_constraints; ++c) {
204 MPConstraintProto*
ct = mp_model->mutable_constraint(c);
206 const int size =
ct->var_index().size();
207 if (size == 0)
continue;
208 const double threshold =
209 params.mip_wanted_precision() /
static_cast<double>(size);
210 for (
int i = 0; i < size; ++i) {
211 const int var =
ct->var_index(i);
212 const double coeff =
ct->coefficient(i);
213 if (std::abs(coeff) * max_bounds[
var] < threshold) {
214 largest_removed =
std::max(largest_removed, std::abs(coeff));
217 ct->set_var_index(new_size,
var);
218 ct->set_coefficient(new_size, coeff);
221 num_removed += size - new_size;
222 ct->mutable_var_index()->Truncate(new_size);
223 ct->mutable_coefficient()->Truncate(new_size);
226 const bool log_info =
VLOG_IS_ON(1) || params.log_search_progress();
227 if (log_info && num_removed > 0) {
228 LOG(
INFO) <<
"Removed " << num_removed
229 <<
" near zero terms with largest magnitude of "
230 << largest_removed <<
".";
235 MPModelProto* mp_model) {
236 const int num_variables = mp_model->variable_size();
237 std::vector<double> var_scaling(num_variables, 1.0);
239 int initial_num_integers = 0;
240 for (
int i = 0; i < num_variables; ++i) {
241 if (mp_model->variable(i).is_integer()) ++initial_num_integers;
243 VLOG(1) <<
"Initial num integers: " << initial_num_integers;
246 const double tolerance = 1e-6;
247 std::vector<int> constraint_queue;
249 const int num_constraints = mp_model->constraint_size();
250 std::vector<int> constraint_to_num_non_integer(num_constraints, 0);
251 std::vector<std::vector<int>> var_to_constraints(num_variables);
252 for (
int i = 0; i < num_constraints; ++i) {
253 const MPConstraintProto& mp_constraint = mp_model->constraint(i);
255 for (
const int var : mp_constraint.var_index()) {
256 if (!mp_model->variable(
var).is_integer()) {
257 var_to_constraints[
var].push_back(i);
258 constraint_to_num_non_integer[i]++;
261 if (constraint_to_num_non_integer[i] == 1) {
262 constraint_queue.push_back(i);
265 VLOG(1) <<
"Initial constraint queue: " << constraint_queue.size() <<
" / "
268 int num_detected = 0;
269 double max_scaling = 0.0;
270 auto scale_and_mark_as_integer = [&](
int var,
double scaling)
mutable {
272 CHECK(!mp_model->variable(
var).is_integer());
274 if (scaling != 1.0) {
275 VLOG(2) <<
"Scaled " <<
var <<
" by " << scaling;
279 max_scaling =
std::max(max_scaling, scaling);
283 var_scaling[
var] = scaling;
284 mp_model->mutable_variable(
var)->set_is_integer(
true);
287 for (
const int ct_index : var_to_constraints[
var]) {
288 constraint_to_num_non_integer[ct_index]--;
289 if (constraint_to_num_non_integer[ct_index] == 1) {
290 constraint_queue.push_back(ct_index);
295 int num_fail_due_to_rhs = 0;
296 int num_fail_due_to_large_multiplier = 0;
297 int num_processed_constraints = 0;
298 while (!constraint_queue.empty()) {
299 const int top_ct_index = constraint_queue.back();
300 constraint_queue.pop_back();
304 if (constraint_to_num_non_integer[top_ct_index] == 0)
continue;
307 const MPConstraintProto&
ct = mp_model->constraint(top_ct_index);
308 if (
ct.lower_bound() + tolerance <
ct.upper_bound())
continue;
310 ++num_processed_constraints;
322 double multiplier = 1.0;
323 const double max_multiplier = 1e4;
325 for (
int i = 0; i <
ct.var_index().size(); ++i) {
326 if (!mp_model->variable(
ct.var_index(i)).is_integer()) {
328 var =
ct.var_index(i);
329 var_coeff =
ct.coefficient(i);
334 multiplier *
ct.coefficient(i) / var_scaling[
ct.var_index(i)];
337 if (multiplier == 0 || multiplier > max_multiplier) {
343 if (multiplier == 0 || multiplier > max_multiplier) {
344 ++num_fail_due_to_large_multiplier;
349 const double rhs =
ct.lower_bound();
350 if (std::abs(std::round(rhs * multiplier) - rhs * multiplier) >
351 tolerance * multiplier) {
352 ++num_fail_due_to_rhs;
362 double best_scaling = std::abs(var_coeff * multiplier);
363 for (
const int ct_index : var_to_constraints[
var]) {
364 if (ct_index == top_ct_index)
continue;
365 if (constraint_to_num_non_integer[ct_index] != 1)
continue;
368 const MPConstraintProto&
ct = mp_model->constraint(top_ct_index);
369 if (
ct.lower_bound() + tolerance <
ct.upper_bound())
continue;
371 const double multiplier = GetIntegralityMultiplier(
372 *mp_model, var_scaling,
var, ct_index, tolerance);
373 if (multiplier != 0.0 && multiplier < best_scaling) {
374 best_scaling = multiplier;
378 scale_and_mark_as_integer(
var, best_scaling);
386 int num_in_inequalities = 0;
387 int num_to_be_handled = 0;
388 for (
int var = 0;
var < num_variables; ++
var) {
389 if (mp_model->variable(
var).is_integer())
continue;
392 if (var_to_constraints[
var].empty())
continue;
395 for (
const int ct_index : var_to_constraints[
var]) {
396 if (constraint_to_num_non_integer[ct_index] != 1) {
403 std::vector<double> scaled_coeffs;
404 for (
const int ct_index : var_to_constraints[
var]) {
405 const double multiplier = GetIntegralityMultiplier(
406 *mp_model, var_scaling,
var, ct_index, tolerance);
407 if (multiplier == 0.0) {
411 scaled_coeffs.push_back(multiplier);
420 double scaling = scaled_coeffs[0];
421 for (
const double c : scaled_coeffs) {
425 for (
const double c : scaled_coeffs) {
426 const double fraction = c / scaling;
427 if (std::abs(std::round(fraction) - fraction) > tolerance) {
439 for (
const double bound : {mp_model->variable(
var).lower_bound(),
440 mp_model->variable(
var).upper_bound()}) {
441 if (!std::isfinite(
bound))
continue;
442 if (std::abs(std::round(
bound * scaling) -
bound * scaling) >
443 tolerance * scaling) {
455 ++num_in_inequalities;
456 scale_and_mark_as_integer(
var, scaling);
458 VLOG(1) <<
"num_new_integer: " << num_detected
459 <<
" num_processed_constraints: " << num_processed_constraints
460 <<
" num_rhs_fail: " << num_fail_due_to_rhs
461 <<
" num_multiplier_fail: " << num_fail_due_to_large_multiplier;
463 if (log_info && num_to_be_handled > 0) {
464 LOG(
INFO) <<
"Missed " << num_to_be_handled
465 <<
" potential implied integer.";
468 const int num_integers = initial_num_integers + num_detected;
469 LOG_IF(
INFO, log_info) <<
"Num integers: " << num_integers <<
"/"
470 << num_variables <<
" (implied: " << num_detected
471 <<
" in_inequalities: " << num_in_inequalities
472 <<
" max_scaling: " << max_scaling <<
")"
473 << (num_integers == num_variables ?
" [IP] "
476 ApplyVarScaling(var_scaling, mp_model);
483 struct ConstraintScaler {
485 ConstraintProto* AddConstraint(
const MPModelProto& mp_model,
486 const MPConstraintProto& mp_constraint,
487 CpModelProto* cp_model);
503 double FindFractionalScaling(
const std::vector<double>&
coefficients,
505 double multiplier = 1.0;
509 if (multiplier == 0.0)
break;
516 ConstraintProto* ConstraintScaler::AddConstraint(
517 const MPModelProto& mp_model,
const MPConstraintProto& mp_constraint,
518 CpModelProto* cp_model) {
519 if (mp_constraint.lower_bound() == -
kInfinity &&
520 mp_constraint.upper_bound() ==
kInfinity) {
524 auto* constraint = cp_model->add_constraints();
525 constraint->set_name(mp_constraint.name());
526 auto* arg = constraint->mutable_linear();
534 const int num_coeffs = mp_constraint.coefficient_size();
535 for (
int i = 0; i < num_coeffs; ++i) {
536 const auto& var_proto = cp_model->variables(mp_constraint.var_index(i));
537 const int64 lb = var_proto.domain(0);
538 const int64 ub = var_proto.domain(var_proto.domain_size() - 1);
539 if (lb == 0 && ub == 0)
continue;
541 const double coeff = mp_constraint.coefficient(i);
542 if (coeff == 0.0)
continue;
563 double x =
std::min(scaling_factor, 1.0);
564 double relative_coeff_error;
565 double scaled_sum_error;
566 for (; x <= scaling_factor; x *= 2) {
568 &relative_coeff_error, &scaled_sum_error);
578 const double integer_factor = FindFractionalScaling(
coefficients, 1e-8);
579 if (integer_factor != 0 && integer_factor < scaling_factor) {
581 &relative_coeff_error, &scaled_sum_error);
583 scaling_factor = integer_factor;
594 bool relax_bound = scaled_sum_error > 0;
597 const double scaled_value =
coefficients[i] * scaling_factor;
598 const int64 value =
static_cast<int64>(std::round(scaled_value)) / gcd;
600 if (!mp_model.variable(
var_indices[i]).is_integer()) {
604 arg->add_coeffs(
value);
616 const Fractional scaled_lb = std::ceil(lb * scaling_factor);
620 arg->add_domain(
CeilRatio(IntegerValue(
static_cast<int64>(scaled_lb)),
628 const Fractional scaled_ub = std::floor(ub * scaling_factor);
632 arg->add_domain(
FloorRatio(IntegerValue(
static_cast<int64>(scaled_ub)),
643 const MPModelProto& mp_model,
644 CpModelProto* cp_model) {
645 CHECK(cp_model !=
nullptr);
647 cp_model->set_name(mp_model.name());
661 const int64 kMaxVariableBound =
static_cast<int64>(params.mip_max_bound());
663 int num_truncated_bounds = 0;
664 int num_small_domains = 0;
665 const int64 kSmallDomainSize = 1000;
666 const double kWantedPrecision = params.mip_wanted_precision();
669 const int num_variables = mp_model.variable_size();
670 for (
int i = 0; i < num_variables; ++i) {
671 const MPVariableProto& mp_var = mp_model.variable(i);
672 IntegerVariableProto* cp_var = cp_model->add_variables();
673 cp_var->set_name(mp_var.name());
680 if (mp_var.lower_bound() > kMaxVariableBound) {
682 ++num_truncated_bounds;
683 const int64 value =
static_cast<int64>(std::round(mp_var.lower_bound()));
684 cp_var->add_domain(
value);
685 cp_var->add_domain(
value);
687 }
else if (mp_var.upper_bound() < -kMaxVariableBound) {
689 ++num_truncated_bounds;
690 const int64 value =
static_cast<int64>(std::round(mp_var.upper_bound()));
691 cp_var->add_domain(
value);
692 cp_var->add_domain(
value);
697 for (
const bool lower : {
true,
false}) {
698 const double bound = lower ? mp_var.lower_bound() : mp_var.upper_bound();
699 if (std::abs(
bound) >= kMaxVariableBound) {
700 ++num_truncated_bounds;
701 cp_var->add_domain(
bound < 0 ? -kMaxVariableBound : kMaxVariableBound);
707 static_cast<int64>(lower ? std::ceil(
bound - kWantedPrecision)
708 : std::floor(
bound + kWantedPrecision)));
711 if (cp_var->domain(0) > cp_var->domain(1)) {
712 LOG(
WARNING) <<
"Variable #" << i <<
" cannot take integer value. "
713 << mp_var.ShortDebugString();
719 if (!mp_var.is_integer() && cp_var->domain(0) != cp_var->domain(1) &&
720 cp_var->domain(1) - cp_var->domain(0) < kSmallDomainSize) {
726 << num_truncated_bounds <<
" bounds were truncated to "
727 << kMaxVariableBound <<
".";
729 << num_small_domains <<
" continuous variable domain with fewer than "
730 << kSmallDomainSize <<
" values.";
732 ConstraintScaler scaler;
733 const int64 kScalingTarget =
int64{1} << params.mip_max_activity_exponent();
734 scaler.wanted_precision = kWantedPrecision;
735 scaler.scaling_target = kScalingTarget;
738 for (
const MPConstraintProto& mp_constraint : mp_model.constraint()) {
739 scaler.AddConstraint(mp_model, mp_constraint, cp_model);
741 for (
const MPGeneralConstraintProto& general_constraint :
742 mp_model.general_constraint()) {
743 switch (general_constraint.general_constraint_case()) {
744 case MPGeneralConstraintProto::kIndicatorConstraint: {
745 const auto& indicator_constraint =
746 general_constraint.indicator_constraint();
747 const MPConstraintProto& mp_constraint =
748 indicator_constraint.constraint();
749 ConstraintProto*
ct =
750 scaler.AddConstraint(mp_model, mp_constraint, cp_model);
751 if (
ct ==
nullptr)
continue;
754 const int var = indicator_constraint.var_index();
755 const int value = indicator_constraint.var_value();
759 case MPGeneralConstraintProto::kAndConstraint: {
760 const auto& and_constraint = general_constraint.and_constraint();
761 const std::string&
name = general_constraint.name();
763 ConstraintProto* ct_pos = cp_model->add_constraints();
764 ct_pos->set_name(
name.empty() ?
"" : absl::StrCat(
name,
"_pos"));
765 ct_pos->add_enforcement_literal(and_constraint.resultant_var_index());
766 *ct_pos->mutable_bool_and()->mutable_literals() =
767 and_constraint.var_index();
769 ConstraintProto* ct_neg = cp_model->add_constraints();
770 ct_neg->set_name(
name.empty() ?
"" : absl::StrCat(
name,
"_neg"));
771 ct_neg->add_enforcement_literal(
772 NegatedRef(and_constraint.resultant_var_index()));
773 for (
const int var_index : and_constraint.var_index()) {
774 ct_neg->mutable_bool_or()->add_literals(
NegatedRef(var_index));
778 case MPGeneralConstraintProto::kOrConstraint: {
779 const auto& or_constraint = general_constraint.or_constraint();
780 const std::string&
name = general_constraint.name();
782 ConstraintProto* ct_pos = cp_model->add_constraints();
783 ct_pos->set_name(
name.empty() ?
"" : absl::StrCat(
name,
"_pos"));
784 ct_pos->add_enforcement_literal(or_constraint.resultant_var_index());
785 *ct_pos->mutable_bool_or()->mutable_literals() =
786 or_constraint.var_index();
788 ConstraintProto* ct_neg = cp_model->add_constraints();
789 ct_neg->set_name(
name.empty() ?
"" : absl::StrCat(
name,
"_neg"));
790 ct_neg->add_enforcement_literal(
791 NegatedRef(or_constraint.resultant_var_index()));
792 for (
const int var_index : or_constraint.var_index()) {
793 ct_neg->mutable_bool_and()->add_literals(
NegatedRef(var_index));
798 LOG(
ERROR) <<
"Can't convert general constraints of type "
799 << general_constraint.general_constraint_case()
800 <<
" to CpModelProto.";
806 const bool log_info =
VLOG_IS_ON(1) || params.log_search_progress();
807 LOG_IF(
INFO, log_info) <<
"Maximum constraint coefficient relative error: "
808 << scaler.max_relative_coeff_error;
810 <<
"Maximum constraint worst-case activity relative error: "
811 << scaler.max_relative_rhs_error
812 << (scaler.max_relative_rhs_error > params.mip_check_precision()
813 ?
" [Potentially IMPRECISE]"
815 LOG_IF(
INFO, log_info) <<
"Maximum constraint scaling factor: "
816 << scaler.max_scaling_factor;
823 double min_magnitude = std::numeric_limits<double>::infinity();
824 double max_magnitude = 0.0;
825 double l1_norm = 0.0;
826 for (
int i = 0; i < num_variables; ++i) {
827 const MPVariableProto& mp_var = mp_model.variable(i);
828 if (mp_var.objective_coefficient() == 0.0)
continue;
830 const auto& var_proto = cp_model->variables(i);
831 const int64 lb = var_proto.domain(0);
832 const int64 ub = var_proto.domain(var_proto.domain_size() - 1);
833 if (lb == 0 && ub == 0)
continue;
844 const double average_magnitude =
846 LOG_IF(
INFO, log_info) <<
"Objective magnitude in [" << min_magnitude
847 <<
", " << max_magnitude
848 <<
"] average = " << average_magnitude;
850 if (!
coefficients.empty() || mp_model.objective_offset() != 0.0) {
859 double x =
std::min(scaling_factor, 1.0);
860 double relative_coeff_error;
861 double scaled_sum_error;
862 for (; x <= scaling_factor; x *= 2) {
864 &relative_coeff_error, &scaled_sum_error);
865 if (scaled_sum_error < kWantedPrecision * x)
break;
871 const double integer_factor = FindFractionalScaling(
coefficients, 1e-8);
872 if (integer_factor != 0 && integer_factor < scaling_factor) {
874 &relative_coeff_error, &scaled_sum_error);
875 if (scaled_sum_error < kWantedPrecision * integer_factor) {
876 scaling_factor = integer_factor;
884 <<
"Objective coefficient relative error: " << relative_coeff_error
885 << (relative_coeff_error > params.mip_check_precision() ?
" [IMPRECISE]"
887 LOG_IF(
INFO, log_info) <<
"Objective worst-case absolute error: "
888 << scaled_sum_error / scaling_factor;
889 LOG_IF(
INFO, log_info) <<
"Objective scaling factor: "
890 << scaling_factor / gcd;
895 auto* objective = cp_model->mutable_objective();
896 const int mult = mp_model.maximize() ? -1 : 1;
897 objective->set_offset(mp_model.objective_offset() * scaling_factor / gcd *
899 objective->set_scaling_factor(1.0 / scaling_factor * gcd * mult);
906 objective->add_coeffs(
value * mult);
915 LinearBooleanProblem* problem) {
916 CHECK(problem !=
nullptr);
918 problem->set_name(mp_model.name());
919 const int num_variables = mp_model.variable_size();
920 problem->set_num_variables(num_variables);
924 for (
int var_id(0); var_id < num_variables; ++var_id) {
925 const MPVariableProto& mp_var = mp_model.variable(var_id);
926 problem->add_var_names(mp_var.name());
931 bool is_binary = mp_var.is_integer();
935 if (lb <= -1.0) is_binary =
false;
936 if (ub >= 2.0) is_binary =
false;
939 if (lb <= 0.0 && ub >= 1.0) {
941 }
else if (lb <= 1.0 && ub >= 1.0) {
943 LinearBooleanConstraint* constraint = problem->add_constraints();
944 constraint->set_lower_bound(1);
945 constraint->set_upper_bound(1);
946 constraint->add_literals(var_id + 1);
947 constraint->add_coefficients(1);
948 }
else if (lb <= 0.0 && ub >= 0.0) {
950 LinearBooleanConstraint* constraint = problem->add_constraints();
951 constraint->set_lower_bound(0);
952 constraint->set_upper_bound(0);
953 constraint->add_literals(var_id + 1);
954 constraint->add_coefficients(1);
963 LOG(
WARNING) <<
"The variable #" << var_id <<
" with name "
964 << mp_var.name() <<
" is not binary. "
965 <<
"lb: " << lb <<
" ub: " << ub;
972 double max_relative_error = 0.0;
973 double max_bound_error = 0.0;
975 double relative_error = 0.0;
976 double scaling_factor = 0.0;
980 for (
const MPConstraintProto& mp_constraint : mp_model.constraint()) {
981 LinearBooleanConstraint* constraint = problem->add_constraints();
982 constraint->set_name(mp_constraint.name());
986 const int num_coeffs = mp_constraint.coefficient_size();
987 for (
int i = 0; i < num_coeffs; ++i) {
993 max_relative_error =
std::max(relative_error, max_relative_error);
996 double bound_error = 0.0;
997 for (
int i = 0; i < num_coeffs; ++i) {
998 const double scaled_value = mp_constraint.coefficient(i) * scaling_factor;
999 bound_error += std::abs(round(scaled_value) - scaled_value);
1002 constraint->add_literals(mp_constraint.var_index(i) + 1);
1003 constraint->add_coefficients(
value);
1006 max_bound_error =
std::max(max_bound_error, bound_error);
1013 const Fractional lb = mp_constraint.lower_bound();
1015 if (lb * scaling_factor >
static_cast<double>(kInt64Max)) {
1016 LOG(
WARNING) <<
"A constraint is trivially unsatisfiable.";
1019 if (lb * scaling_factor > -
static_cast<double>(kInt64Max)) {
1021 constraint->set_lower_bound(
1022 static_cast<int64>(round(lb * scaling_factor - bound_error)) / gcd);
1025 const Fractional ub = mp_constraint.upper_bound();
1027 if (ub * scaling_factor < -
static_cast<double>(kInt64Max)) {
1028 LOG(
WARNING) <<
"A constraint is trivially unsatisfiable.";
1031 if (ub * scaling_factor <
static_cast<double>(kInt64Max)) {
1033 constraint->set_upper_bound(
1034 static_cast<int64>(round(ub * scaling_factor + bound_error)) / gcd);
1040 LOG(
INFO) <<
"Maximum constraint relative error: " << max_relative_error;
1041 LOG(
INFO) <<
"Maximum constraint bound error: " << max_bound_error;
1046 for (
int var_id = 0; var_id < num_variables; ++var_id) {
1047 const MPVariableProto& mp_var = mp_model.variable(var_id);
1048 coefficients.push_back(mp_var.objective_coefficient());
1053 max_relative_error =
std::max(relative_error, max_relative_error);
1056 LOG(
INFO) <<
"objective relative error: " << relative_error;
1057 LOG(
INFO) <<
"objective scaling factor: " << scaling_factor / gcd;
1059 LinearObjective* objective = problem->mutable_objective();
1060 objective->set_offset(mp_model.objective_offset() * scaling_factor / gcd);
1064 objective->set_scaling_factor(1.0 / scaling_factor * gcd);
1065 for (
int var_id = 0; var_id < num_variables; ++var_id) {
1066 const MPVariableProto& mp_var = mp_model.variable(var_id);
1068 mp_var.objective_coefficient() * scaling_factor)) /
1071 objective->add_literals(var_id + 1);
1072 objective->add_coefficients(
value);
1080 const double kRelativeTolerance = 1e-8;
1081 if (max_relative_error > kRelativeTolerance) {
1082 LOG(
WARNING) <<
"The relative error during double -> int64 conversion "
1092 for (
int i = 0; i < problem.num_variables(); ++i) {
1099 if (problem.var_names_size() != 0) {
1100 CHECK_EQ(problem.var_names_size(), problem.num_variables());
1101 for (
int i = 0; i < problem.num_variables(); ++i) {
1106 for (
const LinearBooleanConstraint& constraint : problem.constraints()) {
1110 for (
int i = 0; i < constraint.literals_size(); ++i) {
1111 const int literal = constraint.literals(i);
1112 const double coeff = constraint.coefficients(i);
1113 const ColIndex variable_index = ColIndex(abs(
literal) - 1);
1123 constraint.has_lower_bound() ? constraint.lower_bound() - sum
1125 constraint.has_upper_bound() ? constraint.upper_bound() - sum
1132 const LinearObjective& objective = problem.objective();
1133 const double scaling_factor = objective.scaling_factor();
1134 for (
int i = 0; i < objective.literals_size(); ++i) {
1135 const int literal = objective.literals(i);
1136 const double coeff =
1137 static_cast<double>(objective.coefficients(i)) * scaling_factor;
1138 const ColIndex variable_index = ColIndex(abs(
literal) - 1);
1154 int num_fixed_variables = 0;
1156 for (
int i = 0; i < trail.
Index(); ++i) {
1157 const BooleanVariable
var = trail[i].Variable();
1158 const int value = trail[i].IsPositive() ? 1.0 : 0.0;
1160 ++num_fixed_variables;
1164 return num_fixed_variables;
1169 double max_time_in_seconds) {
1171 glop::GlopParameters glop_parameters;
1172 glop_parameters.set_max_time_in_seconds(max_time_in_seconds);
1190 LinearBooleanProblem* problem) {
1196 int num_variable_fixed = 0;
1200 if (
value > 1 - tolerance) {
1201 ++num_variable_fixed;
1202 LinearBooleanConstraint* constraint = problem->add_constraints();
1203 constraint->set_lower_bound(1);
1204 constraint->set_upper_bound(1);
1205 constraint->add_coefficients(1);
1206 constraint->add_literals(
col.value() + 1);
1207 }
else if (
value < tolerance) {
1208 ++num_variable_fixed;
1209 LinearBooleanConstraint* constraint = problem->add_constraints();
1210 constraint->set_lower_bound(0);
1211 constraint->set_upper_bound(0);
1212 constraint->add_coefficients(1);
1213 constraint->add_literals(
col.value() + 1);
1216 LOG(
INFO) <<
"LNS with " << num_variable_fixed <<
" fixed variables.";
#define LOG_IF(severity, condition)
#define DCHECK_NE(val1, val2)
#define CHECK_EQ(val1, val2)
#define CHECK_GT(val1, val2)
#define CHECK_NE(val1, val2)
#define DCHECK(condition)
#define VLOG(verboselevel)
const DenseRow & variable_values() const
ABSL_MUST_USE_RESULT ProblemStatus Solve(const LinearProgram &lp)
void SetParameters(const GlopParameters ¶meters)
void SetVariableBounds(ColIndex col, Fractional lower_bound, Fractional upper_bound)
void SetConstraintName(RowIndex row, absl::string_view name)
void SetObjectiveOffset(Fractional objective_offset)
void SetCoefficient(RowIndex row, ColIndex col, Fractional value)
void SetVariableName(ColIndex col, absl::string_view name)
void SetConstraintBounds(RowIndex row, Fractional lower_bound, Fractional upper_bound)
ColIndex CreateNewVariable()
void SetVariableType(ColIndex col, VariableType type)
void SetObjectiveCoefficient(ColIndex col, Fractional value)
ColIndex num_variables() const
RowIndex CreateNewConstraint()
void SetMaximizationProblem(bool maximize)
const Trail & LiteralTrail() const
void SetAssignmentPreference(Literal literal, double weight)
const AssignmentInfo & Info(BooleanVariable var) const
static const int64 kint64max
static const int64 kint64min
IntegerValue FloorRatio(IntegerValue dividend, IntegerValue positive_divisor)
bool SolveLpAndUseSolutionForSatAssignmentPreference(const glop::LinearProgram &lp, SatSolver *sat_solver, double max_time_in_seconds)
void RemoveNearZeroTerms(const SatParameters ¶ms, MPModelProto *mp_model)
IntegerValue CeilRatio(IntegerValue dividend, IntegerValue positive_divisor)
void ConvertBooleanProblemToLinearProgram(const LinearBooleanProblem &problem, glop::LinearProgram *lp)
std::vector< double > DetectImpliedIntegers(bool log_info, MPModelProto *mp_model)
bool ConvertBinaryMPModelProtoToBooleanProblem(const MPModelProto &mp_model, LinearBooleanProblem *problem)
bool SolveLpAndUseIntegerVariableToStartLNS(const glop::LinearProgram &lp, LinearBooleanProblem *problem)
void ChangeOptimizationDirection(LinearBooleanProblem *problem)
int FixVariablesFromSat(const SatSolver &solver, glop::LinearProgram *lp)
std::vector< double > ScaleContinuousVariables(double scaling, double max_bound, MPModelProto *mp_model)
bool ConvertMPModelProtoToCpModelProto(const SatParameters ¶ms, const MPModelProto &mp_model, CpModelProto *cp_model)
int FindRationalFactor(double x, int limit, double tolerance)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 ComputeGcdOfRoundedDoubles(const std::vector< double > &x, double scaling_factor)
void ComputeScalingErrors(const std::vector< double > &input, const std::vector< double > &lb, const std::vector< double > &ub, double scaling_factor, double *max_relative_coeff_error, double *max_scaled_sum_error)
double GetBestScalingOfDoublesToInt64(const std::vector< double > &input, const std::vector< double > &lb, const std::vector< double > &ub, int64 max_absolute_sum)
double max_scaling_factor
double max_relative_coeff_error
std::vector< double > lower_bounds
std::vector< int > var_indices
std::vector< double > upper_bounds
std::vector< double > coefficients
double max_relative_rhs_error
#define VLOG_IS_ON(verboselevel)