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
24
25namespace operations_research {
26namespace bop {
27
28using ::operations_research::glop::ColIndex;
32using ::operations_research::glop::LinearProgram;
33using ::operations_research::glop::LPDecomposer;
34using ::operations_research::glop::RowIndex;
35using ::operations_research::glop::SparseColumn;
36using ::operations_research::glop::SparseMatrix;
37using ::operations_research::sat::LinearBooleanConstraint;
38using ::operations_research::sat::LinearBooleanProblem;
39using ::operations_research::sat::LinearObjective;
40
41namespace {
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.
51bool 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.
77void 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.
185class 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
233IntegralVariable::IntegralVariable()
234 : bits_(), weights_(), offset_(0), can_be_reversed_(true) {}
235
236void 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
257void IntegralVariable::Clear() {
258 bits_.clear();
259 weights_.clear();
260 offset_ = 0;
261 can_be_reversed_ = true;
262}
263
264void 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
270int64_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
278std::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
297std::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.
324class 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
424IntegralProblemConverter::IntegralProblemConverter()
425 : global_to_boolean_(),
426 integral_variables_(),
427 integral_indices_(),
428 num_boolean_variables_(0),
429 variable_types_() {}
430
431bool 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
498int64_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
509bool 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
531void 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
554void 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
579void 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 =
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
666void 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
706void 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
752bool 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
799bool 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
855Fractional 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
881template <class T>
882double 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}
899bool 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
909bool 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.
944BopSolveStatus 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
1009void 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
1050IntegralSolver::IntegralSolver()
1051 : parameters_(), variable_values_(), objective_value_(0.0) {}
1052
1053BopSolveStatus 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)
ABSL_MUST_USE_RESULT BopSolveStatus Solve(const glop::LinearProgram &linear_problem)
const glop::DenseRow & variable_values() const
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...
int64 ComputeGcdOfRoundedDoubles(const std::vector< double > &x, double scaling_factor)
Definition: fp_utils.cc:189
int MostSignificantBitPosition64(uint64 n)
Definition: bitset.h:231
bool IsIntegerWithinTolerance(FloatType x, FloatType tolerance)
Definition: fp_utils.h:161
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