OR-Tools  8.2
integral_solver.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 
15 
16 #include <math.h>
17 
18 #include <cstdint>
19 #include <limits>
20 #include <vector>
21 
22 #include "ortools/bop/bop_solver.h"
24 
25 namespace operations_research {
26 namespace bop {
27 
28 using ::operations_research::glop::ColIndex;
32 using ::operations_research::glop::LinearProgram;
33 using ::operations_research::glop::LPDecomposer;
34 using ::operations_research::glop::RowIndex;
35 using ::operations_research::glop::SparseColumn;
36 using ::operations_research::glop::SparseMatrix;
37 using ::operations_research::sat::LinearBooleanConstraint;
38 using ::operations_research::sat::LinearBooleanProblem;
39 using ::operations_research::sat::LinearObjective;
40 
41 namespace {
42 // TODO(user): Use an existing one or move it to util.
44  const double kTolerance = 1e-10;
45  return std::abs(x - round(x)) <= kTolerance;
46 }
47 
48 // Returns true when all the variables of the problem are Boolean, and all the
49 // constraints have integer coefficients.
50 // TODO(user): Move to SAT util.
51 bool ProblemIsBooleanAndHasOnlyIntegralConstraints(
52  const LinearProgram& linear_problem) {
53  const glop::SparseMatrix& matrix = linear_problem.GetSparseMatrix();
54 
55  for (ColIndex col(0); col < linear_problem.num_variables(); ++col) {
56  const Fractional lower_bound = linear_problem.variable_lower_bounds()[col];
57  const Fractional upper_bound = linear_problem.variable_upper_bounds()[col];
58 
59  if (lower_bound <= -1.0 || upper_bound >= 2.0) {
60  // Integral variable.
61  return false;
62  }
63 
64  for (const SparseColumn::Entry e : matrix.column(col)) {
65  if (!IsIntegerWithinTolerance(e.coefficient())) {
66  // Floating coefficient.
67  return false;
68  }
69  }
70  }
71  return true;
72 }
73 
74 // Builds a LinearBooleanProblem based on a LinearProgram with all the variables
75 // being booleans and all the constraints having only integral coefficients.
76 // TODO(user): Move to SAT util.
77 void BuildBooleanProblemWithIntegralConstraints(
78  const LinearProgram& linear_problem, const DenseRow& initial_solution,
79  LinearBooleanProblem* boolean_problem,
80  std::vector<bool>* boolean_initial_solution) {
81  CHECK(boolean_problem != nullptr);
82  boolean_problem->Clear();
83 
84  const glop::SparseMatrix& matrix = linear_problem.GetSparseMatrix();
85  // Create Boolean variables.
86  for (ColIndex col(0); col < matrix.num_cols(); ++col) {
87  boolean_problem->add_var_names(linear_problem.GetVariableName(col));
88  }
89  boolean_problem->set_num_variables(matrix.num_cols().value());
90  boolean_problem->set_name(linear_problem.name());
91 
92  // Create constraints.
93  for (RowIndex row(0); row < matrix.num_rows(); ++row) {
94  LinearBooleanConstraint* const constraint =
95  boolean_problem->add_constraints();
96  constraint->set_name(linear_problem.GetConstraintName(row));
97  if (linear_problem.constraint_lower_bounds()[row] != -kInfinity) {
98  constraint->set_lower_bound(
99  linear_problem.constraint_lower_bounds()[row]);
100  }
101  if (linear_problem.constraint_upper_bounds()[row] != kInfinity) {
102  constraint->set_upper_bound(
103  linear_problem.constraint_upper_bounds()[row]);
104  }
105  }
106 
107  // Store the constraint coefficients.
108  for (ColIndex col(0); col < matrix.num_cols(); ++col) {
109  for (const SparseColumn::Entry e : matrix.column(col)) {
110  LinearBooleanConstraint* const constraint =
111  boolean_problem->mutable_constraints(e.row().value());
112  constraint->add_literals(col.value() + 1);
113  constraint->add_coefficients(e.coefficient());
114  }
115  }
116 
117  // Add the unit constraints to fix the variables since the variable bounds
118  // are always [0, 1] in a BooleanLinearProblem.
119  for (ColIndex col(0); col < matrix.num_cols(); ++col) {
120  // TODO(user): double check the rounding, and add unit test for this.
121  const int lb = std::round(linear_problem.variable_lower_bounds()[col]);
122  const int ub = std::round(linear_problem.variable_upper_bounds()[col]);
123  if (lb == ub) {
124  LinearBooleanConstraint* ct = boolean_problem->add_constraints();
125  ct->set_lower_bound(ub);
126  ct->set_upper_bound(ub);
127  ct->add_literals(col.value() + 1);
128  ct->add_coefficients(1.0);
129  }
130  }
131 
132  // Create the minimization objective.
133  std::vector<double> coefficients;
134  for (ColIndex col(0); col < linear_problem.num_variables(); ++col) {
135  const Fractional coeff = linear_problem.objective_coefficients()[col];
136  if (coeff != 0.0) coefficients.push_back(coeff);
137  }
138  double scaling_factor = 0.0;
139  double relative_error = 0.0;
142  &scaling_factor, &relative_error);
143  const int64_t gcd = ComputeGcdOfRoundedDoubles(coefficients, scaling_factor);
144  LinearObjective* const objective = boolean_problem->mutable_objective();
145  objective->set_offset(linear_problem.objective_offset() * scaling_factor /
146  gcd);
147 
148  // Note that here we set the scaling factor for the inverse operation of
149  // getting the "true" objective value from the scaled one. Hence the inverse.
150  objective->set_scaling_factor(1.0 / scaling_factor * gcd);
151  for (ColIndex col(0); col < linear_problem.num_variables(); ++col) {
152  const Fractional coeff = linear_problem.objective_coefficients()[col];
153  const int64_t value =
154  static_cast<int64_t>(round(coeff * scaling_factor)) / gcd;
155  if (value != 0) {
156  objective->add_literals(col.value() + 1);
157  objective->add_coefficients(value);
158  }
159  }
160 
161  // If the problem was a maximization one, we need to modify the objective.
162  if (linear_problem.IsMaximizationProblem()) {
163  sat::ChangeOptimizationDirection(boolean_problem);
164  }
165 
166  // Fill the Boolean initial solution.
167  if (!initial_solution.empty()) {
168  CHECK(boolean_initial_solution != nullptr);
169  CHECK_EQ(boolean_problem->num_variables(), initial_solution.size());
170  boolean_initial_solution->assign(boolean_problem->num_variables(), false);
171  for (int i = 0; i < initial_solution.size(); ++i) {
172  (*boolean_initial_solution)[i] = (initial_solution[ColIndex(i)] != 0);
173  }
174  }
175 }
176 
177 //------------------------------------------------------------------------------
178 // IntegralVariable
179 //------------------------------------------------------------------------------
180 // Model an integral variable using Boolean variables.
181 // TODO(user): Enable discrete representation by value, i.e. use three Boolean
182 // variables when only possible values are 10, 12, 32.
183 // In the same way, when only two consecutive values are possible
184 // use only one Boolean variable with an offset.
185 class IntegralVariable {
186  public:
187  IntegralVariable();
188 
189  // Creates the minimal number of Boolean variables to represent an integral
190  // variable with range [lower_bound, upper_bound]. start_var_index corresponds
191  // to the next available Boolean variable index. If three Boolean variables
192  // are needed to model the integral variable, the used variables will have
193  // indices start_var_index, start_var_index +1, and start_var_index +2.
194  void BuildFromRange(int start_var_index, Fractional lower_bound,
195  Fractional upper_bound);
196 
197  void Clear();
198  void set_offset(int64_t offset) { offset_ = offset; }
199  void set_weight(VariableIndex var, int64_t weight);
200 
201  int GetNumberOfBooleanVariables() const { return bits_.size(); }
202 
203  const std::vector<VariableIndex>& bits() const { return bits_; }
204  const std::vector<int64_t>& weights() const { return weights_; }
205  int64_t offset() const { return offset_; }
206 
207  // Returns the value of the integral variable based on the Boolean conversion
208  // and the Boolean solution to the problem.
209  int64_t GetSolutionValue(const BopSolution& solution) const;
210 
211  // Returns the values of the Boolean variables based on the Boolean conversion
212  // and the integral value of this variable. This only works for variables that
213  // were constructed using BuildFromRange() (for which can_be_reversed_ is
214  // true).
215  std::vector<bool> GetBooleanSolutionValues(int64_t integral_value) const;
216 
217  std::string DebugString() const;
218 
219  private:
220  // The value of the integral variable is expressed as
221  // sum_i(weights[i] * Value(bits[i])) + offset.
222  // Note that weights can be negative to represent negative values.
223  std::vector<VariableIndex> bits_;
224  std::vector<int64_t> weights_;
225  int64_t offset_;
226  // True if the values of the boolean variables representing this integral
227  // variable can be deduced from the integral variable's value. Namely, this is
228  // true for variables built using BuildFromRange() but usually false for
229  // variables built using set_weight().
230  bool can_be_reversed_;
231 };
232 
233 IntegralVariable::IntegralVariable()
234  : bits_(), weights_(), offset_(0), can_be_reversed_(true) {}
235 
236 void IntegralVariable::BuildFromRange(int start_var_index,
237  Fractional lower_bound,
238  Fractional upper_bound) {
239  Clear();
240 
241  // Integral variable. Split the variable into the minimum number of bits
242  // required to model the upper bound.
243  CHECK_NE(-kInfinity, lower_bound);
244  CHECK_NE(kInfinity, upper_bound);
245 
246  const int64_t integral_lower_bound = static_cast<int64_t>(ceil(lower_bound));
247  const int64_t integral_upper_bound = static_cast<int64_t>(floor(upper_bound));
248  offset_ = integral_lower_bound;
249  const int64_t delta = integral_upper_bound - integral_lower_bound;
250  const int num_used_bits = MostSignificantBitPosition64(delta) + 1;
251  for (int i = 0; i < num_used_bits; ++i) {
252  bits_.push_back(VariableIndex(start_var_index + i));
253  weights_.push_back(1ULL << i);
254  }
255 }
256 
257 void IntegralVariable::Clear() {
258  bits_.clear();
259  weights_.clear();
260  offset_ = 0;
261  can_be_reversed_ = true;
262 }
263 
264 void IntegralVariable::set_weight(VariableIndex var, int64_t weight) {
265  bits_.push_back(var);
266  weights_.push_back(weight);
267  can_be_reversed_ = false;
268 }
269 
270 int64_t IntegralVariable::GetSolutionValue(const BopSolution& solution) const {
271  int64_t value = offset_;
272  for (int i = 0; i < bits_.size(); ++i) {
273  value += weights_[i] * solution.Value(bits_[i]);
274  }
275  return value;
276 }
277 
278 std::vector<bool> IntegralVariable::GetBooleanSolutionValues(
279  int64_t integral_value) const {
280  if (can_be_reversed_) {
281  DCHECK(std::is_sorted(weights_.begin(), weights_.end()));
282  std::vector<bool> boolean_values(weights_.size(), false);
283  int64_t remaining_value = integral_value - offset_;
284  for (int i = weights_.size() - 1; i >= 0; --i) {
285  if (remaining_value >= weights_[i]) {
286  boolean_values[i] = true;
287  remaining_value -= weights_[i];
288  }
289  }
290  CHECK_EQ(0, remaining_value)
291  << "Couldn't map integral value to boolean variables.";
292  return boolean_values;
293  }
294  return std::vector<bool>();
295 }
296 
297 std::string IntegralVariable::DebugString() const {
298  std::string str;
299  CHECK_EQ(bits_.size(), weights_.size());
300  for (int i = 0; i < bits_.size(); ++i) {
301  str += absl::StrFormat("%d [%d] ", weights_[i], bits_[i].value());
302  }
303  str += absl::StrFormat(" Offset: %d", offset_);
304  return str;
305 }
306 
307 //------------------------------------------------------------------------------
308 // IntegralProblemConverter
309 //------------------------------------------------------------------------------
310 // This class is used to convert a LinearProblem containing integral variables
311 // into a LinearBooleanProblem that Bop can consume.
312 // The converter tries to reuse existing Boolean variables as much as possible,
313 // but there are no guarantees to model all integral variables using the total
314 // minimal number of Boolean variables.
315 // Consider for instance the constraint "x - 2 * y = 0".
316 // Depending on the declaration order, two different outcomes are possible:
317 // - When x is considered first, the converter will generate new variables
318 // for both x and y as we only consider integral weights, i.e. y = x / 2.
319 // - When y is considered first, the converter will reuse Boolean variables
320 // from y to model x as x = 2 * y (integral weight).
321 //
322 // Note that the converter only deals with integral variables, i.e. no
323 // continuous variables.
324 class IntegralProblemConverter {
325  public:
326  IntegralProblemConverter();
327 
328  // Converts the LinearProgram into a LinearBooleanProblem. If an initial
329  // solution is given (i.e. if its size is not zero), converts it into a
330  // Boolean solution.
331  // Returns false when the conversion fails.
332  bool ConvertToBooleanProblem(const LinearProgram& linear_problem,
333  const DenseRow& initial_solution,
334  LinearBooleanProblem* boolean_problem,
335  std::vector<bool>* boolean_initial_solution);
336 
337  // Returns the value of a variable of the original problem based on the
338  // Boolean conversion and the Boolean solution to the problem.
339  int64_t GetSolutionValue(ColIndex global_col,
340  const BopSolution& solution) const;
341 
342  private:
343  // Returns true when the linear_problem_ can be converted into a Boolean
344  // problem. Note that floating weights and continuous variables are not
345  // supported.
346  bool CheckProblem(const LinearProgram& linear_problem) const;
347 
348  // Initializes the type of each variable of the linear_problem_.
349  void InitVariableTypes(const LinearProgram& linear_problem,
350  LinearBooleanProblem* boolean_problem);
351 
352  // Converts all variables of the problem.
353  void ConvertAllVariables(const LinearProgram& linear_problem,
354  LinearBooleanProblem* boolean_problem);
355 
356  // Adds all variables constraints, i.e. lower and upper bounds of variables.
357  void AddVariableConstraints(const LinearProgram& linear_problem,
358  LinearBooleanProblem* boolean_problem);
359 
360  // Converts all constraints from LinearProgram to LinearBooleanProblem.
361  void ConvertAllConstraints(const LinearProgram& linear_problem,
362  LinearBooleanProblem* boolean_problem);
363 
364  // Converts the objective from LinearProgram to LinearBooleanProblem.
365  void ConvertObjective(const LinearProgram& linear_problem,
366  LinearBooleanProblem* boolean_problem);
367 
368  // Converts the integral variable represented by col in the linear_problem_
369  // into an IntegralVariable using existing Boolean variables.
370  // Returns false when existing Boolean variables are not enough to model
371  // the integral variable.
372  bool ConvertUsingExistingBooleans(const LinearProgram& linear_problem,
373  ColIndex col,
374  IntegralVariable* integral_var);
375 
376  // Creates the integral_var using the given linear_problem_ constraint.
377  // The constraint is an equality constraint and contains only one integral
378  // variable (already the case in the model or thanks to previous
379  // booleanization of other integral variables), i.e.
380  // bound <= w * integral_var + sum(w_i * b_i) <= bound
381  // The remaining integral variable can then be expressed:
382  // integral_var == (bound + sum(-w_i * b_i)) / w
383  // Note that all divisions by w have to be integral as Bop only deals with
384  // integral coefficients.
385  bool CreateVariableUsingConstraint(const LinearProgram& linear_problem,
386  RowIndex constraint,
387  IntegralVariable* integral_var);
388 
389  // Adds weighted integral variable represented by col to the current dense
390  // constraint.
391  Fractional AddWeightedIntegralVariable(
392  ColIndex col, Fractional weight,
394 
395  // Scales weights and adds all non-zero scaled weights and literals to t.
396  // t is a constraint or the objective.
397  // Returns the bound error due to the scaling.
398  // The weight is scaled using:
399  // static_cast<int64>(round(weight * scaling_factor)) / gcd;
400  template <class T>
401  double ScaleAndSparsifyWeights(
402  double scaling_factor, int64_t gcd,
403  const absl::StrongVector<VariableIndex, Fractional>& dense_weights, T* t);
404 
405  // Returns true when at least one element is non-zero.
406  bool HasNonZeroWeights(
407  const absl::StrongVector<VariableIndex, Fractional>& dense_weights) const;
408 
409  bool problem_is_boolean_and_has_only_integral_constraints_;
410 
411  // global_to_boolean_[i] represents the Boolean variable index in Bop; when
412  // negative -global_to_boolean_[i] - 1 represents the index of the
413  // integral variable in integral_variables_.
414  absl::StrongVector</*global_col*/ glop::ColIndex, /*boolean_col*/ int>
415  global_to_boolean_;
416  std::vector<IntegralVariable> integral_variables_;
417  std::vector<ColIndex> integral_indices_;
418  int num_boolean_variables_;
419 
420  enum VariableType { BOOLEAN, INTEGRAL, INTEGRAL_EXPRESSED_AS_BOOLEAN };
422 };
423 
424 IntegralProblemConverter::IntegralProblemConverter()
425  : global_to_boolean_(),
426  integral_variables_(),
427  integral_indices_(),
428  num_boolean_variables_(0),
429  variable_types_() {}
430 
431 bool IntegralProblemConverter::ConvertToBooleanProblem(
432  const LinearProgram& linear_problem, const DenseRow& initial_solution,
433  LinearBooleanProblem* boolean_problem,
434  std::vector<bool>* boolean_initial_solution) {
435  bool use_initial_solution = (initial_solution.size() > 0);
436  if (use_initial_solution) {
437  CHECK_EQ(initial_solution.size(), linear_problem.num_variables())
438  << "The initial solution should have the same number of variables as "
439  "the LinearProgram.";
440  CHECK(boolean_initial_solution != nullptr);
441  }
442  if (!CheckProblem(linear_problem)) {
443  return false;
444  }
445 
446  problem_is_boolean_and_has_only_integral_constraints_ =
447  ProblemIsBooleanAndHasOnlyIntegralConstraints(linear_problem);
448  if (problem_is_boolean_and_has_only_integral_constraints_) {
449  BuildBooleanProblemWithIntegralConstraints(linear_problem, initial_solution,
450  boolean_problem,
451  boolean_initial_solution);
452  return true;
453  }
454 
455  InitVariableTypes(linear_problem, boolean_problem);
456  ConvertAllVariables(linear_problem, boolean_problem);
457  boolean_problem->set_num_variables(num_boolean_variables_);
458  boolean_problem->set_name(linear_problem.name());
459 
460  AddVariableConstraints(linear_problem, boolean_problem);
461  ConvertAllConstraints(linear_problem, boolean_problem);
462  ConvertObjective(linear_problem, boolean_problem);
463 
464  // A BooleanLinearProblem is always in the minimization form.
465  if (linear_problem.IsMaximizationProblem()) {
466  sat::ChangeOptimizationDirection(boolean_problem);
467  }
468 
469  if (use_initial_solution) {
470  boolean_initial_solution->assign(boolean_problem->num_variables(), false);
471  for (ColIndex global_col(0); global_col < global_to_boolean_.size();
472  ++global_col) {
473  const int col = global_to_boolean_[global_col];
474  if (col >= 0) {
475  (*boolean_initial_solution)[col] = (initial_solution[global_col] != 0);
476  } else {
477  const IntegralVariable& integral_variable =
478  integral_variables_[-col - 1];
479  const std::vector<VariableIndex>& boolean_cols =
480  integral_variable.bits();
481  const std::vector<bool>& boolean_values =
482  integral_variable.GetBooleanSolutionValues(
483  round(initial_solution[global_col]));
484  if (!boolean_values.empty()) {
485  CHECK_EQ(boolean_cols.size(), boolean_values.size());
486  for (int i = 0; i < boolean_values.size(); ++i) {
487  const int boolean_col = boolean_cols[i].value();
488  (*boolean_initial_solution)[boolean_col] = boolean_values[i];
489  }
490  }
491  }
492  }
493  }
494 
495  return true;
496 }
497 
498 int64_t IntegralProblemConverter::GetSolutionValue(
499  ColIndex global_col, const BopSolution& solution) const {
500  if (problem_is_boolean_and_has_only_integral_constraints_) {
501  return solution.Value(VariableIndex(global_col.value()));
502  }
503 
504  const int pos = global_to_boolean_[global_col];
505  return pos >= 0 ? solution.Value(VariableIndex(pos))
506  : integral_variables_[-pos - 1].GetSolutionValue(solution);
507 }
508 
509 bool IntegralProblemConverter::CheckProblem(
510  const LinearProgram& linear_problem) const {
511  for (ColIndex col(0); col < linear_problem.num_variables(); ++col) {
512  if (!linear_problem.IsVariableInteger(col)) {
513  LOG(ERROR) << "Variable " << linear_problem.GetVariableName(col)
514  << " is continuous. This is not supported by BOP.";
515  return false;
516  }
517  if (linear_problem.variable_lower_bounds()[col] == -kInfinity) {
518  LOG(ERROR) << "Variable " << linear_problem.GetVariableName(col)
519  << " has no lower bound. This is not supported by BOP.";
520  return false;
521  }
522  if (linear_problem.variable_upper_bounds()[col] == kInfinity) {
523  LOG(ERROR) << "Variable " << linear_problem.GetVariableName(col)
524  << " has no upper bound. This is not supported by BOP.";
525  return false;
526  }
527  }
528  return true;
529 }
530 
531 void IntegralProblemConverter::InitVariableTypes(
532  const LinearProgram& linear_problem,
533  LinearBooleanProblem* boolean_problem) {
534  global_to_boolean_.assign(linear_problem.num_variables().value(), 0);
535  variable_types_.assign(linear_problem.num_variables().value(), INTEGRAL);
536  for (ColIndex col(0); col < linear_problem.num_variables(); ++col) {
537  const Fractional lower_bound = linear_problem.variable_lower_bounds()[col];
538  const Fractional upper_bound = linear_problem.variable_upper_bounds()[col];
539 
540  if (lower_bound > -1.0 && upper_bound < 2.0) {
541  // Boolean variable.
542  variable_types_[col] = BOOLEAN;
543  global_to_boolean_[col] = num_boolean_variables_;
544  ++num_boolean_variables_;
545  boolean_problem->add_var_names(linear_problem.GetVariableName(col));
546  } else {
547  // Integral variable.
548  variable_types_[col] = INTEGRAL;
549  integral_indices_.push_back(col);
550  }
551  }
552 }
553 
554 void IntegralProblemConverter::ConvertAllVariables(
555  const LinearProgram& linear_problem,
556  LinearBooleanProblem* boolean_problem) {
557  for (const ColIndex col : integral_indices_) {
558  CHECK_EQ(INTEGRAL, variable_types_[col]);
559  IntegralVariable integral_var;
560  if (!ConvertUsingExistingBooleans(linear_problem, col, &integral_var)) {
561  const Fractional lower_bound =
562  linear_problem.variable_lower_bounds()[col];
563  const Fractional upper_bound =
564  linear_problem.variable_upper_bounds()[col];
565  integral_var.BuildFromRange(num_boolean_variables_, lower_bound,
566  upper_bound);
567  num_boolean_variables_ += integral_var.GetNumberOfBooleanVariables();
568  const std::string var_name = linear_problem.GetVariableName(col);
569  for (int i = 0; i < integral_var.bits().size(); ++i) {
570  boolean_problem->add_var_names(var_name + absl::StrFormat("_%d", i));
571  }
572  }
573  integral_variables_.push_back(integral_var);
574  global_to_boolean_[col] = -integral_variables_.size();
575  variable_types_[col] = INTEGRAL_EXPRESSED_AS_BOOLEAN;
576  }
577 }
578 
579 void IntegralProblemConverter::ConvertAllConstraints(
580  const LinearProgram& linear_problem,
581  LinearBooleanProblem* boolean_problem) {
582  // TODO(user): This is the way it's done in glop/proto_utils.cc but having
583  // to transpose looks unnecessary costly.
584  glop::SparseMatrix transpose;
585  transpose.PopulateFromTranspose(linear_problem.GetSparseMatrix());
586 
587  double max_relative_error = 0.0;
588  double max_bound_error = 0.0;
589  double max_scaling_factor = 0.0;
590  double relative_error = 0.0;
591  double scaling_factor = 0.0;
592  std::vector<double> coefficients;
593  for (RowIndex row(0); row < linear_problem.num_constraints(); ++row) {
594  Fractional offset = 0.0;
596  num_boolean_variables_, 0.0);
597  for (const SparseColumn::Entry e : transpose.column(RowToColIndex(row))) {
598  // Cast in ColIndex due to the transpose.
599  offset += AddWeightedIntegralVariable(RowToColIndex(e.row()),
600  e.coefficient(), &dense_weights);
601  }
602  if (!HasNonZeroWeights(dense_weights)) {
603  continue;
604  }
605 
606  // Compute the scaling for non-integral weights.
607  coefficients.clear();
608  for (VariableIndex var(0); var < num_boolean_variables_; ++var) {
609  if (dense_weights[var] != 0.0) {
610  coefficients.push_back(dense_weights[var]);
611  }
612  }
615  &scaling_factor, &relative_error);
616  const int64_t gcd =
617  ComputeGcdOfRoundedDoubles(coefficients, scaling_factor);
618  max_relative_error = std::max(relative_error, max_relative_error);
619  max_scaling_factor = std::max(scaling_factor / gcd, max_scaling_factor);
620 
621  LinearBooleanConstraint* constraint = boolean_problem->add_constraints();
622  constraint->set_name(linear_problem.GetConstraintName(row));
623  const double bound_error =
624  ScaleAndSparsifyWeights(scaling_factor, gcd, dense_weights, constraint);
625  max_bound_error = std::max(max_bound_error, bound_error);
626 
627  const Fractional lower_bound =
628  linear_problem.constraint_lower_bounds()[row];
629  if (lower_bound != -kInfinity) {
630  const Fractional offset_lower_bound = lower_bound - offset;
631  const double offset_scaled_lower_bound =
632  round(offset_lower_bound * scaling_factor - bound_error);
633  if (offset_scaled_lower_bound >=
634  static_cast<double>(std::numeric_limits<int64_t>::max())) {
635  LOG(WARNING) << "A constraint is trivially unsatisfiable.";
636  return;
637  }
638  if (offset_scaled_lower_bound >
639  -static_cast<double>(std::numeric_limits<int64_t>::max())) {
640  // Otherwise, the constraint is not needed.
641  constraint->set_lower_bound(
642  static_cast<int64_t>(offset_scaled_lower_bound) / gcd);
643  }
644  }
645  const Fractional upper_bound =
646  linear_problem.constraint_upper_bounds()[row];
647  if (upper_bound != kInfinity) {
648  const Fractional offset_upper_bound = upper_bound - offset;
649  const double offset_scaled_upper_bound =
650  round(offset_upper_bound * scaling_factor + bound_error);
651  if (offset_scaled_upper_bound <=
652  -static_cast<double>(std::numeric_limits<int64_t>::max())) {
653  LOG(WARNING) << "A constraint is trivially unsatisfiable.";
654  return;
655  }
656  if (offset_scaled_upper_bound <
657  static_cast<double>(std::numeric_limits<int64_t>::max())) {
658  // Otherwise, the constraint is not needed.
659  constraint->set_upper_bound(
660  static_cast<int64_t>(offset_scaled_upper_bound) / gcd);
661  }
662  }
663  }
664 }
665 
666 void IntegralProblemConverter::ConvertObjective(
667  const LinearProgram& linear_problem,
668  LinearBooleanProblem* boolean_problem) {
669  LinearObjective* objective = boolean_problem->mutable_objective();
670  Fractional offset = 0.0;
672  num_boolean_variables_, 0.0);
673  // Compute the objective weights for the binary variable model.
674  for (ColIndex col(0); col < linear_problem.num_variables(); ++col) {
675  offset += AddWeightedIntegralVariable(
676  col, linear_problem.objective_coefficients()[col], &dense_weights);
677  }
678 
679  // Compute the scaling for non-integral weights.
680  std::vector<double> coefficients;
681  for (VariableIndex var(0); var < num_boolean_variables_; ++var) {
682  if (dense_weights[var] != 0.0) {
683  coefficients.push_back(dense_weights[var]);
684  }
685  }
686  double scaling_factor = 0.0;
687  double max_relative_error = 0.0;
688  double relative_error = 0.0;
691  &scaling_factor, &relative_error);
692  const int64_t gcd = ComputeGcdOfRoundedDoubles(coefficients, scaling_factor);
693  max_relative_error = std::max(relative_error, max_relative_error);
694  VLOG(1) << "objective relative error: " << relative_error;
695  VLOG(1) << "objective scaling factor: " << scaling_factor / gcd;
696 
697  ScaleAndSparsifyWeights(scaling_factor, gcd, dense_weights, objective);
698 
699  // Note that here we set the scaling factor for the inverse operation of
700  // getting the "true" objective value from the scaled one. Hence the inverse.
701  objective->set_scaling_factor(1.0 / scaling_factor * gcd);
702  objective->set_offset((linear_problem.objective_offset() + offset) *
703  scaling_factor / gcd);
704 }
705 
706 void IntegralProblemConverter::AddVariableConstraints(
707  const LinearProgram& linear_problem,
708  LinearBooleanProblem* boolean_problem) {
709  for (ColIndex col(0); col < linear_problem.num_variables(); ++col) {
710  const Fractional lower_bound = linear_problem.variable_lower_bounds()[col];
711  const Fractional upper_bound = linear_problem.variable_upper_bounds()[col];
712  const int pos = global_to_boolean_[col];
713  if (pos >= 0) {
714  // Boolean variable.
715  CHECK_EQ(BOOLEAN, variable_types_[col]);
716  const bool is_fixed = (lower_bound > -1.0 && upper_bound < 1.0) ||
717  (lower_bound > 0.0 && upper_bound < 2.0);
718  if (is_fixed) {
719  // Set the variable.
720  const int fixed_value = lower_bound > -1.0 && upper_bound < 1.0 ? 0 : 1;
721  LinearBooleanConstraint* constraint =
722  boolean_problem->add_constraints();
723  constraint->set_lower_bound(fixed_value);
724  constraint->set_upper_bound(fixed_value);
725  constraint->add_literals(pos + 1);
726  constraint->add_coefficients(1);
727  }
728  } else {
729  CHECK_EQ(INTEGRAL_EXPRESSED_AS_BOOLEAN, variable_types_[col]);
730  // Integral variable.
731  if (lower_bound != -kInfinity || upper_bound != kInfinity) {
732  const IntegralVariable& integral_var = integral_variables_[-pos - 1];
733  LinearBooleanConstraint* constraint =
734  boolean_problem->add_constraints();
735  for (int i = 0; i < integral_var.bits().size(); ++i) {
736  constraint->add_literals(integral_var.bits()[i].value() + 1);
737  constraint->add_coefficients(integral_var.weights()[i]);
738  }
739  if (lower_bound != -kInfinity) {
740  constraint->set_lower_bound(static_cast<int64_t>(ceil(lower_bound)) -
741  integral_var.offset());
742  }
743  if (upper_bound != kInfinity) {
744  constraint->set_upper_bound(static_cast<int64_t>(floor(upper_bound)) -
745  integral_var.offset());
746  }
747  }
748  }
749  }
750 }
751 
752 bool IntegralProblemConverter::ConvertUsingExistingBooleans(
753  const LinearProgram& linear_problem, ColIndex col,
754  IntegralVariable* integral_var) {
755  CHECK(nullptr != integral_var);
756  CHECK_EQ(INTEGRAL, variable_types_[col]);
757 
758  const SparseMatrix& matrix = linear_problem.GetSparseMatrix();
759  const SparseMatrix& transpose = linear_problem.GetTransposeSparseMatrix();
760  for (const SparseColumn::Entry var_entry : matrix.column(col)) {
761  const RowIndex constraint = var_entry.row();
762  const Fractional lb = linear_problem.constraint_lower_bounds()[constraint];
763  const Fractional ub = linear_problem.constraint_upper_bounds()[constraint];
764  if (lb != ub) {
765  // To replace an integral variable by a weighted sum of Boolean variables,
766  // the constraint has to be an equality.
767  continue;
768  }
769 
770  if (transpose.column(RowToColIndex(constraint)).num_entries() <= 1) {
771  // Can't replace the integer variable by Boolean variables when there are
772  // no Boolean variables.
773  // TODO(user): We could actually simplify the problem when the variable
774  // is constant, but this should be done by the preprocessor,
775  // not here. Consider activating the MIP preprocessing.
776  continue;
777  }
778 
779  bool only_one_integral_variable = true;
780  for (const SparseColumn::Entry constraint_entry :
781  transpose.column(RowToColIndex(constraint))) {
782  const ColIndex var_index = RowToColIndex(constraint_entry.row());
783  if (var_index != col && variable_types_[var_index] == INTEGRAL) {
784  only_one_integral_variable = false;
785  break;
786  }
787  }
788  if (only_one_integral_variable &&
789  CreateVariableUsingConstraint(linear_problem, constraint,
790  integral_var)) {
791  return true;
792  }
793  }
794 
795  integral_var->Clear();
796  return false;
797 }
798 
799 bool IntegralProblemConverter::CreateVariableUsingConstraint(
800  const LinearProgram& linear_problem, RowIndex constraint,
801  IntegralVariable* integral_var) {
802  CHECK(nullptr != integral_var);
803  integral_var->Clear();
804 
805  const SparseMatrix& transpose = linear_problem.GetTransposeSparseMatrix();
807  num_boolean_variables_, 0.0);
808  Fractional scale = 1.0;
809  int64_t variable_offset = 0;
810  for (const SparseColumn::Entry constraint_entry :
811  transpose.column(RowToColIndex(constraint))) {
812  const ColIndex col = RowToColIndex(constraint_entry.row());
813  if (variable_types_[col] == INTEGRAL) {
814  scale = constraint_entry.coefficient();
815  } else if (variable_types_[col] == BOOLEAN) {
816  const int pos = global_to_boolean_[col];
817  CHECK_LE(0, pos);
818  dense_weights[VariableIndex(pos)] -= constraint_entry.coefficient();
819  } else {
820  CHECK_EQ(INTEGRAL_EXPRESSED_AS_BOOLEAN, variable_types_[col]);
821  const int pos = global_to_boolean_[col];
822  CHECK_GT(0, pos);
823  const IntegralVariable& local_integral_var =
824  integral_variables_[-pos - 1];
825  variable_offset -=
826  constraint_entry.coefficient() * local_integral_var.offset();
827  for (int i = 0; i < local_integral_var.bits().size(); ++i) {
828  dense_weights[local_integral_var.bits()[i]] -=
829  constraint_entry.coefficient() * local_integral_var.weights()[i];
830  }
831  }
832  }
833 
834  // Rescale using the weight of the integral variable.
835  const Fractional lb = linear_problem.constraint_lower_bounds()[constraint];
836  const Fractional offset = (lb + variable_offset) / scale;
837  if (!IsIntegerWithinTolerance(offset)) {
838  return false;
839  }
840  integral_var->set_offset(static_cast<int64_t>(offset));
841 
842  for (VariableIndex var(0); var < dense_weights.size(); ++var) {
843  if (dense_weights[var] != 0.0) {
844  const Fractional weight = dense_weights[var] / scale;
846  return false;
847  }
848  integral_var->set_weight(var, static_cast<int64_t>(weight));
849  }
850  }
851 
852  return true;
853 }
854 
855 Fractional IntegralProblemConverter::AddWeightedIntegralVariable(
856  ColIndex col, Fractional weight,
858  CHECK(nullptr != dense_weights);
859 
860  if (weight == 0.0) {
861  return 0;
862  }
863 
864  Fractional offset = 0;
865  const int pos = global_to_boolean_[col];
866  if (pos >= 0) {
867  // Boolean variable.
868  (*dense_weights)[VariableIndex(pos)] += weight;
869  } else {
870  // Integral variable.
871  const IntegralVariable& integral_var = integral_variables_[-pos - 1];
872  for (int i = 0; i < integral_var.bits().size(); ++i) {
873  (*dense_weights)[integral_var.bits()[i]] +=
874  integral_var.weights()[i] * weight;
875  }
876  offset += weight * integral_var.offset();
877  }
878  return offset;
879 }
880 
881 template <class T>
882 double IntegralProblemConverter::ScaleAndSparsifyWeights(
883  double scaling_factor, int64_t gcd,
884  const absl::StrongVector<VariableIndex, Fractional>& dense_weights, T* t) {
885  CHECK(nullptr != t);
886 
887  double bound_error = 0.0;
888  for (VariableIndex var(0); var < dense_weights.size(); ++var) {
889  if (dense_weights[var] != 0.0) {
890  const double scaled_weight = dense_weights[var] * scaling_factor;
891  bound_error += fabs(round(scaled_weight) - scaled_weight);
892  t->add_literals(var.value() + 1);
893  t->add_coefficients(static_cast<int64_t>(round(scaled_weight)) / gcd);
894  }
895  }
896 
897  return bound_error;
898 }
899 bool IntegralProblemConverter::HasNonZeroWeights(
900  const absl::StrongVector<VariableIndex, Fractional>& dense_weights) const {
901  for (const Fractional weight : dense_weights) {
902  if (weight != 0.0) {
903  return true;
904  }
905  }
906  return false;
907 }
908 
909 bool CheckSolution(const LinearProgram& linear_problem,
910  const glop::DenseRow& variable_values) {
911  glop::DenseColumn constraint_values(linear_problem.num_constraints(), 0);
912 
913  const SparseMatrix& matrix = linear_problem.GetSparseMatrix();
914  for (ColIndex col(0); col < linear_problem.num_variables(); ++col) {
915  const Fractional lower_bound = linear_problem.variable_lower_bounds()[col];
916  const Fractional upper_bound = linear_problem.variable_upper_bounds()[col];
917  const Fractional value = variable_values[col];
918  if (lower_bound > value || upper_bound < value) {
919  LOG(ERROR) << "Variable " << col << " out of bound: " << value
920  << " should be in " << lower_bound << " .. " << upper_bound;
921  return false;
922  }
923 
924  for (const SparseColumn::Entry entry : matrix.column(col)) {
925  constraint_values[entry.row()] += entry.coefficient() * value;
926  }
927  }
928 
929  for (RowIndex row(0); row < linear_problem.num_constraints(); ++row) {
930  const Fractional lb = linear_problem.constraint_lower_bounds()[row];
931  const Fractional ub = linear_problem.constraint_upper_bounds()[row];
932  const Fractional value = constraint_values[row];
933  if (lb > value || ub < value) {
934  LOG(ERROR) << "Constraint " << row << " out of bound: " << value
935  << " should be in " << lb << " .. " << ub;
936  return false;
937  }
938  }
939 
940  return true;
941 }
942 
943 // Solves the given linear program and returns the solve status.
944 BopSolveStatus InternalSolve(const LinearProgram& linear_problem,
945  const BopParameters& parameters,
946  const DenseRow& initial_solution,
947  TimeLimit* time_limit, DenseRow* variable_values,
948  Fractional* objective_value,
949  Fractional* best_bound) {
950  CHECK(variable_values != nullptr);
951  CHECK(objective_value != nullptr);
952  CHECK(best_bound != nullptr);
953  const bool use_initial_solution = (initial_solution.size() > 0);
954  if (use_initial_solution) {
955  CHECK_EQ(initial_solution.size(), linear_problem.num_variables());
956  }
957 
958  // Those values will only make sense when a solution is found, however we
959  // resize here such that one can access the values even if they don't mean
960  // anything.
961  variable_values->resize(linear_problem.num_variables(), 0);
962 
963  LinearBooleanProblem boolean_problem;
964  std::vector<bool> boolean_initial_solution;
965  IntegralProblemConverter converter;
966  if (!converter.ConvertToBooleanProblem(linear_problem, initial_solution,
967  &boolean_problem,
968  &boolean_initial_solution)) {
969  return BopSolveStatus::INVALID_PROBLEM;
970  }
971 
972  BopSolver bop_solver(boolean_problem);
973  bop_solver.SetParameters(parameters);
974  BopSolveStatus status = BopSolveStatus::NO_SOLUTION_FOUND;
975  if (use_initial_solution) {
976  BopSolution bop_solution(boolean_problem, "InitialSolution");
977  CHECK_EQ(boolean_initial_solution.size(), boolean_problem.num_variables());
978  for (int i = 0; i < boolean_initial_solution.size(); ++i) {
979  bop_solution.SetValue(VariableIndex(i), boolean_initial_solution[i]);
980  }
981  status = bop_solver.SolveWithTimeLimit(bop_solution, time_limit);
982  } else {
983  status = bop_solver.SolveWithTimeLimit(time_limit);
984  }
985  if (status == BopSolveStatus::OPTIMAL_SOLUTION_FOUND ||
986  status == BopSolveStatus::FEASIBLE_SOLUTION_FOUND) {
987  // Compute objective value.
988  const BopSolution& solution = bop_solver.best_solution();
989  CHECK(solution.IsFeasible());
990 
991  *objective_value = linear_problem.objective_offset();
992  for (ColIndex col(0); col < linear_problem.num_variables(); ++col) {
993  const int64_t value = converter.GetSolutionValue(col, solution);
994  (*variable_values)[col] = value;
995  *objective_value += value * linear_problem.objective_coefficients()[col];
996  }
997 
998  CheckSolution(linear_problem, *variable_values);
999 
1000  // TODO(user): Check that the scaled best bound from Bop is a valid one
1001  // even after conversion. If yes, remove the optimality test.
1002  *best_bound = status == BopSolveStatus::OPTIMAL_SOLUTION_FOUND
1003  ? *objective_value
1004  : bop_solver.GetScaledBestBound();
1005  }
1006  return status;
1007 }
1008 
1009 void RunOneBop(const BopParameters& parameters, int problem_index,
1010  const DenseRow& initial_solution, TimeLimit* time_limit,
1011  LPDecomposer* decomposer, DenseRow* variable_values,
1012  Fractional* objective_value, Fractional* best_bound,
1013  BopSolveStatus* status) {
1014  CHECK(decomposer != nullptr);
1015  CHECK(variable_values != nullptr);
1016  CHECK(objective_value != nullptr);
1017  CHECK(best_bound != nullptr);
1018  CHECK(status != nullptr);
1019 
1020  LinearProgram problem;
1021  decomposer->ExtractLocalProblem(problem_index, &problem);
1022  DenseRow local_initial_solution;
1023  if (initial_solution.size() > 0) {
1024  local_initial_solution =
1025  decomposer->ExtractLocalAssignment(problem_index, initial_solution);
1026  }
1027  // TODO(user): Investigate a better approximation of the time needed to
1028  // solve the problem than just the number of variables.
1029  const double total_num_variables = std::max(
1030  1.0, static_cast<double>(
1031  decomposer->original_problem().num_variables().value()));
1032  const double time_per_variable =
1033  parameters.max_time_in_seconds() / total_num_variables;
1034  const double deterministic_time_per_variable =
1035  parameters.max_deterministic_time() / total_num_variables;
1036  const int local_num_variables = std::max(1, problem.num_variables().value());
1037 
1038  NestedTimeLimit subproblem_time_limit(
1039  time_limit,
1040  std::max(time_per_variable * local_num_variables,
1041  parameters.decomposed_problem_min_time_in_seconds()),
1042  deterministic_time_per_variable * local_num_variables);
1043 
1044  *status = InternalSolve(problem, parameters, local_initial_solution,
1045  subproblem_time_limit.GetTimeLimit(), variable_values,
1046  objective_value, best_bound);
1047 }
1048 } // anonymous namespace
1049 
1050 IntegralSolver::IntegralSolver()
1051  : parameters_(), variable_values_(), objective_value_(0.0) {}
1052 
1053 BopSolveStatus IntegralSolver::Solve(const LinearProgram& linear_problem) {
1054  return Solve(linear_problem, DenseRow());
1055 }
1056 
1058  const LinearProgram& linear_problem, TimeLimit* time_limit) {
1059  return SolveWithTimeLimit(linear_problem, DenseRow(), time_limit);
1060 }
1061 
1063  const LinearProgram& linear_problem,
1064  const DenseRow& user_provided_initial_solution) {
1065  std::unique_ptr<TimeLimit> time_limit =
1066  TimeLimit::FromParameters(parameters_);
1067  return SolveWithTimeLimit(linear_problem, user_provided_initial_solution,
1068  time_limit.get());
1069 }
1070 
1072  const LinearProgram& linear_problem,
1073  const DenseRow& user_provided_initial_solution, TimeLimit* time_limit) {
1074  // We make a copy so that we can clear it if the presolve is active.
1075  DenseRow initial_solution = user_provided_initial_solution;
1076  if (initial_solution.size() > 0) {
1077  CHECK_EQ(initial_solution.size(), linear_problem.num_variables())
1078  << "The initial solution should have the same number of variables as "
1079  "the LinearProgram.";
1080  }
1081 
1082  // Some code path requires to copy the given linear_problem. When this
1083  // happens, we will simply change the target of this pointer.
1084  LinearProgram const* lp = &linear_problem;
1085 
1086  BopSolveStatus status;
1087  if (lp->num_variables() >= parameters_.decomposer_num_variables_threshold()) {
1088  LPDecomposer decomposer;
1089  decomposer.Decompose(lp);
1090  const int num_sub_problems = decomposer.GetNumberOfProblems();
1091  VLOG(1) << "Problem is decomposable into " << num_sub_problems
1092  << " components!";
1093  if (num_sub_problems > 1) {
1094  // The problem can be decomposed. Solve each sub-problem and aggregate the
1095  // result.
1096  std::vector<DenseRow> variable_values(num_sub_problems);
1097  std::vector<Fractional> objective_values(num_sub_problems,
1098  Fractional(0.0));
1099  std::vector<Fractional> best_bounds(num_sub_problems, Fractional(0.0));
1100  std::vector<BopSolveStatus> statuses(num_sub_problems,
1102 
1103  for (int i = 0; i < num_sub_problems; ++i) {
1104  RunOneBop(parameters_, i, initial_solution, time_limit, &decomposer,
1105  &(variable_values[i]), &(objective_values[i]),
1106  &(best_bounds[i]), &(statuses[i]));
1107  }
1108 
1109  // Aggregate results.
1111  objective_value_ = lp->objective_offset();
1112  best_bound_ = 0.0;
1113  for (int i = 0; i < num_sub_problems; ++i) {
1114  objective_value_ += objective_values[i];
1115  best_bound_ += best_bounds[i];
1116  if (statuses[i] == BopSolveStatus::NO_SOLUTION_FOUND ||
1117  statuses[i] == BopSolveStatus::INFEASIBLE_PROBLEM ||
1118  statuses[i] == BopSolveStatus::INVALID_PROBLEM) {
1119  return statuses[i];
1120  }
1121 
1122  if (statuses[i] == BopSolveStatus::FEASIBLE_SOLUTION_FOUND) {
1124  }
1125  }
1126  variable_values_ = decomposer.AggregateAssignments(variable_values);
1127  CheckSolution(*lp, variable_values_);
1128  } else {
1129  status =
1130  InternalSolve(*lp, parameters_, initial_solution, time_limit,
1131  &variable_values_, &objective_value_, &best_bound_);
1132  }
1133  } else {
1134  status = InternalSolve(*lp, parameters_, initial_solution, time_limit,
1135  &variable_values_, &objective_value_, &best_bound_);
1136  }
1137 
1138  return status;
1139 }
1140 
1141 } // namespace bop
1142 } // namespace operations_research
int64 max
Definition: alldiff_cst.cc:139
#define CHECK(condition)
Definition: base/logging.h:495
#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 CHECK_LE(val1, val2)
Definition: base/logging.h:699
#define VLOG(verboselevel)
Definition: base/logging.h:978
size_type size() const
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
Definition: time_limit.h:105
static std::unique_ptr< TimeLimit > FromParameters(const Parameters &parameters)
Creates a time limit object initialized from an object that provides methods max_time_in_seconds() an...
Definition: time_limit.h:159
ABSL_MUST_USE_RESULT BopSolveStatus SolveWithTimeLimit(const glop::LinearProgram &linear_problem, TimeLimit *time_limit)
const glop::DenseRow & variable_values() const
ABSL_MUST_USE_RESULT BopSolveStatus Solve(const glop::LinearProgram &linear_problem)
SatParameters parameters
SharedTimeLimit * time_limit
const Constraint * ct
int64 value
IntVar * var
Definition: expr_array.cc:1858
const int64 offset_
Definition: interval.cc:2076
const int WARNING
Definition: log_severity.h:31
const int ERROR
Definition: log_severity.h:32
ColIndex col
Definition: markowitz.cc:176
RowIndex row
Definition: markowitz.cc:175
bool CheckSolution(const Model &model, const std::function< int64(IntegerVariable *)> &evaluator)
Definition: checker.cc:1263
StrictITIVector< ColIndex, Fractional > DenseRow
Definition: lp_types.h:299
ColIndex RowToColIndex(RowIndex row)
Definition: lp_types.h:48
StrictITIVector< RowIndex, Fractional > DenseColumn
Definition: lp_types.h:328
const double kInfinity
Definition: lp_types.h:83
void ChangeOptimizationDirection(LinearBooleanProblem *problem)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
bool IsIntegerWithinTolerance(FloatType x, FloatType tolerance)
Definition: fp_utils.h:161
int MostSignificantBitPosition64(uint64 n)
Definition: bitset.h:231
int64 ComputeGcdOfRoundedDoubles(const std::vector< double > &x, double scaling_factor)
Definition: fp_utils.cc:189
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
int64 weight
Definition: pack.cc:509
EntryIndex num_entries
int64 delta
Definition: resource.cc:1684
double max_scaling_factor
std::vector< double > coefficients