Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
linear_programming_constraint.h
Go to the documentation of this file.
1// Copyright 2010-2025 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14#ifndef OR_TOOLS_SAT_LINEAR_PROGRAMMING_CONSTRAINT_H_
15#define OR_TOOLS_SAT_LINEAR_PROGRAMMING_CONSTRAINT_H_
16
17#include <cstdint>
18#include <functional>
19#include <memory>
20#include <optional>
21#include <string>
22#include <utility>
23#include <vector>
24
25#include "absl/container/flat_hash_map.h"
26#include "absl/numeric/int128.h"
27#include "absl/strings/string_view.h"
28#include "absl/types/span.h"
30#include "ortools/glop/parameters.pb.h"
35#include "ortools/sat/cp_model.pb.h"
37#include "ortools/sat/cuts.h"
39#include "ortools/sat/integer.h"
45#include "ortools/sat/model.h"
47#include "ortools/sat/sat_parameters.pb.h"
49#include "ortools/sat/util.h"
51#include "ortools/util/rev.h"
54
55namespace operations_research {
56namespace sat {
57
58// Simple class to combine linear expression efficiently. First in a sparse
59// way that switch to dense when the number of non-zeros grows.
61 public:
62 // This must be called with the correct size before any other functions are
63 // used.
64 void ClearAndResize(int size);
65
66 // Does vector[col] += value and return false in case of overflow.
67 bool Add(glop::ColIndex col, IntegerValue value);
68
69 // Similar to Add() but for multiplier * terms.
70 //
71 // Returns false if we encountered any integer overflow. If the template bool
72 // is false, we do not check for a bit of extra speed.
73 template <bool check_overflow = true>
74 bool AddLinearExpressionMultiple(IntegerValue multiplier,
75 absl::Span<const glop::ColIndex> cols,
76 absl::Span<const IntegerValue> coeffs,
77 IntegerValue max_coeff_magnitude);
78
79 // This is not const only because non_zeros is sorted. Note that sorting the
80 // non-zeros make the result deterministic whether or not we were in sparse
81 // mode.
82 //
83 // TODO(user): Ideally we should convert to IntegerVariable as late as
84 // possible. Prefer to use GetTerms().
86 absl::Span<const IntegerVariable> integer_variables,
87 IntegerValue upper_bound,
88 std::optional<std::pair<IntegerVariable, IntegerValue>> extra_term =
89 std::nullopt);
90
91 void ConvertToCutData(absl::int128 rhs,
92 absl::Span<const IntegerVariable> integer_variables,
93 absl::Span<const double> lp_solution,
94 IntegerTrail* integer_trail, CutData* result);
95
96 // Similar to ConvertToLinearConstraint().
97 std::vector<std::pair<glop::ColIndex, IntegerValue>> GetTerms();
98
99 // We only provide the const [].
100 IntegerValue operator[](glop::ColIndex col) const {
101 return dense_vector_[col];
102 }
103
104 bool IsSparse() const { return is_sparse_; }
105
106 private:
107 // If is_sparse is true we maintain the non_zeros positions and bool vector
108 // of dense_vector_. Otherwise we don't. Note that we automatically switch
109 // from sparse to dense as needed.
110 bool is_sparse_ = true;
111 std::vector<glop::ColIndex> non_zeros_;
113
114 // The dense representation of the vector.
116};
117
118// A SAT constraint that enforces a set of linear inequality constraints on
119// integer variables using an LP solver.
120//
121// The propagator uses glop's revised simplex for feasibility and propagation.
122// It uses the Reduced Cost Strengthening technique, a classic in mixed integer
123// programming, for instance see the thesis of Tobias Achterberg,
124// "Constraint Integer Programming", sections 7.7 and 8.8, algorithm 7.11.
125// http://nbn-resolving.de/urn:nbn:de:0297-zib-11129
126//
127// Per-constraint bounds propagation is NOT done by this constraint,
128// it should be done by redundant constraints, as reduced cost propagation
129// may miss some filtering.
130//
131// Note that this constraint works with double floating-point numbers, so one
132// could be worried that it may filter too much in case of precision issues.
133// However, by default, we interpret the LP result by recomputing everything
134// in integer arithmetic, so we are exact.
135class LinearProgrammingDispatcher;
136
139 public:
140 typedef glop::RowIndex ConstraintIndex;
141
142 // Each linear programming constraint works on a fixed set of variables.
143 // We expect the set of variable to be sorted in increasing order.
145 absl::Span<const IntegerVariable> vars);
146
147 // Add a new linear constraint to this LP.
148 // Return false if we prove infeasibility of the global model.
150
151 // Set the coefficient of the variable in the objective. Calling it twice will
152 // overwrite the previous value.
153 void SetObjectiveCoefficient(IntegerVariable ivar, IntegerValue coeff);
154
155 // The main objective variable should be equal to the linear sum of
156 // the arguments passed to SetObjectiveCoefficient().
157 void SetMainObjectiveVariable(IntegerVariable ivar) {
158 objective_cp_ = ivar;
159 objective_cp_is_part_of_lp_ = false;
160 for (const IntegerVariable var : integer_variables_) {
161 if (var == objective_cp_) {
162 objective_cp_is_part_of_lp_ = true;
163 break;
164 }
165 }
166 }
167 IntegerVariable ObjectiveVariable() const { return objective_cp_; }
168
169 // Register a new cut generator with this constraint.
170 void AddCutGenerator(CutGenerator generator);
171
172 // Returns the LP value and reduced cost of a variable in the current
173 // solution. These functions should only be called when HasSolution() is true.
174 //
175 // Note that this solution is always an OPTIMAL solution of an LP above or
176 // at the current decision level. We "erase" it when we backtrack over it.
177 bool HasSolution() const { return lp_solution_is_set_; }
178 double GetSolutionValue(IntegerVariable variable) const;
179 bool SolutionIsInteger() const { return lp_solution_is_integer_; }
180
181 // Returns a valid lp lower bound for the current branch, and indicates if
182 // the latest LP solve in that branch was solved to optimality or not.
183 // During normal operation, we will always propagate the LP, so this should
184 // not refer to an optimality status lower in that branch.
185 bool AtOptimal() const { return lp_at_optimal_; }
186 double ObjectiveLpLowerBound() const { return lp_objective_lower_bound_; }
187
188 // PropagatorInterface API.
189 bool Propagate() override;
190 bool IncrementalPropagate(const std::vector<int>& watch_indices) override;
191 void RegisterWith(Model* model);
192
193 // ReversibleInterface API.
194 void SetLevel(int level) override;
195
196 // From outside, the lp should be seen as containing all extended variables.
197 int NumVariables() const {
198 return static_cast<int>(extended_integer_variables_.size());
199 }
200 const std::vector<IntegerVariable>& integer_variables() const {
201 return extended_integer_variables_;
202 }
203
204 std::string DimensionString() const;
205
206 // Returns a IntegerLiteral guided by the underlying LP constraints.
207 //
208 // This computes the mean of reduced costs over successive calls,
209 // and tries to fix the variable which has the highest reduced cost.
210 // Tie-breaking is done using the variable natural order.
212
213 // Average number of nonbasic variables with zero reduced costs.
214 double average_degeneracy() const {
215 return average_degeneracy_.CurrentAverage();
216 }
217
218 // Stats.
220 return total_num_simplex_iterations_;
221 }
223 return total_num_cut_propagations_;
224 }
226 return total_num_eq_propagations_;
227 }
228 int64_t num_solves() const { return num_solves_; }
229 int64_t num_adjusts() const { return num_adjusts_; }
230 int64_t num_cut_overflows() const { return num_cut_overflows_; }
231 int64_t num_bad_cuts() const { return num_bad_cuts_; }
232 int64_t num_scaling_issues() const { return num_scaling_issues_; }
233
234 // This can serve as a timestamp to know if a saved basis is out of date.
235 int64_t num_lp_changes() const { return num_lp_changes_; }
236
237 const std::vector<int64_t>& num_solves_by_status() const {
238 return num_solves_by_status_;
239 }
240
242 return constraint_manager_;
243 }
244
245 // Important: this is only temporarily valid.
247 if (optimal_constraints_.empty()) return nullptr;
248 return optimal_constraints_.back().get();
249 }
250
251 const std::vector<std::unique_ptr<IntegerSumLE128>>& OptimalConstraints()
252 const {
253 return optimal_constraints_;
254 }
255
256 // This api allows to temporarily disable the LP propagator which can be
257 // costly during probing or other heavy propagation phase.
258 void EnablePropagation(bool enable) {
259 enabled_ = enable;
260 watcher_->CallOnNextPropagate(watcher_id_);
261 }
262 bool PropagationIsEnabled() const { return enabled_; }
263
264 const glop::BasisState& GetBasisState() const { return state_; }
265 void LoadBasisState(const glop::BasisState& state) {
266 state_ = state;
267 simplex_.LoadStateForNextSolve(state_);
268 }
269
270 private:
271 // Helper method to fill reduced cost / dual ray reason in 'integer_reason'.
272 // Generates a set of IntegerLiterals explaining why the best solution can not
273 // be improved using reduced costs. This is used to generate explanations for
274 // both infeasibility and bounds deductions.
275 void FillReducedCostReasonIn(const glop::DenseRow& reduced_costs,
276 std::vector<IntegerLiteral>* integer_reason);
277
278 // Reinitialize the LP from a potentially new set of constraints.
279 // This fills all data structure and properly rescale the underlying LP.
280 //
281 // Returns false if the problem is UNSAT (it can happen when presolve is off
282 // and some LP constraint are trivially false).
283 bool CreateLpFromConstraintManager();
284
285 // Solve the LP, returns false if something went wrong in the LP solver.
286 bool SolveLp();
287
288 // Analyzes the result of an LP Solution. Returns false on conflict.
289 bool AnalyzeLp();
290
291 // Does some basic preprocessing of a cut candidate. Returns false if we
292 // should abort processing this candidate.
293 bool PreprocessCut(IntegerVariable first_slack, CutData* cut);
294
295 // Add a "MIR" cut obtained by first taking the linear combination of the
296 // row of the matrix according to "integer_multipliers" and then trying
297 // some integer rounding heuristic.
298 //
299 // Return true if a new cut was added to the cut manager.
300 bool AddCutFromConstraints(
301 absl::string_view name,
302 absl::Span<const std::pair<glop::RowIndex, IntegerValue>>
303 integer_multipliers);
304
305 // Second half of AddCutFromConstraints().
306 bool PostprocessAndAddCut(const std::string& name, const std::string& info,
307 IntegerVariable first_slack, const CutData& cut);
308
309 // Computes and adds the corresponding type of cuts.
310 // This can currently only be called at the root node.
311 void AddObjectiveCut();
312 void AddCGCuts();
313 void AddMirCuts();
314 void AddZeroHalfCuts();
315
316 // Updates the bounds of the LP variables from the CP bounds.
317 void UpdateBoundsOfLpVariables();
318
319 // Use the dual optimal lp values to compute an EXACT lower bound on the
320 // objective. Fills its reason and perform reduced cost strenghtening.
321 // Returns false in case of conflict.
322 bool PropagateExactLpReason();
323
324 // Same as FillDualRayReason() but perform the computation EXACTLY. Returns
325 // false in the case that the problem is not provably infeasible with exact
326 // computations, true otherwise.
327 bool PropagateExactDualRay();
328
329 // Called by PropagateExactLpReason() and PropagateExactDualRay() to finish
330 // propagation.
331 bool PropagateLpConstraint(LinearConstraint ct);
332
333 // Returns number of non basic variables with zero reduced costs.
334 int64_t CalculateDegeneracy();
335
336 // From a set of row multipliers (at LP scale), scale them back to the CP
337 // world and then make them integer (eventually multiplying them by a new
338 // scaling factor returned in *scaling).
339 //
340 // Note that this will loose some precision, but our subsequent computation
341 // will still be exact as it will work for any set of multiplier.
342 void IgnoreTrivialConstraintMultipliers(
343 std::vector<std::pair<glop::RowIndex, double>>* lp_multipliers);
344 void ScaleMultipliers(
345 absl::Span<const std::pair<glop::RowIndex, double>> lp_multipliers,
346 bool take_objective_into_account, IntegerValue* scaling,
347 std::vector<std::pair<glop::RowIndex, IntegerValue>>* output) const;
348
349 // Can we have an overflow if we scale each coefficients with
350 // std::round(std::ldexp(coeff, power)) ?
351 bool ScalingCanOverflow(
352 int power, bool take_objective_into_account,
353 absl::Span<const std::pair<glop::RowIndex, double>> multipliers,
354 int64_t overflow_cap) const;
355
356 // Computes from an integer linear combination of the integer rows of the LP a
357 // new constraint of the form "sum terms <= upper_bound". All computation are
358 // exact here.
359 //
360 // Returns false if we encountered any integer overflow. If the template bool
361 // is false, we do not check for a bit of extra speed.
362 template <bool check_overflow = true>
363 bool ComputeNewLinearConstraint(
364 absl::Span<const std::pair<glop::RowIndex, IntegerValue>>
365 integer_multipliers,
366 ScatteredIntegerVector* scattered_vector,
367 IntegerValue* upper_bound) const;
368
369 // Simple heuristic to try to minimize |upper_bound - ImpliedLB(terms)|. This
370 // should make the new constraint tighter and correct a bit the imprecision
371 // introduced by rounding the floating points values.
372 void AdjustNewLinearConstraint(
373 std::vector<std::pair<glop::RowIndex, IntegerValue>>* integer_multipliers,
374 ScatteredIntegerVector* scattered_vector,
375 IntegerValue* upper_bound) const;
376
377 // Shortcut for an integer linear expression type.
378 using LinearExpression = std::vector<std::pair<glop::ColIndex, IntegerValue>>;
379
380 // Converts a dense representation of a linear constraint to a sparse one
381 // expressed in terms of IntegerVariable.
382 void ConvertToLinearConstraint(
384 dense_vector,
385 IntegerValue upper_bound, LinearConstraint* result);
386
387 // Compute the implied lower bound of the given linear expression using the
388 // current variable bound.
389 absl::int128 GetImpliedLowerBound(const LinearConstraint& terms) const;
390
391 // Fills the deductions vector with reduced cost deductions that can be made
392 // from the current state of the LP solver. The given delta should be the
393 // difference between the cp objective upper bound and lower bound given by
394 // the lp.
395 void ReducedCostStrengtheningDeductions(double cp_objective_delta);
396
397 // Returns the variable value on the same scale as the CP variable value.
398 glop::Fractional GetVariableValueAtCpScale(glop::ColIndex var);
399
400 // Gets an LP variable that mirrors a CP variable.
401 // The variable should be a positive reference.
402 glop::ColIndex GetMirrorVariable(IntegerVariable positive_variable);
403
404 // This must be called on an OPTIMAL LP and will update the data for
405 // LPReducedCostAverageDecision().
406 void UpdateAverageReducedCosts();
407
408 // Callback underlying LPReducedCostAverageBranching().
409 IntegerLiteral LPReducedCostAverageDecision();
410
411 // Updates the simplex iteration limit for the next visit.
412 // As per current algorithm, we use a limit which is dependent on size of the
413 // problem and drop it significantly if degeneracy is detected. We use
414 // DUAL_FEASIBLE status as a signal to correct the prediction. The next limit
415 // is capped by 'min_iter' and 'max_iter'. Note that this is enabled only for
416 // linearization level 2 and above.
417 void UpdateSimplexIterationLimit(int64_t min_iter, int64_t max_iter);
418
419 // Returns the col/coeff of integer_lp_[row].
420 absl::Span<const glop::ColIndex> IntegerLpRowCols(glop::RowIndex row) const;
421 absl::Span<const IntegerValue> IntegerLpRowCoeffs(glop::RowIndex row) const;
422
423 void ComputeIntegerLpScalingFactors();
424 void FillLpData();
425
426 // For ComputeIntegerLpScalingFactors().
427 std::vector<double> row_factors_;
428 std::vector<double> col_factors_;
429 std::vector<double> col_max_;
430 std::vector<double> col_min_;
431
432 // This epsilon is related to the precision of the value/reduced_cost returned
433 // by the LP once they have been scaled back into the CP domain. So for large
434 // domain or cost coefficient, we may have some issues.
435 static constexpr double kCpEpsilon = 1e-4;
436
437 // Same but at the LP scale.
438 static constexpr double kLpEpsilon = 1e-6;
439
440 // Anything coming from the LP with a magnitude below that will be assumed to
441 // be zero.
442 static constexpr double kZeroTolerance = 1e-12;
443
444 // Class responsible for managing all possible constraints that may be part
445 // of the LP.
446 LinearConstraintManager constraint_manager_;
447
448 // We do not want to add too many cut during each generation round.
449 TopNCuts top_n_cuts_ = TopNCuts(10);
450
451 // Initial problem in integer form.
452 // We always sort the inner vectors by increasing glop::ColIndex.
453 struct LinearConstraintInternal {
454 IntegerValue lb;
455 IntegerValue ub;
456
457 // Point in integer_lp_cols_/integer_lp_coeffs_ for the actual data.
458 int start_in_buffer;
459 int num_terms;
460
461 bool lb_is_trivial = false;
462 bool ub_is_trivial = false;
463 };
464 std::vector<glop::ColIndex> integer_lp_cols_;
465 std::vector<IntegerValue> integer_lp_coeffs_;
466
467 std::vector<glop::ColIndex> tmp_cols_;
468 std::vector<IntegerValue> tmp_coeffs_;
469 std::vector<IntegerVariable> tmp_vars_;
470
471 LinearExpression integer_objective_;
472 IntegerValue integer_objective_offset_ = IntegerValue(0);
473 IntegerValue objective_infinity_norm_ = IntegerValue(0);
475 integer_lp_;
477
478 // Underlying LP solver API.
479 glop::GlopParameters simplex_params_;
480 glop::BasisState state_;
481 glop::DenseRow obj_with_slack_;
482 glop::RevisedSimplex simplex_;
483
484 int64_t next_simplex_iter_ = 500;
485
486 // For the scaling.
487 glop::LpScalingHelper scaler_;
488
489 // Temporary data for cuts.
490 ZeroHalfCutHelper zero_half_cut_helper_;
491 CoverCutHelper cover_cut_helper_;
492 IntegerRoundingCutHelper integer_rounding_cut_helper_;
493
494 bool problem_proven_infeasible_by_cuts_ = false;
495 CutData base_ct_;
496
497 ScatteredIntegerVector tmp_scattered_vector_;
498
499 std::vector<double> tmp_lp_values_;
500 std::vector<IntegerValue> tmp_var_lbs_;
501 std::vector<IntegerValue> tmp_var_ubs_;
502 std::vector<glop::RowIndex> tmp_slack_rows_;
503 std::vector<std::pair<glop::ColIndex, IntegerValue>> tmp_terms_;
504
505 // Used by ScaleMultipliers().
506 std::vector<std::pair<glop::RowIndex, double>> tmp_lp_multipliers_;
507 std::vector<std::pair<glop::RowIndex, double>> tmp_cg_multipliers_;
508 std::vector<std::pair<glop::RowIndex, IntegerValue>> tmp_integer_multipliers_;
509
510 // Structures used for mirroring IntegerVariables inside the underlying LP
511 // solver: an integer variable var is mirrored by mirror_lp_variable_[var].
512 // Note that these indices are dense in [0, integer_variables.size()] so
513 // they can be used as vector indices.
514 std::vector<IntegerVariable> integer_variables_;
515 std::vector<IntegerVariable> extended_integer_variables_;
516
517 // This is only used if we use symmetry folding.
518 // Refer to relevant orbit in the LinearConstraintSymmetrizer.
519 std::vector<int> orbit_indices_;
520
521 // We need to remember what to optimize if an objective is given, because
522 // then we will switch the objective between feasibility and optimization.
523 bool objective_is_defined_ = false;
524 bool objective_cp_is_part_of_lp_ = false;
525 IntegerVariable objective_cp_;
526
527 // Singletons from Model.
528 //
529 // TODO(user): ObjectiveDefinition and SharedResponseManager are only needed
530 // to report the objective bounds during propagation, find a better way to
531 // avoid some of these dependencies?
532 const SatParameters& parameters_;
533 Model* model_;
534 TimeLimit* time_limit_;
535 IntegerTrail* integer_trail_;
536 Trail* trail_;
537 GenericLiteralWatcher* watcher_;
538 IntegerEncoder* integer_encoder_;
539 ProductDetector* product_detector_;
540 ObjectiveDefinition* objective_definition_;
541 SharedStatistics* shared_stats_;
542 SharedResponseManager* shared_response_manager_;
543 ModelRandomGenerator* random_;
544 LinearConstraintSymmetrizer* symmetrizer_;
545 LinearPropagator* linear_propagator_;
546
547 int watcher_id_;
548
549 BoolRLTCutHelper rlt_cut_helper_;
550
551 // Used while deriving cuts.
552 ImpliedBoundsProcessor implied_bounds_processor_;
553
554 // The dispatcher for all LP propagators of the model, allows to find which
555 // LinearProgrammingConstraint has a given IntegerVariable.
556 LinearProgrammingDispatcher* dispatcher_;
557
558 std::vector<IntegerLiteral> integer_reason_;
559 std::vector<IntegerLiteral> deductions_;
560 std::vector<IntegerLiteral> deductions_reason_;
561
562 // Repository of IntegerSumLE128 that needs to be kept around for the lazy
563 // reasons. Those are new integer constraint that are created each time we
564 // solve the LP to a dual-feasible solution. Propagating these constraints
565 // both improve the objective lower bound but also perform reduced cost
566 // fixing.
567 int rev_optimal_constraints_size_ = 0;
568 std::vector<std::unique_ptr<IntegerSumLE128>> optimal_constraints_;
569 std::vector<int64_t> cumulative_optimal_constraint_sizes_;
570
571 // Last OPTIMAL solution found by a call to the underlying LP solver.
572 // On IncrementalPropagate(), if the bound updates do not invalidate this
573 // solution, Propagate() will not find domain reductions, no need to call it.
574 int lp_solution_level_ = 0;
575 bool lp_solution_is_set_ = false;
576 bool lp_solution_is_integer_ = false;
577 std::vector<double> lp_solution_;
578 std::vector<double> lp_reduced_cost_;
579
580 // Last objective lower bound found by the LP Solver.
581 // We erase this on backtrack.
582 int previous_level_ = 0;
583 bool lp_at_optimal_ = false;
584 double lp_objective_lower_bound_;
585
586 // If non-empty, this is the last known optimal lp solution at root-node. If
587 // the variable bounds changed, or cuts where added, it is possible that this
588 // solution is no longer optimal though.
589 std::vector<double> level_zero_lp_solution_;
590
591 // True if the last time we solved the exact same LP at level zero, no cuts
592 // and no lazy constraints where added.
593 bool lp_at_level_zero_is_final_ = false;
594
595 // Same as lp_solution_ but this vector is indexed by IntegerVariable.
596 ModelLpVariableMapping& mirror_lp_variable_;
597 ModelLpValues& expanded_lp_solution_;
598 ModelReducedCosts& expanded_reduced_costs_;
599
600 // Linear constraints cannot be created or modified after this is registered.
601 bool lp_constraint_is_registered_ = false;
602
603 std::vector<CutGenerator> cut_generators_;
604
605 // Store some statistics for HeuristicLPReducedCostAverage().
606 bool compute_reduced_cost_averages_ = false;
607 int num_calls_since_reduced_cost_averages_reset_ = 0;
608 std::vector<double> sum_cost_up_;
609 std::vector<double> sum_cost_down_;
610 std::vector<int> num_cost_up_;
611 std::vector<int> num_cost_down_;
612 std::vector<double> rc_scores_;
613
614 // All the entries before rev_rc_start_ in the sorted positions correspond
615 // to fixed variables and can be ignored.
616 int rev_rc_start_ = 0;
617 RevRepository<int> rc_rev_int_repository_;
618 std::vector<std::pair<double, int>> positions_by_decreasing_rc_score_;
619
620 // Defined as average number of nonbasic variables with zero reduced costs.
621 IncrementalAverage average_degeneracy_;
622 bool is_degenerate_ = false;
623
624 // Sum of all simplex iterations performed by this class. This is useful to
625 // test the incrementality and compare to other solvers.
626 int64_t total_num_simplex_iterations_ = 0;
627
628 // As we form candidate form cuts, sometimes we can propagate level zero
629 // bounds with them.
630 FirstFewValues<10> reachable_;
631 int64_t total_num_cut_propagations_ = 0;
632 int64_t total_num_eq_propagations_ = 0;
633
634 // The number of times we changed the LP.
635 int64_t num_lp_changes_ = 0;
636
637 // Some stats on the LP statuses encountered.
638 int64_t num_solves_ = 0;
639 mutable int64_t num_adjusts_ = 0;
640 mutable int64_t num_cut_overflows_ = 0;
641 mutable int64_t num_bad_cuts_ = 0;
642 mutable int64_t num_scaling_issues_ = 0;
643 std::vector<int64_t> num_solves_by_status_;
644
645 // We might temporarily disable the LP propagation.
646 bool enabled_ = true;
647};
648
649// A class that stores which LP propagator is associated to each variable.
650// We need to give the hash_map a name so it can be used as a singleton in our
651// model.
652//
653// Important: only positive variable do appear here.
655 : public absl::flat_hash_map<IntegerVariable,
656 LinearProgrammingConstraint*> {};
657
658// A class that stores the collection of all LP constraints in a model.
660 : public std::vector<LinearProgrammingConstraint*> {
661 public:
664};
665
666} // namespace sat
667} // namespace operations_research
668
669#endif // OR_TOOLS_SAT_LINEAR_PROGRAMMING_CONSTRAINT_H_
Definition model.h:341
Entry point of the revised simplex algorithm implementation.
int64_t num_lp_changes() const
This can serve as a timestamp to know if a saved basis is out of date.
const std::vector< std::unique_ptr< IntegerSumLE128 > > & OptimalConstraints() const
IntegerSumLE128 * LatestOptimalConstraintOrNull() const
Important: this is only temporarily valid.
void SetLevel(int level) override
ReversibleInterface API.
void AddCutGenerator(CutGenerator generator)
Register a new cut generator with this constraint.
void SetObjectiveCoefficient(IntegerVariable ivar, IntegerValue coeff)
bool IncrementalPropagate(const std::vector< int > &watch_indices) override
LinearProgrammingConstraint(Model *model, absl::Span< const IntegerVariable > vars)
int NumVariables() const
From outside, the lp should be seen as containing all extended variables.
const std::vector< IntegerVariable > & integer_variables() const
double average_degeneracy() const
Average number of nonbasic variables with zero reduced costs.
bool Add(glop::ColIndex col, IntegerValue value)
Does vector[col] += value and return false in case of overflow.
LinearConstraint ConvertToLinearConstraint(absl::Span< const IntegerVariable > integer_variables, IntegerValue upper_bound, std::optional< std::pair< IntegerVariable, IntegerValue > > extra_term=std::nullopt)
void ConvertToCutData(absl::int128 rhs, absl::Span< const IntegerVariable > integer_variables, absl::Span< const double > lp_solution, IntegerTrail *integer_trail, CutData *result)
std::vector< std::pair< glop::ColIndex, IntegerValue > > GetTerms()
Similar to ConvertToLinearConstraint().
bool AddLinearExpressionMultiple(IntegerValue multiplier, absl::Span< const glop::ColIndex > cols, absl::Span< const IntegerValue > coeffs, IntegerValue max_coeff_magnitude)
Force instantations for tests.
IntegerValue operator[](glop::ColIndex col) const
We only provide the const [].
StrictITIVector< ColIndex, Fractional > DenseRow
Row-vector types. Row-vector types are indexed by a column index.
Definition lp_types.h:351
LinearConstraintPropagator< true > IntegerSumLE128
In SWIG mode, we don't want anything besides these top-level includes.
STL namespace.
Our cut are always of the form linear_expression <= rhs.
Definition cuts.h:116