OR-Tools  8.2
sat/lp_utils.cc
Go to the documentation of this file.
1 // Copyright 2010-2018 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 
14 #include "ortools/sat/lp_utils.h"
15 
16 #include <stdlib.h>
17 
18 #include <algorithm>
19 #include <cmath>
20 #include <limits>
21 #include <string>
22 #include <vector>
23 
24 #include "absl/strings/str_cat.h"
25 #include "ortools/base/int_type.h"
27 #include "ortools/base/logging.h"
28 #include "ortools/glop/lp_solver.h"
29 #include "ortools/glop/parameters.pb.h"
33 #include "ortools/sat/integer.h"
34 #include "ortools/sat/sat_base.h"
35 #include "ortools/util/fp_utils.h"
36 
37 namespace operations_research {
38 namespace sat {
39 
40 using glop::ColIndex;
41 using glop::Fractional;
42 using glop::kInfinity;
43 using glop::RowIndex;
44 
45 using operations_research::MPConstraintProto;
46 using operations_research::MPModelProto;
47 using operations_research::MPVariableProto;
48 
49 namespace {
50 
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]);
58  }
59 }
60 
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);
73  }
74  for (MPConstraintProto& mp_constraint : *mp_model->mutable_constraint()) {
75  ScaleConstraint(var_scaling, &mp_constraint);
76  }
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());
84  break;
85  case MPGeneralConstraintProto::kAndConstraint:
86  case MPGeneralConstraintProto::kOrConstraint:
87  // These constraints have only Boolean variables and no constants. They
88  // don't need scaling.
89  break;
90  default:
91  LOG(FATAL) << "Scaling unsupported for general constraint of type "
92  << general_constraint.general_constraint_case();
93  }
94  }
95 }
96 
97 } // namespace
98 
99 std::vector<double> ScaleContinuousVariables(double scaling, double max_bound,
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);
110  }
111  ApplyVarScaling(var_scaling, mp_model);
112  return var_scaling;
113 }
114 
115 // This uses the best rational approximation of x via continuous fractions. It
116 // is probably not the best implementation, but according to the unit test, it
117 // seems to do the job.
118 int FindRationalFactor(double x, int limit, double tolerance) {
119  const double initial_x = x;
120  x = std::abs(x);
121  x -= std::floor(x);
122  int q = 1;
123  int prev_q = 0;
124  while (q < limit) {
125  if (std::abs(q * initial_x - std::round(q * initial_x)) < q * tolerance) {
126  return q;
127  }
128  x = 1 / x;
129  const int new_q = prev_q + static_cast<int>(std::floor(x)) * q;
130  prev_q = q;
131  q = new_q;
132  x -= std::floor(x);
133  }
134  return 0;
135 }
136 
137 namespace {
138 
139 // Returns a factor such that factor * var only need to take integer values to
140 // satisfy the given constraint. Return 0.0 if we didn't find such factor.
141 //
142 // Precondition: var must be the only non-integer in the given constraint.
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);
154  continue;
155  }
156 
157  DCHECK(mp_model.variable(ct.var_index(i)).is_integer());
158  // This actually compute the smallest multiplier to make all other
159  // terms in the constraint integer.
160  const double coeff =
161  multiplier * ct.coefficient(i) / var_scaling[ct.var_index(i)];
162  multiplier *=
163  FindRationalFactor(coeff, /*limit=*/100, multiplier * tolerance);
164  if (multiplier == 0 || multiplier > max_multiplier) return 0.0;
165  }
166  DCHECK_NE(var_coeff, 0.0);
167 
168  // The constraint bound need to be infinite or integer.
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) {
173  return 0.0;
174  }
175  }
176  return std::abs(multiplier * var_coeff);
177 }
178 
179 } // namespace
180 
181 void RemoveNearZeroTerms(const SatParameters& params, MPModelProto* mp_model) {
182  const int num_variables = mp_model->variable_size();
183 
184  // Compute for each variable its current maximum magnitude. Note that we will
185  // only scale variable with a coefficient >= 1, so it is safe to use this
186  // bound.
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());
190  value = std::max(value, std::abs(mp_model->variable(i).upper_bound()));
191  value = std::min(value, params.mip_max_bound());
192  max_bounds[i] = value;
193  }
194 
195  // We want the maximum absolute error while setting coefficients to zero to
196  // not exceed our mip wanted precision. So for a binary variable we might set
197  // to zero coefficient around 1e-7. But for large domain, we need lower coeff
198  // than that, around 1e-12 with the default params.mip_max_bound(). This also
199  // depends on the size of the constraint.
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);
205  int new_size = 0;
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));
215  continue;
216  }
217  ct->set_var_index(new_size, var);
218  ct->set_coefficient(new_size, coeff);
219  ++new_size;
220  }
221  num_removed += size - new_size;
222  ct->mutable_var_index()->Truncate(new_size);
223  ct->mutable_coefficient()->Truncate(new_size);
224  }
225 
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 << ".";
231  }
232 }
233 
234 std::vector<double> DetectImpliedIntegers(bool log_info,
235  MPModelProto* mp_model) {
236  const int num_variables = mp_model->variable_size();
237  std::vector<double> var_scaling(num_variables, 1.0);
238 
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;
242  }
243  VLOG(1) << "Initial num integers: " << initial_num_integers;
244 
245  // We will process all equality constraints with exactly one non-integer.
246  const double tolerance = 1e-6;
247  std::vector<int> constraint_queue;
248 
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);
254 
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]++;
259  }
260  }
261  if (constraint_to_num_non_integer[i] == 1) {
262  constraint_queue.push_back(i);
263  }
264  }
265  VLOG(1) << "Initial constraint queue: " << constraint_queue.size() << " / "
266  << num_constraints;
267 
268  int num_detected = 0;
269  double max_scaling = 0.0;
270  auto scale_and_mark_as_integer = [&](int var, double scaling) mutable {
271  CHECK_NE(var, -1);
272  CHECK(!mp_model->variable(var).is_integer());
273  CHECK_EQ(var_scaling[var], 1.0);
274  if (scaling != 1.0) {
275  VLOG(2) << "Scaled " << var << " by " << scaling;
276  }
277 
278  ++num_detected;
279  max_scaling = std::max(max_scaling, scaling);
280 
281  // Scale the variable right away and mark it as implied integer.
282  // Note that the constraints will be scaled later.
283  var_scaling[var] = scaling;
284  mp_model->mutable_variable(var)->set_is_integer(true);
285 
286  // Update the queue of constraints with a single non-integer.
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);
291  }
292  }
293  };
294 
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();
301 
302  // The non integer variable was already made integer by one other
303  // constraint.
304  if (constraint_to_num_non_integer[top_ct_index] == 0) continue;
305 
306  // Ignore non-equality here.
307  const MPConstraintProto& ct = mp_model->constraint(top_ct_index);
308  if (ct.lower_bound() + tolerance < ct.upper_bound()) continue;
309 
310  ++num_processed_constraints;
311 
312  // This will be set to the unique non-integer term of this constraint.
313  int var = -1;
314  double var_coeff;
315 
316  // We are looking for a "multiplier" so that the unique non-integer term
317  // in this constraint (i.e. var * var_coeff) times this multiplier is an
318  // integer.
319  //
320  // If this is set to zero or becomes too large, we fail to detect a new
321  // implied integer and ignore this constraint.
322  double multiplier = 1.0;
323  const double max_multiplier = 1e4;
324 
325  for (int i = 0; i < ct.var_index().size(); ++i) {
326  if (!mp_model->variable(ct.var_index(i)).is_integer()) {
327  CHECK_EQ(var, -1);
328  var = ct.var_index(i);
329  var_coeff = ct.coefficient(i);
330  } else {
331  // This actually compute the smallest multiplier to make all other
332  // terms in the constraint integer.
333  const double coeff =
334  multiplier * ct.coefficient(i) / var_scaling[ct.var_index(i)];
335  multiplier *=
336  FindRationalFactor(coeff, /*limit=*/100, multiplier * tolerance);
337  if (multiplier == 0 || multiplier > max_multiplier) {
338  break;
339  }
340  }
341  }
342 
343  if (multiplier == 0 || multiplier > max_multiplier) {
344  ++num_fail_due_to_large_multiplier;
345  continue;
346  }
347 
348  // These "rhs" fail could be handled by shifting the variable.
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;
353  continue;
354  }
355 
356  // We want to multiply the variable so that it is integer. We know that
357  // coeff * multiplier is an integer, so we just multiply by that.
358  //
359  // But if a variable appear in more than one equality, we want to find the
360  // smallest integrality factor! See diameterc-msts-v40a100d5i.mps
361  // for an instance of this.
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;
366 
367  // Ignore non-equality here.
368  const MPConstraintProto& ct = mp_model->constraint(top_ct_index);
369  if (ct.lower_bound() + tolerance < ct.upper_bound()) continue;
370 
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;
375  }
376  }
377 
378  scale_and_mark_as_integer(var, best_scaling);
379  }
380 
381  // Process continuous variables that only appear as the unique non integer
382  // in a set of non-equality constraints.
383  //
384  // Note that turning to integer such variable cannot in turn trigger new
385  // integer detection, so there is no point doing that in a loop.
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;
390 
391  // This should be presolved and not happen.
392  if (var_to_constraints[var].empty()) continue;
393 
394  bool ok = true;
395  for (const int ct_index : var_to_constraints[var]) {
396  if (constraint_to_num_non_integer[ct_index] != 1) {
397  ok = false;
398  break;
399  }
400  }
401  if (!ok) continue;
402 
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) {
408  ok = false;
409  break;
410  }
411  scaled_coeffs.push_back(multiplier);
412  }
413  if (!ok) continue;
414 
415  // The situation is a bit tricky here, we have a bunch of coeffs c_i, and we
416  // know that X * c_i can take integer value without changing the constraint
417  // i meaning.
418  //
419  // For now we take the min, and scale only if all c_i / min are integer.
420  double scaling = scaled_coeffs[0];
421  for (const double c : scaled_coeffs) {
422  scaling = std::min(scaling, c);
423  }
424  CHECK_GT(scaling, 0.0);
425  for (const double c : scaled_coeffs) {
426  const double fraction = c / scaling;
427  if (std::abs(std::round(fraction) - fraction) > tolerance) {
428  ok = false;
429  break;
430  }
431  }
432  if (!ok) {
433  // TODO(user): be smarter! we should be able to handle these cases.
434  ++num_to_be_handled;
435  continue;
436  }
437 
438  // Tricky, we also need the bound of the scaled variable to be integer.
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) {
444  ok = false;
445  break;
446  }
447  }
448  if (!ok) {
449  // TODO(user): If we scale more we migth be able to turn it into an
450  // integer.
451  ++num_to_be_handled;
452  continue;
453  }
454 
455  ++num_in_inequalities;
456  scale_and_mark_as_integer(var, scaling);
457  }
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;
462 
463  if (log_info && num_to_be_handled > 0) {
464  LOG(INFO) << "Missed " << num_to_be_handled
465  << " potential implied integer.";
466  }
467 
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] "
474  : " [MIP] ");
475 
476  ApplyVarScaling(var_scaling, mp_model);
477  return var_scaling;
478 }
479 
480 namespace {
481 
482 // We use a class to reuse the temporay memory.
483 struct ConstraintScaler {
484  // Scales an individual constraint.
485  ConstraintProto* AddConstraint(const MPModelProto& mp_model,
486  const MPConstraintProto& mp_constraint,
487  CpModelProto* cp_model);
488 
491  double max_scaling_factor = 0.0;
492 
493  double wanted_precision = 1e-6;
495  std::vector<int> var_indices;
496  std::vector<double> coefficients;
497  std::vector<double> lower_bounds;
498  std::vector<double> upper_bounds;
499 };
500 
501 namespace {
502 
503 double FindFractionalScaling(const std::vector<double>& coefficients,
504  double tolerance) {
505  double multiplier = 1.0;
506  for (const double coeff : coefficients) {
507  multiplier *=
508  FindRationalFactor(coeff, /*limit=*/1e8, multiplier * tolerance);
509  if (multiplier == 0.0) break;
510  }
511  return multiplier;
512 }
513 
514 } // namespace
515 
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) {
521  return nullptr;
522  }
523 
524  auto* constraint = cp_model->add_constraints();
525  constraint->set_name(mp_constraint.name());
526  auto* arg = constraint->mutable_linear();
527 
528  // First scale the coefficients of the constraints so that the constraint
529  // sum can always be computed without integer overflow.
530  var_indices.clear();
531  coefficients.clear();
532  lower_bounds.clear();
533  upper_bounds.clear();
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;
540 
541  const double coeff = mp_constraint.coefficient(i);
542  if (coeff == 0.0) continue;
543 
544  var_indices.push_back(mp_constraint.var_index(i));
545  coefficients.push_back(coeff);
546  lower_bounds.push_back(lb);
547  upper_bounds.push_back(ub);
548  }
549 
550  // We compute the worst case error relative to the magnitude of the bounds.
551  Fractional lb = mp_constraint.lower_bound();
552  Fractional ub = mp_constraint.upper_bound();
553  const double ct_norm = std::max(1.0, std::min(std::abs(lb), std::abs(ub)));
554 
555  double scaling_factor = GetBestScalingOfDoublesToInt64(
557 
558  // Returns the smallest factor of the form 2^i that gives us a relative sum
559  // error of wanted_precision and still make sure we will have no integer
560  // overflow.
561  //
562  // TODO(user): Make this faster.
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);
569  if (scaled_sum_error < wanted_precision * x * ct_norm) break;
570  }
571  scaling_factor = x;
572 
573  // Because we deal with an approximate input, scaling with a power of 2 might
574  // not be the best choice. It is also possible user used rational coeff and
575  // then converted them to double (1/2, 1/3, 4/5, etc...). This scaling will
576  // recover such rational input and might result in a smaller overall
577  // coefficient which is good.
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);
582  if (scaled_sum_error < wanted_precision * integer_factor * ct_norm) {
583  scaling_factor = integer_factor;
584  }
585  }
586 
587  const int64 gcd = ComputeGcdOfRoundedDoubles(coefficients, scaling_factor);
589  std::max(relative_coeff_error, max_relative_coeff_error);
590  max_scaling_factor = std::max(scaling_factor / gcd, max_scaling_factor);
591 
592  // We do not relax the constraint bound if all variables are integer and
593  // we made no error at all during our scaling.
594  bool relax_bound = scaled_sum_error > 0;
595 
596  for (int i = 0; i < coefficients.size(); ++i) {
597  const double scaled_value = coefficients[i] * scaling_factor;
598  const int64 value = static_cast<int64>(std::round(scaled_value)) / gcd;
599  if (value != 0) {
600  if (!mp_model.variable(var_indices[i]).is_integer()) {
601  relax_bound = true;
602  }
603  arg->add_vars(var_indices[i]);
604  arg->add_coeffs(value);
605  }
606  }
608  max_relative_rhs_error, scaled_sum_error / (scaling_factor * ct_norm));
609 
610  // Add the constraint bounds. Because we are sure the scaled constraint fit
611  // on an int64, if the scaled bounds are too large, the constraint is either
612  // always true or always false.
613  if (relax_bound) {
614  lb -= std::max(std::abs(lb), 1.0) * wanted_precision;
615  }
616  const Fractional scaled_lb = std::ceil(lb * scaling_factor);
617  if (lb == -kInfinity || scaled_lb <= kint64min) {
618  arg->add_domain(kint64min);
619  } else {
620  arg->add_domain(CeilRatio(IntegerValue(static_cast<int64>(scaled_lb)),
621  IntegerValue(gcd))
622  .value());
623  }
624 
625  if (relax_bound) {
626  ub += std::max(std::abs(ub), 1.0) * wanted_precision;
627  }
628  const Fractional scaled_ub = std::floor(ub * scaling_factor);
629  if (ub == kInfinity || scaled_ub >= kint64max) {
630  arg->add_domain(kint64max);
631  } else {
632  arg->add_domain(FloorRatio(IntegerValue(static_cast<int64>(scaled_ub)),
633  IntegerValue(gcd))
634  .value());
635  }
636 
637  return constraint;
638 }
639 
640 } // namespace
641 
642 bool ConvertMPModelProtoToCpModelProto(const SatParameters& params,
643  const MPModelProto& mp_model,
644  CpModelProto* cp_model) {
645  CHECK(cp_model != nullptr);
646  cp_model->Clear();
647  cp_model->set_name(mp_model.name());
648 
649  // To make sure we cannot have integer overflow, we use this bound for any
650  // unbounded variable.
651  //
652  // TODO(user): This could be made larger if needed, so be smarter if we have
653  // MIP problem that we cannot "convert" because of this. Note however than we
654  // cannot go that much further because we need to make sure we will not run
655  // into overflow if we add a big linear combination of such variables. It
656  // should always be possible for a user to scale its problem so that all
657  // relevant quantities are a couple of millions. A LP/MIP solver have a
658  // similar condition in disguise because problem with a difference of more
659  // than 6 magnitudes between the variable values will likely run into numeric
660  // trouble.
661  const int64 kMaxVariableBound = static_cast<int64>(params.mip_max_bound());
662 
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();
667 
668  // Add the variables.
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());
674 
675  // Deal with the corner case of a domain far away from zero.
676  //
677  // TODO(user): We should deal with these case by shifting the domain so
678  // that it includes zero instead of just fixing the variable. But that is a
679  // bit of work as it requires some postsolve.
680  if (mp_var.lower_bound() > kMaxVariableBound) {
681  // Fix var to its lower bound.
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);
686  continue;
687  } else if (mp_var.upper_bound() < -kMaxVariableBound) {
688  // Fix var to its upper_bound.
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);
693  continue;
694  }
695 
696  // Note that we must process the lower bound first.
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);
702  continue;
703  }
704 
705  // Note that the cast is "perfect" because we forbid large values.
706  cp_var->add_domain(
707  static_cast<int64>(lower ? std::ceil(bound - kWantedPrecision)
708  : std::floor(bound + kWantedPrecision)));
709  }
710 
711  if (cp_var->domain(0) > cp_var->domain(1)) {
712  LOG(WARNING) << "Variable #" << i << " cannot take integer value. "
713  << mp_var.ShortDebugString();
714  return false;
715  }
716 
717  // Notify if a continuous variable has a small domain as this is likely to
718  // make an all integer solution far from a continuous one.
719  if (!mp_var.is_integer() && cp_var->domain(0) != cp_var->domain(1) &&
720  cp_var->domain(1) - cp_var->domain(0) < kSmallDomainSize) {
721  ++num_small_domains;
722  }
723  }
724 
725  LOG_IF(WARNING, num_truncated_bounds > 0)
726  << num_truncated_bounds << " bounds were truncated to "
727  << kMaxVariableBound << ".";
728  LOG_IF(WARNING, num_small_domains > 0)
729  << num_small_domains << " continuous variable domain with fewer than "
730  << kSmallDomainSize << " values.";
731 
732  ConstraintScaler scaler;
733  const int64 kScalingTarget = int64{1} << params.mip_max_activity_exponent();
734  scaler.wanted_precision = kWantedPrecision;
735  scaler.scaling_target = kScalingTarget;
736 
737  // Add the constraints. We scale each of them individually.
738  for (const MPConstraintProto& mp_constraint : mp_model.constraint()) {
739  scaler.AddConstraint(mp_model, mp_constraint, cp_model);
740  }
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;
752 
753  // Add the indicator.
754  const int var = indicator_constraint.var_index();
755  const int value = indicator_constraint.var_value();
756  ct->add_enforcement_literal(value == 1 ? var : NegatedRef(var));
757  break;
758  }
759  case MPGeneralConstraintProto::kAndConstraint: {
760  const auto& and_constraint = general_constraint.and_constraint();
761  const std::string& name = general_constraint.name();
762 
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();
768 
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));
775  }
776  break;
777  }
778  case MPGeneralConstraintProto::kOrConstraint: {
779  const auto& or_constraint = general_constraint.or_constraint();
780  const std::string& name = general_constraint.name();
781 
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();
787 
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));
794  }
795  break;
796  }
797  default:
798  LOG(ERROR) << "Can't convert general constraints of type "
799  << general_constraint.general_constraint_case()
800  << " to CpModelProto.";
801  return false;
802  }
803  }
804 
805  // Display the error/scaling on the constraints.
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;
809  LOG_IF(INFO, log_info)
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]"
814  : "");
815  LOG_IF(INFO, log_info) << "Maximum constraint scaling factor: "
816  << scaler.max_scaling_factor;
817 
818  // Add the objective.
819  std::vector<int> var_indices;
820  std::vector<double> coefficients;
821  std::vector<double> lower_bounds;
822  std::vector<double> upper_bounds;
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;
829 
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;
834 
835  var_indices.push_back(i);
836  coefficients.push_back(mp_var.objective_coefficient());
837  lower_bounds.push_back(lb);
838  upper_bounds.push_back(ub);
839  min_magnitude = std::min(min_magnitude, std::abs(coefficients.back()));
840  max_magnitude = std::max(max_magnitude, std::abs(coefficients.back()));
841  l1_norm += std::abs(coefficients.back());
842  }
843  if (!coefficients.empty()) {
844  const double average_magnitude =
845  l1_norm / static_cast<double>(coefficients.size());
846  LOG_IF(INFO, log_info) << "Objective magnitude in [" << min_magnitude
847  << ", " << max_magnitude
848  << "] average = " << average_magnitude;
849  }
850  if (!coefficients.empty() || mp_model.objective_offset() != 0.0) {
851  double scaling_factor = GetBestScalingOfDoublesToInt64(
852  coefficients, lower_bounds, upper_bounds, kScalingTarget);
853 
854  // Returns the smallest factor of the form 2^i that gives us an absolute
855  // error of kWantedPrecision and still make sure we will have no integer
856  // overflow.
857  //
858  // TODO(user): Make this faster.
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;
866  }
867  scaling_factor = x;
868 
869  // Same remark as for the constraint.
870  // TODO(user): Extract common code.
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;
877  }
878  }
879 
880  const int64 gcd = ComputeGcdOfRoundedDoubles(coefficients, scaling_factor);
881 
882  // Display the objective error/scaling.
883  LOG_IF(INFO, log_info)
884  << "Objective coefficient relative error: " << relative_coeff_error
885  << (relative_coeff_error > params.mip_check_precision() ? " [IMPRECISE]"
886  : "");
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;
891 
892  // Note that here we set the scaling factor for the inverse operation of
893  // getting the "true" objective value from the scaled one. Hence the
894  // inverse.
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 *
898  mult);
899  objective->set_scaling_factor(1.0 / scaling_factor * gcd * mult);
900  for (int i = 0; i < coefficients.size(); ++i) {
901  const int64 value =
902  static_cast<int64>(std::round(coefficients[i] * scaling_factor)) /
903  gcd;
904  if (value != 0) {
905  objective->add_vars(var_indices[i]);
906  objective->add_coeffs(value * mult);
907  }
908  }
909  }
910 
911  return true;
912 }
913 
914 bool ConvertBinaryMPModelProtoToBooleanProblem(const MPModelProto& mp_model,
915  LinearBooleanProblem* problem) {
916  CHECK(problem != nullptr);
917  problem->Clear();
918  problem->set_name(mp_model.name());
919  const int num_variables = mp_model.variable_size();
920  problem->set_num_variables(num_variables);
921 
922  // Test if the variables are binary variables.
923  // Add constraints for the fixed 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());
927 
928  // This will be changed to false as soon as we detect the variable to be
929  // non-binary. This is done this way so we can display a nice error message
930  // before aborting the function and returning false.
931  bool is_binary = mp_var.is_integer();
932 
933  const Fractional lb = mp_var.lower_bound();
934  const Fractional ub = mp_var.upper_bound();
935  if (lb <= -1.0) is_binary = false;
936  if (ub >= 2.0) is_binary = false;
937  if (is_binary) {
938  // 4 cases.
939  if (lb <= 0.0 && ub >= 1.0) {
940  // Binary variable. Ok.
941  } else if (lb <= 1.0 && ub >= 1.0) {
942  // Fixed variable at 1.
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) {
949  // Fixed variable at 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);
955  } else {
956  // No possible integer value!
957  is_binary = false;
958  }
959  }
960 
961  // Abort if the variable is not binary.
962  if (!is_binary) {
963  LOG(WARNING) << "The variable #" << var_id << " with name "
964  << mp_var.name() << " is not binary. "
965  << "lb: " << lb << " ub: " << ub;
966  return false;
967  }
968  }
969 
970  // Variables needed to scale the double coefficients into int64.
971  const int64 kInt64Max = std::numeric_limits<int64>::max();
972  double max_relative_error = 0.0;
973  double max_bound_error = 0.0;
974  double max_scaling_factor = 0.0;
975  double relative_error = 0.0;
976  double scaling_factor = 0.0;
977  std::vector<double> coefficients;
978 
979  // Add all constraints.
980  for (const MPConstraintProto& mp_constraint : mp_model.constraint()) {
981  LinearBooleanConstraint* constraint = problem->add_constraints();
982  constraint->set_name(mp_constraint.name());
983 
984  // First scale the coefficients of the constraints.
985  coefficients.clear();
986  const int num_coeffs = mp_constraint.coefficient_size();
987  for (int i = 0; i < num_coeffs; ++i) {
988  coefficients.push_back(mp_constraint.coefficient(i));
989  }
990  GetBestScalingOfDoublesToInt64(coefficients, kInt64Max, &scaling_factor,
991  &relative_error);
992  const int64 gcd = ComputeGcdOfRoundedDoubles(coefficients, scaling_factor);
993  max_relative_error = std::max(relative_error, max_relative_error);
994  max_scaling_factor = std::max(scaling_factor / gcd, max_scaling_factor);
995 
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);
1000  const int64 value = static_cast<int64>(round(scaled_value)) / gcd;
1001  if (value != 0) {
1002  constraint->add_literals(mp_constraint.var_index(i) + 1);
1003  constraint->add_coefficients(value);
1004  }
1005  }
1006  max_bound_error = std::max(max_bound_error, bound_error);
1007 
1008  // Add the bounds. Note that we do not pass them to
1009  // GetBestScalingOfDoublesToInt64() because we know that the sum of absolute
1010  // coefficients of the constraint fit on an int64. If one of the scaled
1011  // bound overflows, we don't care by how much because in this case the
1012  // constraint is just trivial or unsatisfiable.
1013  const Fractional lb = mp_constraint.lower_bound();
1014  if (lb != -kInfinity) {
1015  if (lb * scaling_factor > static_cast<double>(kInt64Max)) {
1016  LOG(WARNING) << "A constraint is trivially unsatisfiable.";
1017  return false;
1018  }
1019  if (lb * scaling_factor > -static_cast<double>(kInt64Max)) {
1020  // Otherwise, the constraint is not needed.
1021  constraint->set_lower_bound(
1022  static_cast<int64>(round(lb * scaling_factor - bound_error)) / gcd);
1023  }
1024  }
1025  const Fractional ub = mp_constraint.upper_bound();
1026  if (ub != kInfinity) {
1027  if (ub * scaling_factor < -static_cast<double>(kInt64Max)) {
1028  LOG(WARNING) << "A constraint is trivially unsatisfiable.";
1029  return false;
1030  }
1031  if (ub * scaling_factor < static_cast<double>(kInt64Max)) {
1032  // Otherwise, the constraint is not needed.
1033  constraint->set_upper_bound(
1034  static_cast<int64>(round(ub * scaling_factor + bound_error)) / gcd);
1035  }
1036  }
1037  }
1038 
1039  // Display the error/scaling without taking into account the objective first.
1040  LOG(INFO) << "Maximum constraint relative error: " << max_relative_error;
1041  LOG(INFO) << "Maximum constraint bound error: " << max_bound_error;
1042  LOG(INFO) << "Maximum constraint scaling factor: " << max_scaling_factor;
1043 
1044  // Add the objective.
1045  coefficients.clear();
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());
1049  }
1050  GetBestScalingOfDoublesToInt64(coefficients, kInt64Max, &scaling_factor,
1051  &relative_error);
1052  const int64 gcd = ComputeGcdOfRoundedDoubles(coefficients, scaling_factor);
1053  max_relative_error = std::max(relative_error, max_relative_error);
1054 
1055  // Display the objective error/scaling.
1056  LOG(INFO) << "objective relative error: " << relative_error;
1057  LOG(INFO) << "objective scaling factor: " << scaling_factor / gcd;
1058 
1059  LinearObjective* objective = problem->mutable_objective();
1060  objective->set_offset(mp_model.objective_offset() * scaling_factor / gcd);
1061 
1062  // Note that here we set the scaling factor for the inverse operation of
1063  // getting the "true" objective value from the scaled one. Hence the inverse.
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);
1067  const int64 value = static_cast<int64>(round(
1068  mp_var.objective_coefficient() * scaling_factor)) /
1069  gcd;
1070  if (value != 0) {
1071  objective->add_literals(var_id + 1);
1072  objective->add_coefficients(value);
1073  }
1074  }
1075 
1076  // If the problem was a maximization one, we need to modify the objective.
1077  if (mp_model.maximize()) ChangeOptimizationDirection(problem);
1078 
1079  // Test the precision of the conversion.
1080  const double kRelativeTolerance = 1e-8;
1081  if (max_relative_error > kRelativeTolerance) {
1082  LOG(WARNING) << "The relative error during double -> int64 conversion "
1083  << "is too high!";
1084  return false;
1085  }
1086  return true;
1087 }
1088 
1089 void ConvertBooleanProblemToLinearProgram(const LinearBooleanProblem& problem,
1090  glop::LinearProgram* lp) {
1091  lp->Clear();
1092  for (int i = 0; i < problem.num_variables(); ++i) {
1093  const ColIndex col = lp->CreateNewVariable();
1095  lp->SetVariableBounds(col, 0.0, 1.0);
1096  }
1097 
1098  // Variables name are optional.
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) {
1102  lp->SetVariableName(ColIndex(i), problem.var_names(i));
1103  }
1104  }
1105 
1106  for (const LinearBooleanConstraint& constraint : problem.constraints()) {
1107  const RowIndex constraint_index = lp->CreateNewConstraint();
1108  lp->SetConstraintName(constraint_index, constraint.name());
1109  double sum = 0.0;
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);
1114  if (literal < 0) {
1115  sum += coeff;
1116  lp->SetCoefficient(constraint_index, variable_index, -coeff);
1117  } else {
1118  lp->SetCoefficient(constraint_index, variable_index, coeff);
1119  }
1120  }
1121  lp->SetConstraintBounds(
1122  constraint_index,
1123  constraint.has_lower_bound() ? constraint.lower_bound() - sum
1124  : -kInfinity,
1125  constraint.has_upper_bound() ? constraint.upper_bound() - sum
1126  : kInfinity);
1127  }
1128 
1129  // Objective.
1130  {
1131  double sum = 0.0;
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);
1139  if (literal < 0) {
1140  sum += coeff;
1141  lp->SetObjectiveCoefficient(variable_index, -coeff);
1142  } else {
1143  lp->SetObjectiveCoefficient(variable_index, coeff);
1144  }
1145  }
1146  lp->SetObjectiveOffset((sum + objective.offset()) * scaling_factor);
1147  lp->SetMaximizationProblem(scaling_factor < 0);
1148  }
1149 
1150  lp->CleanUp();
1151 }
1152 
1154  int num_fixed_variables = 0;
1155  const Trail& trail = solver.LiteralTrail();
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;
1159  if (trail.Info(var).level == 0) {
1160  ++num_fixed_variables;
1161  lp->SetVariableBounds(ColIndex(var.value()), value, value);
1162  }
1163  }
1164  return num_fixed_variables;
1165 }
1166 
1168  const glop::LinearProgram& lp, SatSolver* sat_solver,
1169  double max_time_in_seconds) {
1170  glop::LPSolver solver;
1171  glop::GlopParameters glop_parameters;
1172  glop_parameters.set_max_time_in_seconds(max_time_in_seconds);
1173  solver.SetParameters(glop_parameters);
1174  const glop::ProblemStatus& status = solver.Solve(lp);
1175  if (status != glop::ProblemStatus::OPTIMAL &&
1176  status != glop::ProblemStatus::IMPRECISE &&
1178  return false;
1179  }
1180  for (ColIndex col(0); col < lp.num_variables(); ++col) {
1181  const Fractional& value = solver.variable_values()[col];
1182  sat_solver->SetAssignmentPreference(
1183  Literal(BooleanVariable(col.value()), round(value) == 1),
1184  1 - std::abs(value - round(value)));
1185  }
1186  return true;
1187 }
1188 
1190  LinearBooleanProblem* problem) {
1191  glop::LPSolver solver;
1192  const glop::ProblemStatus& status = solver.Solve(lp);
1193  if (status != glop::ProblemStatus::OPTIMAL &&
1195  return false;
1196  int num_variable_fixed = 0;
1197  for (ColIndex col(0); col < lp.num_variables(); ++col) {
1198  const Fractional tolerance = 1e-5;
1199  const Fractional& value = solver.variable_values()[col];
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);
1214  }
1215  }
1216  LOG(INFO) << "LNS with " << num_variable_fixed << " fixed variables.";
1217  return true;
1218 }
1219 
1220 } // namespace sat
1221 } // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define LOG_IF(severity, condition)
Definition: base/logging.h:479
#define CHECK(condition)
Definition: base/logging.h:495
#define DCHECK_NE(val1, val2)
Definition: base/logging.h:886
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define CHECK_GT(val1, val2)
Definition: base/logging.h:702
#define CHECK_NE(val1, val2)
Definition: base/logging.h:698
#define LOG(severity)
Definition: base/logging.h:420
#define DCHECK(condition)
Definition: base/logging.h:884
#define VLOG(verboselevel)
Definition: base/logging.h:978
const DenseRow & variable_values() const
Definition: lp_solver.h:100
ABSL_MUST_USE_RESULT ProblemStatus Solve(const LinearProgram &lp)
Definition: lp_solver.cc:121
void SetParameters(const GlopParameters &parameters)
Definition: lp_solver.cc:113
void SetVariableBounds(ColIndex col, Fractional lower_bound, Fractional upper_bound)
Definition: lp_data.cc:248
void SetConstraintName(RowIndex row, absl::string_view name)
Definition: lp_data.cc:244
void SetObjectiveOffset(Fractional objective_offset)
Definition: lp_data.cc:330
void SetCoefficient(RowIndex row, ColIndex col, Fractional value)
Definition: lp_data.cc:316
void SetVariableName(ColIndex col, absl::string_view name)
Definition: lp_data.cc:231
void SetConstraintBounds(RowIndex row, Fractional lower_bound, Fractional upper_bound)
Definition: lp_data.cc:308
void SetVariableType(ColIndex col, VariableType type)
Definition: lp_data.cc:235
void SetObjectiveCoefficient(ColIndex col, Fractional value)
Definition: lp_data.cc:325
void SetMaximizationProblem(bool maximize)
Definition: lp_data.cc:342
const Trail & LiteralTrail() const
Definition: sat_solver.h:361
void SetAssignmentPreference(Literal literal, double weight)
Definition: sat_solver.h:150
const AssignmentInfo & Info(BooleanVariable var) const
Definition: sat_base.h:381
const std::string name
const Constraint * ct
int64 value
IntVar * var
Definition: expr_array.cc:1858
static const int64 kint64max
int64_t int64
static const int64 kint64min
const int WARNING
Definition: log_severity.h:31
const int INFO
Definition: log_severity.h:31
const int ERROR
Definition: log_severity.h:32
const int FATAL
Definition: log_severity.h:32
ColIndex col
Definition: markowitz.cc:176
const double kInfinity
Definition: lp_types.h:83
IntegerValue FloorRatio(IntegerValue dividend, IntegerValue positive_divisor)
Definition: integer.h:90
bool SolveLpAndUseSolutionForSatAssignmentPreference(const glop::LinearProgram &lp, SatSolver *sat_solver, double max_time_in_seconds)
void RemoveNearZeroTerms(const SatParameters &params, MPModelProto *mp_model)
IntegerValue CeilRatio(IntegerValue dividend, IntegerValue positive_divisor)
Definition: integer.h:81
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)
Definition: sat/lp_utils.cc:99
bool ConvertMPModelProtoToCpModelProto(const SatParameters &params, 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)
Definition: fp_utils.cc:189
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)
Definition: fp_utils.cc:159
double GetBestScalingOfDoublesToInt64(const std::vector< double > &input, const std::vector< double > &lb, const std::vector< double > &ub, int64 max_absolute_sum)
Definition: fp_utils.cc:168
Literal literal
Definition: optimization.cc:84
int64 bound
double max_scaling_factor
double max_relative_coeff_error
std::vector< double > lower_bounds
double wanted_precision
int64 scaling_target
std::vector< int > var_indices
std::vector< double > upper_bounds
std::vector< double > coefficients
double max_relative_rhs_error
#define VLOG_IS_ON(verboselevel)
Definition: vlog_is_on.h:41