OR-Tools  8.2
sat/lp_utils.cc
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
15
16#include <stdlib.h>
17
18#include <algorithm>
19#include <cmath>
20#include <limits>
21#include <string>
22#include <vector>
23
24#include "absl/strings/str_cat.h"
29#include "ortools/glop/parameters.pb.h"
33#include "ortools/sat/integer.h"
36
37namespace operations_research {
38namespace sat {
39
40using glop::ColIndex;
42using glop::kInfinity;
43using glop::RowIndex;
44
45using operations_research::MPConstraintProto;
46using operations_research::MPModelProto;
47using operations_research::MPVariableProto;
48
49namespace {
50
51void ScaleConstraint(const std::vector<double>& var_scaling,
52 MPConstraintProto* mp_constraint) {
53 const int num_terms = mp_constraint->coefficient_size();
54 for (int i = 0; i < num_terms; ++i) {
55 const int var_index = mp_constraint->var_index(i);
56 mp_constraint->set_coefficient(
57 i, mp_constraint->coefficient(i) / var_scaling[var_index]);
58 }
59}
60
61void ApplyVarScaling(const std::vector<double> var_scaling,
62 MPModelProto* mp_model) {
63 const int num_variables = mp_model->variable_size();
64 for (int i = 0; i < num_variables; ++i) {
65 const double scaling = var_scaling[i];
66 const MPVariableProto& mp_var = mp_model->variable(i);
67 const double old_lb = mp_var.lower_bound();
68 const double old_ub = mp_var.upper_bound();
69 const double old_obj = mp_var.objective_coefficient();
70 mp_model->mutable_variable(i)->set_lower_bound(old_lb * scaling);
71 mp_model->mutable_variable(i)->set_upper_bound(old_ub * scaling);
72 mp_model->mutable_variable(i)->set_objective_coefficient(old_obj / scaling);
73 }
74 for (MPConstraintProto& mp_constraint : *mp_model->mutable_constraint()) {
75 ScaleConstraint(var_scaling, &mp_constraint);
76 }
77 for (MPGeneralConstraintProto& general_constraint :
78 *mp_model->mutable_general_constraint()) {
79 switch (general_constraint.general_constraint_case()) {
80 case MPGeneralConstraintProto::kIndicatorConstraint:
81 ScaleConstraint(var_scaling,
82 general_constraint.mutable_indicator_constraint()
83 ->mutable_constraint());
84 break;
85 case MPGeneralConstraintProto::kAndConstraint:
86 case MPGeneralConstraintProto::kOrConstraint:
87 // These constraints have only Boolean variables and no constants. They
88 // don't need scaling.
89 break;
90 default:
91 LOG(FATAL) << "Scaling unsupported for general constraint of type "
92 << general_constraint.general_constraint_case();
93 }
94 }
95}
96
97} // namespace
98
99std::vector<double> ScaleContinuousVariables(double scaling, double max_bound,
100 MPModelProto* mp_model) {
101 const int num_variables = mp_model->variable_size();
102 std::vector<double> var_scaling(num_variables, 1.0);
103 for (int i = 0; i < num_variables; ++i) {
104 if (mp_model->variable(i).is_integer()) continue;
105 const double lb = mp_model->variable(i).lower_bound();
106 const double ub = mp_model->variable(i).upper_bound();
107 const double magnitude = std::max(std::abs(lb), std::abs(ub));
108 if (magnitude == 0 || magnitude > max_bound) continue;
109 var_scaling[i] = std::min(scaling, max_bound / magnitude);
110 }
111 ApplyVarScaling(var_scaling, mp_model);
112 return var_scaling;
113}
114
115// This uses the best rational approximation of x via continuous fractions. It
116// is probably not the best implementation, but according to the unit test, it
117// seems to do the job.
118int FindRationalFactor(double x, int limit, double tolerance) {
119 const double initial_x = x;
120 x = std::abs(x);
121 x -= std::floor(x);
122 int q = 1;
123 int prev_q = 0;
124 while (q < limit) {
125 if (std::abs(q * initial_x - std::round(q * initial_x)) < q * tolerance) {
126 return q;
127 }
128 x = 1 / x;
129 const int new_q = prev_q + static_cast<int>(std::floor(x)) * q;
130 prev_q = q;
131 q = new_q;
132 x -= std::floor(x);
133 }
134 return 0;
135}
136
137namespace {
138
139// Returns a factor such that factor * var only need to take integer values to
140// satisfy the given constraint. Return 0.0 if we didn't find such factor.
141//
142// Precondition: var must be the only non-integer in the given constraint.
143double GetIntegralityMultiplier(const MPModelProto& mp_model,
144 const std::vector<double>& var_scaling, int var,
145 int ct_index, double tolerance) {
146 DCHECK(!mp_model.variable(var).is_integer());
147 const MPConstraintProto& ct = mp_model.constraint(ct_index);
148 double multiplier = 1.0;
149 double var_coeff = 0.0;
150 const double max_multiplier = 1e4;
151 for (int i = 0; i < ct.var_index().size(); ++i) {
152 if (var == ct.var_index(i)) {
153 var_coeff = ct.coefficient(i);
154 continue;
155 }
156
157 DCHECK(mp_model.variable(ct.var_index(i)).is_integer());
158 // This actually compute the smallest multiplier to make all other
159 // terms in the constraint integer.
160 const double coeff =
161 multiplier * ct.coefficient(i) / var_scaling[ct.var_index(i)];
162 multiplier *=
163 FindRationalFactor(coeff, /*limit=*/100, multiplier * tolerance);
164 if (multiplier == 0 || multiplier > max_multiplier) return 0.0;
165 }
166 DCHECK_NE(var_coeff, 0.0);
167
168 // The constraint bound need to be infinite or integer.
169 for (const double bound : {ct.lower_bound(), ct.upper_bound()}) {
170 if (!std::isfinite(bound)) continue;
171 if (std::abs(std::round(bound * multiplier) - bound * multiplier) >
172 tolerance * multiplier) {
173 return 0.0;
174 }
175 }
176 return std::abs(multiplier * var_coeff);
177}
178
179} // namespace
180
181void RemoveNearZeroTerms(const SatParameters& params, MPModelProto* mp_model) {
182 const int num_variables = mp_model->variable_size();
183
184 // Compute for each variable its current maximum magnitude. Note that we will
185 // only scale variable with a coefficient >= 1, so it is safe to use this
186 // bound.
187 std::vector<double> max_bounds(num_variables);
188 for (int i = 0; i < num_variables; ++i) {
189 double value = std::abs(mp_model->variable(i).lower_bound());
190 value = std::max(value, std::abs(mp_model->variable(i).upper_bound()));
191 value = std::min(value, params.mip_max_bound());
192 max_bounds[i] = value;
193 }
194
195 // We want the maximum absolute error while setting coefficients to zero to
196 // not exceed our mip wanted precision. So for a binary variable we might set
197 // to zero coefficient around 1e-7. But for large domain, we need lower coeff
198 // than that, around 1e-12 with the default params.mip_max_bound(). This also
199 // depends on the size of the constraint.
200 int64 num_removed = 0;
201 double largest_removed = 0.0;
202 const int num_constraints = mp_model->constraint_size();
203 for (int c = 0; c < num_constraints; ++c) {
204 MPConstraintProto* ct = mp_model->mutable_constraint(c);
205 int new_size = 0;
206 const int size = ct->var_index().size();
207 if (size == 0) continue;
208 const double threshold =
209 params.mip_wanted_precision() / static_cast<double>(size);
210 for (int i = 0; i < size; ++i) {
211 const int var = ct->var_index(i);
212 const double coeff = ct->coefficient(i);
213 if (std::abs(coeff) * max_bounds[var] < threshold) {
214 largest_removed = std::max(largest_removed, std::abs(coeff));
215 continue;
216 }
217 ct->set_var_index(new_size, var);
218 ct->set_coefficient(new_size, coeff);
219 ++new_size;
220 }
221 num_removed += size - new_size;
222 ct->mutable_var_index()->Truncate(new_size);
223 ct->mutable_coefficient()->Truncate(new_size);
224 }
225
226 const bool log_info = VLOG_IS_ON(1) || params.log_search_progress();
227 if (log_info && num_removed > 0) {
228 LOG(INFO) << "Removed " << num_removed
229 << " near zero terms with largest magnitude of "
230 << largest_removed << ".";
231 }
232}
233
234std::vector<double> DetectImpliedIntegers(bool log_info,
235 MPModelProto* mp_model) {
236 const int num_variables = mp_model->variable_size();
237 std::vector<double> var_scaling(num_variables, 1.0);
238
239 int initial_num_integers = 0;
240 for (int i = 0; i < num_variables; ++i) {
241 if (mp_model->variable(i).is_integer()) ++initial_num_integers;
242 }
243 VLOG(1) << "Initial num integers: " << initial_num_integers;
244
245 // We will process all equality constraints with exactly one non-integer.
246 const double tolerance = 1e-6;
247 std::vector<int> constraint_queue;
248
249 const int num_constraints = mp_model->constraint_size();
250 std::vector<int> constraint_to_num_non_integer(num_constraints, 0);
251 std::vector<std::vector<int>> var_to_constraints(num_variables);
252 for (int i = 0; i < num_constraints; ++i) {
253 const MPConstraintProto& mp_constraint = mp_model->constraint(i);
254
255 for (const int var : mp_constraint.var_index()) {
256 if (!mp_model->variable(var).is_integer()) {
257 var_to_constraints[var].push_back(i);
258 constraint_to_num_non_integer[i]++;
259 }
260 }
261 if (constraint_to_num_non_integer[i] == 1) {
262 constraint_queue.push_back(i);
263 }
264 }
265 VLOG(1) << "Initial constraint queue: " << constraint_queue.size() << " / "
266 << num_constraints;
267
268 int num_detected = 0;
269 double max_scaling = 0.0;
270 auto scale_and_mark_as_integer = [&](int var, double scaling) mutable {
271 CHECK_NE(var, -1);
272 CHECK(!mp_model->variable(var).is_integer());
273 CHECK_EQ(var_scaling[var], 1.0);
274 if (scaling != 1.0) {
275 VLOG(2) << "Scaled " << var << " by " << scaling;
276 }
277
278 ++num_detected;
279 max_scaling = std::max(max_scaling, scaling);
280
281 // Scale the variable right away and mark it as implied integer.
282 // Note that the constraints will be scaled later.
283 var_scaling[var] = scaling;
284 mp_model->mutable_variable(var)->set_is_integer(true);
285
286 // Update the queue of constraints with a single non-integer.
287 for (const int ct_index : var_to_constraints[var]) {
288 constraint_to_num_non_integer[ct_index]--;
289 if (constraint_to_num_non_integer[ct_index] == 1) {
290 constraint_queue.push_back(ct_index);
291 }
292 }
293 };
294
295 int num_fail_due_to_rhs = 0;
296 int num_fail_due_to_large_multiplier = 0;
297 int num_processed_constraints = 0;
298 while (!constraint_queue.empty()) {
299 const int top_ct_index = constraint_queue.back();
300 constraint_queue.pop_back();
301
302 // The non integer variable was already made integer by one other
303 // constraint.
304 if (constraint_to_num_non_integer[top_ct_index] == 0) continue;
305
306 // Ignore non-equality here.
307 const MPConstraintProto& ct = mp_model->constraint(top_ct_index);
308 if (ct.lower_bound() + tolerance < ct.upper_bound()) continue;
309
310 ++num_processed_constraints;
311
312 // This will be set to the unique non-integer term of this constraint.
313 int var = -1;
314 double var_coeff;
315
316 // We are looking for a "multiplier" so that the unique non-integer term
317 // in this constraint (i.e. var * var_coeff) times this multiplier is an
318 // integer.
319 //
320 // If this is set to zero or becomes too large, we fail to detect a new
321 // implied integer and ignore this constraint.
322 double multiplier = 1.0;
323 const double max_multiplier = 1e4;
324
325 for (int i = 0; i < ct.var_index().size(); ++i) {
326 if (!mp_model->variable(ct.var_index(i)).is_integer()) {
327 CHECK_EQ(var, -1);
328 var = ct.var_index(i);
329 var_coeff = ct.coefficient(i);
330 } else {
331 // This actually compute the smallest multiplier to make all other
332 // terms in the constraint integer.
333 const double coeff =
334 multiplier * ct.coefficient(i) / var_scaling[ct.var_index(i)];
335 multiplier *=
336 FindRationalFactor(coeff, /*limit=*/100, multiplier * tolerance);
337 if (multiplier == 0 || multiplier > max_multiplier) {
338 break;
339 }
340 }
341 }
342
343 if (multiplier == 0 || multiplier > max_multiplier) {
344 ++num_fail_due_to_large_multiplier;
345 continue;
346 }
347
348 // These "rhs" fail could be handled by shifting the variable.
349 const double rhs = ct.lower_bound();
350 if (std::abs(std::round(rhs * multiplier) - rhs * multiplier) >
351 tolerance * multiplier) {
352 ++num_fail_due_to_rhs;
353 continue;
354 }
355
356 // We want to multiply the variable so that it is integer. We know that
357 // coeff * multiplier is an integer, so we just multiply by that.
358 //
359 // But if a variable appear in more than one equality, we want to find the
360 // smallest integrality factor! See diameterc-msts-v40a100d5i.mps
361 // for an instance of this.
362 double best_scaling = std::abs(var_coeff * multiplier);
363 for (const int ct_index : var_to_constraints[var]) {
364 if (ct_index == top_ct_index) continue;
365 if (constraint_to_num_non_integer[ct_index] != 1) continue;
366
367 // Ignore non-equality here.
368 const MPConstraintProto& ct = mp_model->constraint(top_ct_index);
369 if (ct.lower_bound() + tolerance < ct.upper_bound()) continue;
370
371 const double multiplier = GetIntegralityMultiplier(
372 *mp_model, var_scaling, var, ct_index, tolerance);
373 if (multiplier != 0.0 && multiplier < best_scaling) {
374 best_scaling = multiplier;
375 }
376 }
377
378 scale_and_mark_as_integer(var, best_scaling);
379 }
380
381 // Process continuous variables that only appear as the unique non integer
382 // in a set of non-equality constraints.
383 //
384 // Note that turning to integer such variable cannot in turn trigger new
385 // integer detection, so there is no point doing that in a loop.
386 int num_in_inequalities = 0;
387 int num_to_be_handled = 0;
388 for (int var = 0; var < num_variables; ++var) {
389 if (mp_model->variable(var).is_integer()) continue;
390
391 // This should be presolved and not happen.
392 if (var_to_constraints[var].empty()) continue;
393
394 bool ok = true;
395 for (const int ct_index : var_to_constraints[var]) {
396 if (constraint_to_num_non_integer[ct_index] != 1) {
397 ok = false;
398 break;
399 }
400 }
401 if (!ok) continue;
402
403 std::vector<double> scaled_coeffs;
404 for (const int ct_index : var_to_constraints[var]) {
405 const double multiplier = GetIntegralityMultiplier(
406 *mp_model, var_scaling, var, ct_index, tolerance);
407 if (multiplier == 0.0) {
408 ok = false;
409 break;
410 }
411 scaled_coeffs.push_back(multiplier);
412 }
413 if (!ok) continue;
414
415 // The situation is a bit tricky here, we have a bunch of coeffs c_i, and we
416 // know that X * c_i can take integer value without changing the constraint
417 // i meaning.
418 //
419 // For now we take the min, and scale only if all c_i / min are integer.
420 double scaling = scaled_coeffs[0];
421 for (const double c : scaled_coeffs) {
422 scaling = std::min(scaling, c);
423 }
424 CHECK_GT(scaling, 0.0);
425 for (const double c : scaled_coeffs) {
426 const double fraction = c / scaling;
427 if (std::abs(std::round(fraction) - fraction) > tolerance) {
428 ok = false;
429 break;
430 }
431 }
432 if (!ok) {
433 // TODO(user): be smarter! we should be able to handle these cases.
434 ++num_to_be_handled;
435 continue;
436 }
437
438 // Tricky, we also need the bound of the scaled variable to be integer.
439 for (const double bound : {mp_model->variable(var).lower_bound(),
440 mp_model->variable(var).upper_bound()}) {
441 if (!std::isfinite(bound)) continue;
442 if (std::abs(std::round(bound * scaling) - bound * scaling) >
443 tolerance * scaling) {
444 ok = false;
445 break;
446 }
447 }
448 if (!ok) {
449 // TODO(user): If we scale more we migth be able to turn it into an
450 // integer.
451 ++num_to_be_handled;
452 continue;
453 }
454
455 ++num_in_inequalities;
456 scale_and_mark_as_integer(var, scaling);
457 }
458 VLOG(1) << "num_new_integer: " << num_detected
459 << " num_processed_constraints: " << num_processed_constraints
460 << " num_rhs_fail: " << num_fail_due_to_rhs
461 << " num_multiplier_fail: " << num_fail_due_to_large_multiplier;
462
463 if (log_info && num_to_be_handled > 0) {
464 LOG(INFO) << "Missed " << num_to_be_handled
465 << " potential implied integer.";
466 }
467
468 const int num_integers = initial_num_integers + num_detected;
469 LOG_IF(INFO, log_info) << "Num integers: " << num_integers << "/"
470 << num_variables << " (implied: " << num_detected
471 << " in_inequalities: " << num_in_inequalities
472 << " max_scaling: " << max_scaling << ")"
473 << (num_integers == num_variables ? " [IP] "
474 : " [MIP] ");
475
476 ApplyVarScaling(var_scaling, mp_model);
477 return var_scaling;
478}
479
480namespace {
481
482// We use a class to reuse the temporay memory.
483struct ConstraintScaler {
484 // Scales an individual constraint.
485 ConstraintProto* AddConstraint(const MPModelProto& mp_model,
486 const MPConstraintProto& mp_constraint,
487 CpModelProto* cp_model);
488
491 double max_scaling_factor = 0.0;
492
493 double wanted_precision = 1e-6;
495 std::vector<int> var_indices;
496 std::vector<double> coefficients;
497 std::vector<double> lower_bounds;
498 std::vector<double> upper_bounds;
499};
500
501namespace {
502
503double FindFractionalScaling(const std::vector<double>& coefficients,
504 double tolerance) {
505 double multiplier = 1.0;
506 for (const double coeff : coefficients) {
507 multiplier *=
508 FindRationalFactor(coeff, /*limit=*/1e8, multiplier * tolerance);
509 if (multiplier == 0.0) break;
510 }
511 return multiplier;
512}
513
514} // namespace
515
516ConstraintProto* ConstraintScaler::AddConstraint(
517 const MPModelProto& mp_model, const MPConstraintProto& mp_constraint,
518 CpModelProto* cp_model) {
519 if (mp_constraint.lower_bound() == -kInfinity &&
520 mp_constraint.upper_bound() == kInfinity) {
521 return nullptr;
522 }
523
524 auto* constraint = cp_model->add_constraints();
525 constraint->set_name(mp_constraint.name());
526 auto* arg = constraint->mutable_linear();
527
528 // First scale the coefficients of the constraints so that the constraint
529 // sum can always be computed without integer overflow.
530 var_indices.clear();
531 coefficients.clear();
532 lower_bounds.clear();
533 upper_bounds.clear();
534 const int num_coeffs = mp_constraint.coefficient_size();
535 for (int i = 0; i < num_coeffs; ++i) {
536 const auto& var_proto = cp_model->variables(mp_constraint.var_index(i));
537 const int64 lb = var_proto.domain(0);
538 const int64 ub = var_proto.domain(var_proto.domain_size() - 1);
539 if (lb == 0 && ub == 0) continue;
540
541 const double coeff = mp_constraint.coefficient(i);
542 if (coeff == 0.0) continue;
543
544 var_indices.push_back(mp_constraint.var_index(i));
545 coefficients.push_back(coeff);
546 lower_bounds.push_back(lb);
547 upper_bounds.push_back(ub);
548 }
549
550 // We compute the worst case error relative to the magnitude of the bounds.
551 Fractional lb = mp_constraint.lower_bound();
552 Fractional ub = mp_constraint.upper_bound();
553 const double ct_norm = std::max(1.0, std::min(std::abs(lb), std::abs(ub)));
554
555 double scaling_factor = GetBestScalingOfDoublesToInt64(
557
558 // Returns the smallest factor of the form 2^i that gives us a relative sum
559 // error of wanted_precision and still make sure we will have no integer
560 // overflow.
561 //
562 // TODO(user): Make this faster.
563 double x = std::min(scaling_factor, 1.0);
564 double relative_coeff_error;
565 double scaled_sum_error;
566 for (; x <= scaling_factor; x *= 2) {
568 &relative_coeff_error, &scaled_sum_error);
569 if (scaled_sum_error < wanted_precision * x * ct_norm) break;
570 }
571 scaling_factor = x;
572
573 // Because we deal with an approximate input, scaling with a power of 2 might
574 // not be the best choice. It is also possible user used rational coeff and
575 // then converted them to double (1/2, 1/3, 4/5, etc...). This scaling will
576 // recover such rational input and might result in a smaller overall
577 // coefficient which is good.
578 const double integer_factor = FindFractionalScaling(coefficients, 1e-8);
579 if (integer_factor != 0 && integer_factor < scaling_factor) {
581 &relative_coeff_error, &scaled_sum_error);
582 if (scaled_sum_error < wanted_precision * integer_factor * ct_norm) {
583 scaling_factor = integer_factor;
584 }
585 }
586
587 const int64 gcd = ComputeGcdOfRoundedDoubles(coefficients, scaling_factor);
589 std::max(relative_coeff_error, max_relative_coeff_error);
590 max_scaling_factor = std::max(scaling_factor / gcd, max_scaling_factor);
591
592 // We do not relax the constraint bound if all variables are integer and
593 // we made no error at all during our scaling.
594 bool relax_bound = scaled_sum_error > 0;
595
596 for (int i = 0; i < coefficients.size(); ++i) {
597 const double scaled_value = coefficients[i] * scaling_factor;
598 const int64 value = static_cast<int64>(std::round(scaled_value)) / gcd;
599 if (value != 0) {
600 if (!mp_model.variable(var_indices[i]).is_integer()) {
601 relax_bound = true;
602 }
603 arg->add_vars(var_indices[i]);
604 arg->add_coeffs(value);
605 }
606 }
608 max_relative_rhs_error, scaled_sum_error / (scaling_factor * ct_norm));
609
610 // Add the constraint bounds. Because we are sure the scaled constraint fit
611 // on an int64, if the scaled bounds are too large, the constraint is either
612 // always true or always false.
613 if (relax_bound) {
614 lb -= std::max(std::abs(lb), 1.0) * wanted_precision;
615 }
616 const Fractional scaled_lb = std::ceil(lb * scaling_factor);
617 if (lb == -kInfinity || scaled_lb <= kint64min) {
618 arg->add_domain(kint64min);
619 } else {
620 arg->add_domain(CeilRatio(IntegerValue(static_cast<int64>(scaled_lb)),
621 IntegerValue(gcd))
622 .value());
623 }
624
625 if (relax_bound) {
626 ub += std::max(std::abs(ub), 1.0) * wanted_precision;
627 }
628 const Fractional scaled_ub = std::floor(ub * scaling_factor);
629 if (ub == kInfinity || scaled_ub >= kint64max) {
630 arg->add_domain(kint64max);
631 } else {
632 arg->add_domain(FloorRatio(IntegerValue(static_cast<int64>(scaled_ub)),
633 IntegerValue(gcd))
634 .value());
635 }
636
637 return constraint;
638}
639
640} // namespace
641
642bool ConvertMPModelProtoToCpModelProto(const SatParameters& params,
643 const MPModelProto& mp_model,
644 CpModelProto* cp_model) {
645 CHECK(cp_model != nullptr);
646 cp_model->Clear();
647 cp_model->set_name(mp_model.name());
648
649 // To make sure we cannot have integer overflow, we use this bound for any
650 // unbounded variable.
651 //
652 // TODO(user): This could be made larger if needed, so be smarter if we have
653 // MIP problem that we cannot "convert" because of this. Note however than we
654 // cannot go that much further because we need to make sure we will not run
655 // into overflow if we add a big linear combination of such variables. It
656 // should always be possible for a user to scale its problem so that all
657 // relevant quantities are a couple of millions. A LP/MIP solver have a
658 // similar condition in disguise because problem with a difference of more
659 // than 6 magnitudes between the variable values will likely run into numeric
660 // trouble.
661 const int64 kMaxVariableBound = static_cast<int64>(params.mip_max_bound());
662
663 int num_truncated_bounds = 0;
664 int num_small_domains = 0;
665 const int64 kSmallDomainSize = 1000;
666 const double kWantedPrecision = params.mip_wanted_precision();
667
668 // Add the variables.
669 const int num_variables = mp_model.variable_size();
670 for (int i = 0; i < num_variables; ++i) {
671 const MPVariableProto& mp_var = mp_model.variable(i);
672 IntegerVariableProto* cp_var = cp_model->add_variables();
673 cp_var->set_name(mp_var.name());
674
675 // Deal with the corner case of a domain far away from zero.
676 //
677 // TODO(user): We should deal with these case by shifting the domain so
678 // that it includes zero instead of just fixing the variable. But that is a
679 // bit of work as it requires some postsolve.
680 if (mp_var.lower_bound() > kMaxVariableBound) {
681 // Fix var to its lower bound.
682 ++num_truncated_bounds;
683 const int64 value = static_cast<int64>(std::round(mp_var.lower_bound()));
684 cp_var->add_domain(value);
685 cp_var->add_domain(value);
686 continue;
687 } else if (mp_var.upper_bound() < -kMaxVariableBound) {
688 // Fix var to its upper_bound.
689 ++num_truncated_bounds;
690 const int64 value = static_cast<int64>(std::round(mp_var.upper_bound()));
691 cp_var->add_domain(value);
692 cp_var->add_domain(value);
693 continue;
694 }
695
696 // Note that we must process the lower bound first.
697 for (const bool lower : {true, false}) {
698 const double bound = lower ? mp_var.lower_bound() : mp_var.upper_bound();
699 if (std::abs(bound) >= kMaxVariableBound) {
700 ++num_truncated_bounds;
701 cp_var->add_domain(bound < 0 ? -kMaxVariableBound : kMaxVariableBound);
702 continue;
703 }
704
705 // Note that the cast is "perfect" because we forbid large values.
706 cp_var->add_domain(
707 static_cast<int64>(lower ? std::ceil(bound - kWantedPrecision)
708 : std::floor(bound + kWantedPrecision)));
709 }
710
711 if (cp_var->domain(0) > cp_var->domain(1)) {
712 LOG(WARNING) << "Variable #" << i << " cannot take integer value. "
713 << mp_var.ShortDebugString();
714 return false;
715 }
716
717 // Notify if a continuous variable has a small domain as this is likely to
718 // make an all integer solution far from a continuous one.
719 if (!mp_var.is_integer() && cp_var->domain(0) != cp_var->domain(1) &&
720 cp_var->domain(1) - cp_var->domain(0) < kSmallDomainSize) {
721 ++num_small_domains;
722 }
723 }
724
725 LOG_IF(WARNING, num_truncated_bounds > 0)
726 << num_truncated_bounds << " bounds were truncated to "
727 << kMaxVariableBound << ".";
728 LOG_IF(WARNING, num_small_domains > 0)
729 << num_small_domains << " continuous variable domain with fewer than "
730 << kSmallDomainSize << " values.";
731
732 ConstraintScaler scaler;
733 const int64 kScalingTarget = int64{1} << params.mip_max_activity_exponent();
734 scaler.wanted_precision = kWantedPrecision;
735 scaler.scaling_target = kScalingTarget;
736
737 // Add the constraints. We scale each of them individually.
738 for (const MPConstraintProto& mp_constraint : mp_model.constraint()) {
739 scaler.AddConstraint(mp_model, mp_constraint, cp_model);
740 }
741 for (const MPGeneralConstraintProto& general_constraint :
742 mp_model.general_constraint()) {
743 switch (general_constraint.general_constraint_case()) {
744 case MPGeneralConstraintProto::kIndicatorConstraint: {
745 const auto& indicator_constraint =
746 general_constraint.indicator_constraint();
747 const MPConstraintProto& mp_constraint =
748 indicator_constraint.constraint();
749 ConstraintProto* ct =
750 scaler.AddConstraint(mp_model, mp_constraint, cp_model);
751 if (ct == nullptr) continue;
752
753 // Add the indicator.
754 const int var = indicator_constraint.var_index();
755 const int value = indicator_constraint.var_value();
756 ct->add_enforcement_literal(value == 1 ? var : NegatedRef(var));
757 break;
758 }
759 case MPGeneralConstraintProto::kAndConstraint: {
760 const auto& and_constraint = general_constraint.and_constraint();
761 const std::string& name = general_constraint.name();
762
763 ConstraintProto* ct_pos = cp_model->add_constraints();
764 ct_pos->set_name(name.empty() ? "" : absl::StrCat(name, "_pos"));
765 ct_pos->add_enforcement_literal(and_constraint.resultant_var_index());
766 *ct_pos->mutable_bool_and()->mutable_literals() =
767 and_constraint.var_index();
768
769 ConstraintProto* ct_neg = cp_model->add_constraints();
770 ct_neg->set_name(name.empty() ? "" : absl::StrCat(name, "_neg"));
771 ct_neg->add_enforcement_literal(
772 NegatedRef(and_constraint.resultant_var_index()));
773 for (const int var_index : and_constraint.var_index()) {
774 ct_neg->mutable_bool_or()->add_literals(NegatedRef(var_index));
775 }
776 break;
777 }
778 case MPGeneralConstraintProto::kOrConstraint: {
779 const auto& or_constraint = general_constraint.or_constraint();
780 const std::string& name = general_constraint.name();
781
782 ConstraintProto* ct_pos = cp_model->add_constraints();
783 ct_pos->set_name(name.empty() ? "" : absl::StrCat(name, "_pos"));
784 ct_pos->add_enforcement_literal(or_constraint.resultant_var_index());
785 *ct_pos->mutable_bool_or()->mutable_literals() =
786 or_constraint.var_index();
787
788 ConstraintProto* ct_neg = cp_model->add_constraints();
789 ct_neg->set_name(name.empty() ? "" : absl::StrCat(name, "_neg"));
790 ct_neg->add_enforcement_literal(
791 NegatedRef(or_constraint.resultant_var_index()));
792 for (const int var_index : or_constraint.var_index()) {
793 ct_neg->mutable_bool_and()->add_literals(NegatedRef(var_index));
794 }
795 break;
796 }
797 default:
798 LOG(ERROR) << "Can't convert general constraints of type "
799 << general_constraint.general_constraint_case()
800 << " to CpModelProto.";
801 return false;
802 }
803 }
804
805 // Display the error/scaling on the constraints.
806 const bool log_info = VLOG_IS_ON(1) || params.log_search_progress();
807 LOG_IF(INFO, log_info) << "Maximum constraint coefficient relative error: "
808 << scaler.max_relative_coeff_error;
809 LOG_IF(INFO, log_info)
810 << "Maximum constraint worst-case activity relative error: "
811 << scaler.max_relative_rhs_error
812 << (scaler.max_relative_rhs_error > params.mip_check_precision()
813 ? " [Potentially IMPRECISE]"
814 : "");
815 LOG_IF(INFO, log_info) << "Maximum constraint scaling factor: "
816 << scaler.max_scaling_factor;
817
818 // Add the objective.
819 std::vector<int> var_indices;
820 std::vector<double> coefficients;
821 std::vector<double> lower_bounds;
822 std::vector<double> upper_bounds;
823 double min_magnitude = std::numeric_limits<double>::infinity();
824 double max_magnitude = 0.0;
825 double l1_norm = 0.0;
826 for (int i = 0; i < num_variables; ++i) {
827 const MPVariableProto& mp_var = mp_model.variable(i);
828 if (mp_var.objective_coefficient() == 0.0) continue;
829
830 const auto& var_proto = cp_model->variables(i);
831 const int64 lb = var_proto.domain(0);
832 const int64 ub = var_proto.domain(var_proto.domain_size() - 1);
833 if (lb == 0 && ub == 0) continue;
834
835 var_indices.push_back(i);
836 coefficients.push_back(mp_var.objective_coefficient());
837 lower_bounds.push_back(lb);
838 upper_bounds.push_back(ub);
839 min_magnitude = std::min(min_magnitude, std::abs(coefficients.back()));
840 max_magnitude = std::max(max_magnitude, std::abs(coefficients.back()));
841 l1_norm += std::abs(coefficients.back());
842 }
843 if (!coefficients.empty()) {
844 const double average_magnitude =
845 l1_norm / static_cast<double>(coefficients.size());
846 LOG_IF(INFO, log_info) << "Objective magnitude in [" << min_magnitude
847 << ", " << max_magnitude
848 << "] average = " << average_magnitude;
849 }
850 if (!coefficients.empty() || mp_model.objective_offset() != 0.0) {
851 double scaling_factor = GetBestScalingOfDoublesToInt64(
852 coefficients, lower_bounds, upper_bounds, kScalingTarget);
853
854 // Returns the smallest factor of the form 2^i that gives us an absolute
855 // error of kWantedPrecision and still make sure we will have no integer
856 // overflow.
857 //
858 // TODO(user): Make this faster.
859 double x = std::min(scaling_factor, 1.0);
860 double relative_coeff_error;
861 double scaled_sum_error;
862 for (; x <= scaling_factor; x *= 2) {
864 &relative_coeff_error, &scaled_sum_error);
865 if (scaled_sum_error < kWantedPrecision * x) break;
866 }
867 scaling_factor = x;
868
869 // Same remark as for the constraint.
870 // TODO(user): Extract common code.
871 const double integer_factor = FindFractionalScaling(coefficients, 1e-8);
872 if (integer_factor != 0 && integer_factor < scaling_factor) {
874 &relative_coeff_error, &scaled_sum_error);
875 if (scaled_sum_error < kWantedPrecision * integer_factor) {
876 scaling_factor = integer_factor;
877 }
878 }
879
880 const int64 gcd = ComputeGcdOfRoundedDoubles(coefficients, scaling_factor);
881
882 // Display the objective error/scaling.
883 LOG_IF(INFO, log_info)
884 << "Objective coefficient relative error: " << relative_coeff_error
885 << (relative_coeff_error > params.mip_check_precision() ? " [IMPRECISE]"
886 : "");
887 LOG_IF(INFO, log_info) << "Objective worst-case absolute error: "
888 << scaled_sum_error / scaling_factor;
889 LOG_IF(INFO, log_info) << "Objective scaling factor: "
890 << scaling_factor / gcd;
891
892 // Note that here we set the scaling factor for the inverse operation of
893 // getting the "true" objective value from the scaled one. Hence the
894 // inverse.
895 auto* objective = cp_model->mutable_objective();
896 const int mult = mp_model.maximize() ? -1 : 1;
897 objective->set_offset(mp_model.objective_offset() * scaling_factor / gcd *
898 mult);
899 objective->set_scaling_factor(1.0 / scaling_factor * gcd * mult);
900 for (int i = 0; i < coefficients.size(); ++i) {
901 const int64 value =
902 static_cast<int64>(std::round(coefficients[i] * scaling_factor)) /
903 gcd;
904 if (value != 0) {
905 objective->add_vars(var_indices[i]);
906 objective->add_coeffs(value * mult);
907 }
908 }
909 }
910
911 return true;
912}
913
914bool ConvertBinaryMPModelProtoToBooleanProblem(const MPModelProto& mp_model,
915 LinearBooleanProblem* problem) {
916 CHECK(problem != nullptr);
917 problem->Clear();
918 problem->set_name(mp_model.name());
919 const int num_variables = mp_model.variable_size();
920 problem->set_num_variables(num_variables);
921
922 // Test if the variables are binary variables.
923 // Add constraints for the fixed variables.
924 for (int var_id(0); var_id < num_variables; ++var_id) {
925 const MPVariableProto& mp_var = mp_model.variable(var_id);
926 problem->add_var_names(mp_var.name());
927
928 // This will be changed to false as soon as we detect the variable to be
929 // non-binary. This is done this way so we can display a nice error message
930 // before aborting the function and returning false.
931 bool is_binary = mp_var.is_integer();
932
933 const Fractional lb = mp_var.lower_bound();
934 const Fractional ub = mp_var.upper_bound();
935 if (lb <= -1.0) is_binary = false;
936 if (ub >= 2.0) is_binary = false;
937 if (is_binary) {
938 // 4 cases.
939 if (lb <= 0.0 && ub >= 1.0) {
940 // Binary variable. Ok.
941 } else if (lb <= 1.0 && ub >= 1.0) {
942 // Fixed variable at 1.
943 LinearBooleanConstraint* constraint = problem->add_constraints();
944 constraint->set_lower_bound(1);
945 constraint->set_upper_bound(1);
946 constraint->add_literals(var_id + 1);
947 constraint->add_coefficients(1);
948 } else if (lb <= 0.0 && ub >= 0.0) {
949 // Fixed variable at 0.
950 LinearBooleanConstraint* constraint = problem->add_constraints();
951 constraint->set_lower_bound(0);
952 constraint->set_upper_bound(0);
953 constraint->add_literals(var_id + 1);
954 constraint->add_coefficients(1);
955 } else {
956 // No possible integer value!
957 is_binary = false;
958 }
959 }
960
961 // Abort if the variable is not binary.
962 if (!is_binary) {
963 LOG(WARNING) << "The variable #" << var_id << " with name "
964 << mp_var.name() << " is not binary. "
965 << "lb: " << lb << " ub: " << ub;
966 return false;
967 }
968 }
969
970 // Variables needed to scale the double coefficients into int64.
971 const int64 kInt64Max = std::numeric_limits<int64>::max();
972 double max_relative_error = 0.0;
973 double max_bound_error = 0.0;
974 double max_scaling_factor = 0.0;
975 double relative_error = 0.0;
976 double scaling_factor = 0.0;
977 std::vector<double> coefficients;
978
979 // Add all constraints.
980 for (const MPConstraintProto& mp_constraint : mp_model.constraint()) {
981 LinearBooleanConstraint* constraint = problem->add_constraints();
982 constraint->set_name(mp_constraint.name());
983
984 // First scale the coefficients of the constraints.
985 coefficients.clear();
986 const int num_coeffs = mp_constraint.coefficient_size();
987 for (int i = 0; i < num_coeffs; ++i) {
988 coefficients.push_back(mp_constraint.coefficient(i));
989 }
990 GetBestScalingOfDoublesToInt64(coefficients, kInt64Max, &scaling_factor,
991 &relative_error);
992 const int64 gcd = ComputeGcdOfRoundedDoubles(coefficients, scaling_factor);
993 max_relative_error = std::max(relative_error, max_relative_error);
994 max_scaling_factor = std::max(scaling_factor / gcd, max_scaling_factor);
995
996 double bound_error = 0.0;
997 for (int i = 0; i < num_coeffs; ++i) {
998 const double scaled_value = mp_constraint.coefficient(i) * scaling_factor;
999 bound_error += std::abs(round(scaled_value) - scaled_value);
1000 const int64 value = static_cast<int64>(round(scaled_value)) / gcd;
1001 if (value != 0) {
1002 constraint->add_literals(mp_constraint.var_index(i) + 1);
1003 constraint->add_coefficients(value);
1004 }
1005 }
1006 max_bound_error = std::max(max_bound_error, bound_error);
1007
1008 // Add the bounds. Note that we do not pass them to
1009 // GetBestScalingOfDoublesToInt64() because we know that the sum of absolute
1010 // coefficients of the constraint fit on an int64. If one of the scaled
1011 // bound overflows, we don't care by how much because in this case the
1012 // constraint is just trivial or unsatisfiable.
1013 const Fractional lb = mp_constraint.lower_bound();
1014 if (lb != -kInfinity) {
1015 if (lb * scaling_factor > static_cast<double>(kInt64Max)) {
1016 LOG(WARNING) << "A constraint is trivially unsatisfiable.";
1017 return false;
1018 }
1019 if (lb * scaling_factor > -static_cast<double>(kInt64Max)) {
1020 // Otherwise, the constraint is not needed.
1021 constraint->set_lower_bound(
1022 static_cast<int64>(round(lb * scaling_factor - bound_error)) / gcd);
1023 }
1024 }
1025 const Fractional ub = mp_constraint.upper_bound();
1026 if (ub != kInfinity) {
1027 if (ub * scaling_factor < -static_cast<double>(kInt64Max)) {
1028 LOG(WARNING) << "A constraint is trivially unsatisfiable.";
1029 return false;
1030 }
1031 if (ub * scaling_factor < static_cast<double>(kInt64Max)) {
1032 // Otherwise, the constraint is not needed.
1033 constraint->set_upper_bound(
1034 static_cast<int64>(round(ub * scaling_factor + bound_error)) / gcd);
1035 }
1036 }
1037 }
1038
1039 // Display the error/scaling without taking into account the objective first.
1040 LOG(INFO) << "Maximum constraint relative error: " << max_relative_error;
1041 LOG(INFO) << "Maximum constraint bound error: " << max_bound_error;
1042 LOG(INFO) << "Maximum constraint scaling factor: " << max_scaling_factor;
1043
1044 // Add the objective.
1045 coefficients.clear();
1046 for (int var_id = 0; var_id < num_variables; ++var_id) {
1047 const MPVariableProto& mp_var = mp_model.variable(var_id);
1048 coefficients.push_back(mp_var.objective_coefficient());
1049 }
1050 GetBestScalingOfDoublesToInt64(coefficients, kInt64Max, &scaling_factor,
1051 &relative_error);
1052 const int64 gcd = ComputeGcdOfRoundedDoubles(coefficients, scaling_factor);
1053 max_relative_error = std::max(relative_error, max_relative_error);
1054
1055 // Display the objective error/scaling.
1056 LOG(INFO) << "objective relative error: " << relative_error;
1057 LOG(INFO) << "objective scaling factor: " << scaling_factor / gcd;
1058
1059 LinearObjective* objective = problem->mutable_objective();
1060 objective->set_offset(mp_model.objective_offset() * scaling_factor / gcd);
1061
1062 // Note that here we set the scaling factor for the inverse operation of
1063 // getting the "true" objective value from the scaled one. Hence the inverse.
1064 objective->set_scaling_factor(1.0 / scaling_factor * gcd);
1065 for (int var_id = 0; var_id < num_variables; ++var_id) {
1066 const MPVariableProto& mp_var = mp_model.variable(var_id);
1067 const int64 value = static_cast<int64>(round(
1068 mp_var.objective_coefficient() * scaling_factor)) /
1069 gcd;
1070 if (value != 0) {
1071 objective->add_literals(var_id + 1);
1072 objective->add_coefficients(value);
1073 }
1074 }
1075
1076 // If the problem was a maximization one, we need to modify the objective.
1077 if (mp_model.maximize()) ChangeOptimizationDirection(problem);
1078
1079 // Test the precision of the conversion.
1080 const double kRelativeTolerance = 1e-8;
1081 if (max_relative_error > kRelativeTolerance) {
1082 LOG(WARNING) << "The relative error during double -> int64 conversion "
1083 << "is too high!";
1084 return false;
1085 }
1086 return true;
1087}
1088
1089void ConvertBooleanProblemToLinearProgram(const LinearBooleanProblem& problem,
1090 glop::LinearProgram* lp) {
1091 lp->Clear();
1092 for (int i = 0; i < problem.num_variables(); ++i) {
1093 const ColIndex col = lp->CreateNewVariable();
1095 lp->SetVariableBounds(col, 0.0, 1.0);
1096 }
1097
1098 // Variables name are optional.
1099 if (problem.var_names_size() != 0) {
1100 CHECK_EQ(problem.var_names_size(), problem.num_variables());
1101 for (int i = 0; i < problem.num_variables(); ++i) {
1102 lp->SetVariableName(ColIndex(i), problem.var_names(i));
1103 }
1104 }
1105
1106 for (const LinearBooleanConstraint& constraint : problem.constraints()) {
1107 const RowIndex constraint_index = lp->CreateNewConstraint();
1108 lp->SetConstraintName(constraint_index, constraint.name());
1109 double sum = 0.0;
1110 for (int i = 0; i < constraint.literals_size(); ++i) {
1111 const int literal = constraint.literals(i);
1112 const double coeff = constraint.coefficients(i);
1113 const ColIndex variable_index = ColIndex(abs(literal) - 1);
1114 if (literal < 0) {
1115 sum += coeff;
1116 lp->SetCoefficient(constraint_index, variable_index, -coeff);
1117 } else {
1118 lp->SetCoefficient(constraint_index, variable_index, coeff);
1119 }
1120 }
1122 constraint_index,
1123 constraint.has_lower_bound() ? constraint.lower_bound() - sum
1124 : -kInfinity,
1125 constraint.has_upper_bound() ? constraint.upper_bound() - sum
1126 : kInfinity);
1127 }
1128
1129 // Objective.
1130 {
1131 double sum = 0.0;
1132 const LinearObjective& objective = problem.objective();
1133 const double scaling_factor = objective.scaling_factor();
1134 for (int i = 0; i < objective.literals_size(); ++i) {
1135 const int literal = objective.literals(i);
1136 const double coeff =
1137 static_cast<double>(objective.coefficients(i)) * scaling_factor;
1138 const ColIndex variable_index = ColIndex(abs(literal) - 1);
1139 if (literal < 0) {
1140 sum += coeff;
1141 lp->SetObjectiveCoefficient(variable_index, -coeff);
1142 } else {
1143 lp->SetObjectiveCoefficient(variable_index, coeff);
1144 }
1145 }
1146 lp->SetObjectiveOffset((sum + objective.offset()) * scaling_factor);
1147 lp->SetMaximizationProblem(scaling_factor < 0);
1148 }
1149
1150 lp->CleanUp();
1151}
1152
1154 int num_fixed_variables = 0;
1155 const Trail& trail = solver.LiteralTrail();
1156 for (int i = 0; i < trail.Index(); ++i) {
1157 const BooleanVariable var = trail[i].Variable();
1158 const int value = trail[i].IsPositive() ? 1.0 : 0.0;
1159 if (trail.Info(var).level == 0) {
1160 ++num_fixed_variables;
1161 lp->SetVariableBounds(ColIndex(var.value()), value, value);
1162 }
1163 }
1164 return num_fixed_variables;
1165}
1166
1168 const glop::LinearProgram& lp, SatSolver* sat_solver,
1169 double max_time_in_seconds) {
1170 glop::LPSolver solver;
1171 glop::GlopParameters glop_parameters;
1172 glop_parameters.set_max_time_in_seconds(max_time_in_seconds);
1173 solver.SetParameters(glop_parameters);
1174 const glop::ProblemStatus& status = solver.Solve(lp);
1175 if (status != glop::ProblemStatus::OPTIMAL &&
1178 return false;
1179 }
1180 for (ColIndex col(0); col < lp.num_variables(); ++col) {
1181 const Fractional& value = solver.variable_values()[col];
1182 sat_solver->SetAssignmentPreference(
1183 Literal(BooleanVariable(col.value()), round(value) == 1),
1184 1 - std::abs(value - round(value)));
1185 }
1186 return true;
1187}
1188
1190 LinearBooleanProblem* problem) {
1191 glop::LPSolver solver;
1192 const glop::ProblemStatus& status = solver.Solve(lp);
1193 if (status != glop::ProblemStatus::OPTIMAL &&
1195 return false;
1196 int num_variable_fixed = 0;
1197 for (ColIndex col(0); col < lp.num_variables(); ++col) {
1198 const Fractional tolerance = 1e-5;
1199 const Fractional& value = solver.variable_values()[col];
1200 if (value > 1 - tolerance) {
1201 ++num_variable_fixed;
1202 LinearBooleanConstraint* constraint = problem->add_constraints();
1203 constraint->set_lower_bound(1);
1204 constraint->set_upper_bound(1);
1205 constraint->add_coefficients(1);
1206 constraint->add_literals(col.value() + 1);
1207 } else if (value < tolerance) {
1208 ++num_variable_fixed;
1209 LinearBooleanConstraint* constraint = problem->add_constraints();
1210 constraint->set_lower_bound(0);
1211 constraint->set_upper_bound(0);
1212 constraint->add_coefficients(1);
1213 constraint->add_literals(col.value() + 1);
1214 }
1215 }
1216 LOG(INFO) << "LNS with " << num_variable_fixed << " fixed variables.";
1217 return true;
1218}
1219
1220} // namespace sat
1221} // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
int64 max
Definition: alldiff_cst.cc:139
#define LOG_IF(severity, condition)
Definition: base/logging.h:479
#define CHECK(condition)
Definition: base/logging.h:495
#define DCHECK_NE(val1, val2)
Definition: base/logging.h:886
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define CHECK_GT(val1, val2)
Definition: base/logging.h:702
#define CHECK_NE(val1, val2)
Definition: base/logging.h:698
#define LOG(severity)
Definition: base/logging.h:420
#define DCHECK(condition)
Definition: base/logging.h:884
#define VLOG(verboselevel)
Definition: base/logging.h:978
const DenseRow & variable_values() const
Definition: lp_solver.h:100
ABSL_MUST_USE_RESULT ProblemStatus Solve(const LinearProgram &lp)
Definition: lp_solver.cc:121
void SetParameters(const GlopParameters &parameters)
Definition: lp_solver.cc:113
void SetVariableBounds(ColIndex col, Fractional lower_bound, Fractional upper_bound)
Definition: lp_data.cc:248
void SetConstraintName(RowIndex row, absl::string_view name)
Definition: lp_data.cc:244
void SetObjectiveOffset(Fractional objective_offset)
Definition: lp_data.cc:330
void SetCoefficient(RowIndex row, ColIndex col, Fractional value)
Definition: lp_data.cc:316
void SetVariableName(ColIndex col, absl::string_view name)
Definition: lp_data.cc:231
void SetConstraintBounds(RowIndex row, Fractional lower_bound, Fractional upper_bound)
Definition: lp_data.cc:308
void SetVariableType(ColIndex col, VariableType type)
Definition: lp_data.cc:235
void SetObjectiveCoefficient(ColIndex col, Fractional value)
Definition: lp_data.cc:325
void SetMaximizationProblem(bool maximize)
Definition: lp_data.cc:342
const Trail & LiteralTrail() const
Definition: sat_solver.h:361
void SetAssignmentPreference(Literal literal, double weight)
Definition: sat_solver.h:150
const AssignmentInfo & Info(BooleanVariable var) const
Definition: sat_base.h:381
const std::string name
const Constraint * ct
int64 value
IntVar * var
Definition: expr_array.cc:1858
static const int64 kint64max
int64_t int64
static const int64 kint64min
const int WARNING
Definition: log_severity.h:31
const int INFO
Definition: log_severity.h:31
const int ERROR
Definition: log_severity.h:32
const int FATAL
Definition: log_severity.h:32
ColIndex col
Definition: markowitz.cc:176
const double kInfinity
Definition: lp_types.h:83
bool SolveLpAndUseSolutionForSatAssignmentPreference(const glop::LinearProgram &lp, SatSolver *sat_solver, double max_time_in_seconds)
void RemoveNearZeroTerms(const SatParameters &params, MPModelProto *mp_model)
void ConvertBooleanProblemToLinearProgram(const LinearBooleanProblem &problem, glop::LinearProgram *lp)
std::vector< double > DetectImpliedIntegers(bool log_info, MPModelProto *mp_model)
bool ConvertBinaryMPModelProtoToBooleanProblem(const MPModelProto &mp_model, LinearBooleanProblem *problem)
IntegerValue FloorRatio(IntegerValue dividend, IntegerValue positive_divisor)
Definition: integer.h:90
bool SolveLpAndUseIntegerVariableToStartLNS(const glop::LinearProgram &lp, LinearBooleanProblem *problem)
void ChangeOptimizationDirection(LinearBooleanProblem *problem)
int FixVariablesFromSat(const SatSolver &solver, glop::LinearProgram *lp)
IntegerValue CeilRatio(IntegerValue dividend, IntegerValue positive_divisor)
Definition: integer.h:81
std::vector< double > ScaleContinuousVariables(double scaling, double max_bound, MPModelProto *mp_model)
Definition: sat/lp_utils.cc:99
bool ConvertMPModelProtoToCpModelProto(const SatParameters &params, const MPModelProto &mp_model, CpModelProto *cp_model)
int FindRationalFactor(double x, int limit, double tolerance)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 ComputeGcdOfRoundedDoubles(const std::vector< double > &x, double scaling_factor)
Definition: fp_utils.cc:189
void ComputeScalingErrors(const std::vector< double > &input, const std::vector< double > &lb, const std::vector< double > &ub, double scaling_factor, double *max_relative_coeff_error, double *max_scaled_sum_error)
Definition: fp_utils.cc:159
double GetBestScalingOfDoublesToInt64(const std::vector< double > &input, const std::vector< double > &lb, const std::vector< double > &ub, int64 max_absolute_sum)
Definition: fp_utils.cc:168
Literal literal
Definition: optimization.cc:84
int64 bound
double max_scaling_factor
double max_relative_coeff_error
std::vector< double > lower_bounds
double wanted_precision
int64 scaling_target
std::vector< int > var_indices
std::vector< double > upper_bounds
std::vector< double > coefficients
double max_relative_rhs_error
#define VLOG_IS_ON(verboselevel)
Definition: vlog_is_on.h:41