14#ifndef OR_TOOLS_SAT_LINEAR_PROGRAMMING_CONSTRAINT_H_
15#define OR_TOOLS_SAT_LINEAR_PROGRAMMING_CONSTRAINT_H_
21#include "absl/container/flat_hash_map.h"
77 IntegerValue multiplier,
78 const std::vector<std::pair<glop::ColIndex, IntegerValue>>& terms);
87 const std::vector<IntegerVariable>& integer_variables,
91 std::vector<std::pair<glop::ColIndex, IntegerValue>>
GetTerms();
95 return dense_vector_[
col];
102 bool is_sparse_ =
true;
103 std::vector<glop::ColIndex> non_zeros_;
127class LinearProgrammingDispatcher;
171 return integer_variables_;
219 return total_num_simplex_iterations_;
225 bool BranchOnVar(IntegerVariable
var);
233 std::vector<IntegerLiteral>* integer_reason);
240 bool CreateLpFromConstraintManager();
250 bool AddCutFromConstraints(
251 const std::string&
name,
252 const std::vector<std::pair<glop::RowIndex, IntegerValue>>&
253 integer_multipliers);
256 bool PostprocessAndAddCut(
257 const std::string&
name,
const std::string& info,
258 IntegerVariable first_new_var, IntegerVariable first_slack,
259 const std::vector<ImpliedBoundsProcessor::SlackInfo>& ib_slack_infos,
266 void AddZeroHalfCuts();
269 void UpdateBoundsOfLpVariables();
274 bool ExactLpReasonning();
279 bool FillExactDualRayReason();
282 int64 CalculateDegeneracy();
290 std::vector<std::pair<glop::RowIndex, IntegerValue>> ScaleLpMultiplier(
291 bool take_objective_into_account,
292 const std::vector<std::pair<glop::RowIndex, double>>& lp_multipliers,
300 bool ComputeNewLinearConstraint(
301 const std::vector<std::pair<glop::RowIndex, IntegerValue>>&
304 IntegerValue* upper_bound)
const;
309 void AdjustNewLinearConstraint(
310 std::vector<std::pair<glop::RowIndex, IntegerValue>>* integer_multipliers,
312 IntegerValue* upper_bound)
const;
315 using LinearExpression = std::vector<std::pair<glop::ColIndex, IntegerValue>>;
319 void ConvertToLinearConstraint(
348 void ReducedCostStrengtheningDeductions(
double cp_objective_delta);
355 glop::ColIndex GetOrCreateMirrorVariable(IntegerVariable positive_variable);
359 void UpdateAverageReducedCosts();
370 void UpdateSimplexIterationLimit(
const int64 min_iter,
const int64 max_iter);
375 static constexpr double kCpEpsilon = 1e-4;
378 static constexpr double kLpEpsilon = 1e-6;
382 static constexpr double kZeroTolerance = 1e-12;
390 struct LinearConstraintInternal {
395 LinearExpression integer_objective_;
396 IntegerValue integer_objective_offset_ = IntegerValue(0);
397 IntegerValue objective_infinity_norm_ = IntegerValue(0);
404 int64 next_simplex_iter_ = 500;
410 ZeroHalfCutHelper zero_half_cut_helper_;
411 CoverCutHelper cover_cut_helper_;
412 IntegerRoundingCutHelper integer_rounding_cut_helper_;
413 LinearConstraint cut_;
415 ScatteredIntegerVector tmp_scattered_vector_;
417 std::vector<double> tmp_lp_values_;
418 std::vector<IntegerValue> tmp_var_lbs_;
419 std::vector<IntegerValue> tmp_var_ubs_;
420 std::vector<glop::RowIndex> tmp_slack_rows_;
421 std::vector<IntegerValue> tmp_slack_bounds_;
424 mutable std::vector<std::pair<glop::RowIndex, double>> tmp_cp_multipliers_;
433 std::vector<IntegerVariable> integer_variables_;
434 absl::flat_hash_map<IntegerVariable, glop::ColIndex> mirror_lp_variable_;
438 bool objective_is_defined_ =
false;
439 IntegerVariable objective_cp_;
442 const SatParameters& sat_parameters_;
445 IntegerTrail* integer_trail_;
447 IntegerEncoder* integer_encoder_;
448 ModelRandomGenerator* random_;
451 ImpliedBoundsProcessor implied_bounds_processor_;
455 LinearProgrammingDispatcher* dispatcher_;
457 std::vector<IntegerLiteral> integer_reason_;
458 std::vector<IntegerLiteral> deductions_;
459 std::vector<IntegerLiteral> deductions_reason_;
466 int rev_optimal_constraints_size_ = 0;
467 std::vector<std::unique_ptr<IntegerSumLE>> optimal_constraints_;
472 int lp_solution_level_ = 0;
473 bool lp_solution_is_set_ =
false;
474 bool lp_solution_is_integer_ =
false;
475 double lp_objective_;
476 std::vector<double> lp_solution_;
477 std::vector<double> lp_reduced_cost_;
482 std::vector<double> level_zero_lp_solution_;
486 bool lp_at_level_zero_is_final_ =
false;
489 LinearProgrammingConstraintLpSolution& expanded_lp_solution_;
492 bool lp_constraint_is_registered_ =
false;
494 std::vector<CutGenerator> cut_generators_;
497 bool compute_reduced_cost_averages_ =
false;
498 int num_calls_since_reduced_cost_averages_reset_ = 0;
499 std::vector<double> sum_cost_up_;
500 std::vector<double> sum_cost_down_;
501 std::vector<int> num_cost_up_;
502 std::vector<int> num_cost_down_;
503 std::vector<double> rc_scores_;
507 int rev_rc_start_ = 0;
509 std::vector<std::pair<double, int>> positions_by_decreasing_rc_score_;
512 IncrementalAverage average_degeneracy_;
513 bool is_degenerate_ =
false;
516 int branching_frequency_ = 1;
517 int64 count_since_last_branching_ = 0;
521 int64 total_num_simplex_iterations_ = 0;
524 std::vector<int64> num_solves_by_status_;
533 :
public absl::flat_hash_map<IntegerVariable,
534 LinearProgrammingConstraint*> {
541 :
public std::vector<LinearProgrammingConstraint*> {
554 int num_nodes,
const std::vector<int>& tails,
const std::vector<int>& heads,
555 const std::vector<Literal>& literals, Model*
model);
562 const std::vector<int>& tails,
563 const std::vector<int>& heads,
564 const std::vector<Literal>& literals,
565 const std::vector<int64>& demands,
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
std::string GetDimensionString() const
double CurrentAverage() const
LinearProgrammingConstraintCollection()
bool Propagate() override
double average_degeneracy() const
std::string DimensionString() const
double SolutionObjectiveValue() const
double GetSolutionValue(IntegerVariable variable) const
void RegisterWith(Model *model)
glop::RowIndex ConstraintIndex
std::function< IntegerLiteral()> HeuristicLpReducedCostAverageBranching()
bool SolutionIsInteger() const
int64 total_num_simplex_iterations() const
LinearProgrammingConstraint(Model *model)
std::function< IntegerLiteral()> HeuristicLpReducedCostBinary(Model *model)
~LinearProgrammingConstraint() override
void AddLinearConstraint(const LinearConstraint &ct)
bool IncrementalPropagate(const std::vector< int > &watch_indices) override
void SetLevel(int level) override
std::function< IntegerLiteral()> HeuristicLpMostInfeasibleBinary(Model *model)
const std::vector< IntegerVariable > & integer_variables() const
void SetMainObjectiveVariable(IntegerVariable ivar)
void SetObjectiveCoefficient(IntegerVariable ivar, IntegerValue coeff)
double GetSolutionReducedCost(IntegerVariable variable) const
void AddCutGenerator(CutGenerator generator)
LinearProgrammingDispatcher(Model *model)
Class that owns everything related to a particular optimization model.
void ConvertToLinearConstraint(const std::vector< IntegerVariable > &integer_variables, IntegerValue upper_bound, LinearConstraint *result)
bool Add(glop::ColIndex col, IntegerValue value)
bool AddLinearExpressionMultiple(IntegerValue multiplier, const std::vector< std::pair< glop::ColIndex, IntegerValue > > &terms)
void ClearAndResize(int size)
IntegerValue operator[](glop::ColIndex col) const
std::vector< std::pair< glop::ColIndex, IntegerValue > > GetTerms()
constexpr IntegerValue kMinIntegerValue(-kMaxIntegerValue)
CutGenerator CreateCVRPCutGenerator(int num_nodes, const std::vector< int > &tails, const std::vector< int > &heads, const std::vector< Literal > &literals, const std::vector< int64 > &demands, int64 capacity, Model *model)
CutGenerator CreateStronglyConnectedGraphCutGenerator(int num_nodes, const std::vector< int > &tails, const std::vector< int > &heads, const std::vector< Literal > &literals, Model *model)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
glop::ProblemStatus status
IntegerValue new_obj_bound
LinearProgrammingConstraintLpSolution()