Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
Classes | Public Member Functions | List of all members
operations_research::sat::PseudoCosts Class Reference

#include <pseudo_costs.h>

Classes

struct  BranchingInfo
 
struct  VariableBoundChange
 

Public Member Functions

 PseudoCosts (Model *model)
 
void BeforeTakingDecision (Literal decision)
 
void AfterTakingDecision (bool conflict=false)
 
double ObjectiveIncrease (bool conflict)
 
bool SaveLpInfo ()
 
void SaveBoundChanges (Literal decision, absl::Span< const double > lp_values)
 
IntegerVariable GetBestDecisionVar ()
 Returns the variable with best reliable pseudo cost that is not fixed.
 
double GetCost (IntegerVariable var) const
 Returns the pseudo cost of given variable. Currently used for testing only.
 
int GetNumRecords (IntegerVariable var) const
 
double CombineScores (double down_branch, double up_branch) const
 Combines the score of the two branch into one score.
 
BranchingInfo EvaluateVar (IntegerVariable var, absl::Span< const double > lp_values)
 
void UpdateBoolPseudoCosts (absl::Span< const Literal > reason, IntegerValue objective_increase)
 
double BoolPseudoCost (Literal lit, double lp_value) const
 
std::vector< VariableBoundChange > GetBoundChanges (Literal decision, absl::Span< const double > lp_values)
 

Detailed Description

Pseudo cost of a variable is measured as average observed change in the objective bounds per unit change in the variable bounds.

Definition at line 37 of file pseudo_costs.h.

Constructor & Destructor Documentation

◆ PseudoCosts()

operations_research::sat::PseudoCosts::PseudoCosts ( Model * model)
explicit

If objective_var == kNoIntegerVariable, there is not really any point using this class.

Definition at line 59 of file pseudo_costs.cc.

Member Function Documentation

◆ AfterTakingDecision()

void operations_research::sat::PseudoCosts::AfterTakingDecision ( bool conflict = false)

Updates the pseudo costs for the given decision given to BeforeTakingDecision().

We store a pseudo cost for this literal. We prefer the pure LP version, but revert to integer version if there is no lp.

Todo
(user): tune that.

We only collect lp increase when the lp is at optimal, otherwise it might just be the "artificial" continuing of the current lp solve that create the increase.

Update the average unit increases.

Todo
(user): Handle this case.

We also store one for any associated IntegerVariable.

Create space for new variable and its negation.

Definition at line 196 of file pseudo_costs.cc.

◆ BeforeTakingDecision()

void operations_research::sat::PseudoCosts::BeforeTakingDecision ( Literal decision)

This must be called before we are about to branch. It will record the current objective bounds.

Definition at line 106 of file pseudo_costs.cc.

◆ BoolPseudoCost()

double operations_research::sat::PseudoCosts::BoolPseudoCost ( Literal lit,
double lp_value ) const

Definition at line 168 of file pseudo_costs.cc.

◆ CombineScores()

double operations_research::sat::PseudoCosts::CombineScores ( double down_branch,
double up_branch ) const

Combines the score of the two branch into one score.

We prefer the product to combine the cost of two branches.

Definition at line 44 of file pseudo_costs.cc.

◆ EvaluateVar()

PseudoCosts::BranchingInfo operations_research::sat::PseudoCosts::EvaluateVar ( IntegerVariable var,
absl::Span< const double > lp_values )

Definition at line 112 of file pseudo_costs.cc.

◆ GetBestDecisionVar()

IntegerVariable operations_research::sat::PseudoCosts::GetBestDecisionVar ( )

Returns the variable with best reliable pseudo cost that is not fixed.

Todo

(user): Supports search randomization tolerance.

(user): Implement generic class to choose the randomized solution, and supports sub-linear variable selection.

Todo
(user): Avoid the O(num_relevant_variable) loop. In practice since a variable only become relevant after 100 records, this list might be small compared to the number of variable though.

Pick the direction with best pseudo cost.

Definition at line 259 of file pseudo_costs.cc.

◆ GetBoundChanges()

std::vector< PseudoCosts::VariableBoundChange > operations_research::sat::PseudoCosts::GetBoundChanges ( Literal decision,
absl::Span< const double > lp_values )
Note
We ignore literal associated to var != value.

Also do the negation.

Definition at line 284 of file pseudo_costs.cc.

◆ GetCost()

double operations_research::sat::PseudoCosts::GetCost ( IntegerVariable var) const
inline

Returns the pseudo cost of given variable. Currently used for testing only.

Definition at line 59 of file pseudo_costs.h.

◆ GetNumRecords()

int operations_research::sat::PseudoCosts::GetNumRecords ( IntegerVariable var) const
inline

Visible for testing. Returns the number of recordings of given variable.

Definition at line 66 of file pseudo_costs.h.

◆ ObjectiveIncrease()

double operations_research::sat::PseudoCosts::ObjectiveIncrease ( bool conflict)

Advanced usage. Internal functions used by Before/AfterTakingDecision(), that are exposed for strong branching.

We count a conflict as a max increase + 1.0

Definition at line 181 of file pseudo_costs.cc.

◆ SaveBoundChanges()

void operations_research::sat::PseudoCosts::SaveBoundChanges ( Literal decision,
absl::Span< const double > lp_values )

Definition at line 101 of file pseudo_costs.cc.

◆ SaveLpInfo()

bool operations_research::sat::PseudoCosts::SaveLpInfo ( )

Definition at line 96 of file pseudo_costs.cc.

◆ UpdateBoolPseudoCosts()

void operations_research::sat::PseudoCosts::UpdateBoolPseudoCosts ( absl::Span< const Literal > reason,
IntegerValue objective_increase )

Experimental alternative pseudo cost based on the explanation for bound increases.

Definition at line 156 of file pseudo_costs.cc.

The documentation for this class was generated from the following files: