#include <feasibility_jump.h>

Public Attributes
std::vector< int64_t >	solution

std::vector< double >	weights

double	bump_value = 1.0

int	compound_move_max_discrepancy = 0

std::vector< double >	compound_weights

std::vector< bool >	in_compound_weight_changed

std::vector< int >	compound_weight_changed

std::unique_ptr< CompoundMoveBuilder >	move

LsCounters	counters
	Counters for a "non-restarted" run.

LsOptions	options
	Strategy.

int64_t	num_restarts = 0
	Global counters, incremented across restart.

int64_t	num_solutions_imported = 0

int64_t	num_batches_before_change = 0
	When this reach zero, we restart / perturbate or trigger something.

int64_t	last_solution_rank = std::numeric_limits<int64_t>::max()
	Used by LS to know the rank of the starting solution for this state.

IntegerValue	saved_inner_objective_lb = 0

IntegerValue	saved_inner_objective_ub = 0

Detailed Description

Each FeasibilityJumpSolver work on many LsState in an interleaved parallel fashion. Each "batch of moves" will update one of these state. Restart heuristic are also on a per state basis.

This allows to not use O(problem size) per state while having a more diverse set of heuristics.

Definition at line 302 of file feasibility_jump.h.

Member Data Documentation

◆ bump_value

double operations_research::sat::LsState::bump_value = 1.0

Depending on the options, we use an exponentially decaying constraint weight like for SAT activities.

Definition at line 310 of file feasibility_jump.h.

◆ compound_move_max_discrepancy

int operations_research::sat::LsState::compound_move_max_discrepancy = 0

If using compound moves, these will be discounted on a new incumbent then re-converge to weights after some exploration. Search will repeatedly pick moves with negative WeightedViolationDelta using these weights.

We limit the discrepancy in compound move search (i.e. limit the number of backtracks to any ancestor of the current leaf). This is set to 0 whenever a new incumbent is found or weights are updated, and increased at fixed point. Weights are only increased if no moves are found with discrepancy 2. Empirically we have seen very few moves applied with discrepancy > 2.

Definition at line 321 of file feasibility_jump.h.

◆ compound_weight_changed

std::vector<int> operations_research::sat::LsState::compound_weight_changed

Definition at line 324 of file feasibility_jump.h.

◆ compound_weights

std::vector<double> operations_research::sat::LsState::compound_weights

Definition at line 322 of file feasibility_jump.h.

◆ counters

LsCounters operations_research::sat::LsState::counters

Counters for a "non-restarted" run.

Definition at line 328 of file feasibility_jump.h.

◆ in_compound_weight_changed

std::vector<bool> operations_research::sat::LsState::in_compound_weight_changed

Definition at line 323 of file feasibility_jump.h.

◆ last_solution_rank

int64_t operations_research::sat::LsState::last_solution_rank = std::numeric_limits<int64_t>::max()

Used by LS to know the rank of the starting solution for this state.

Definition at line 341 of file feasibility_jump.h.

◆ move

std::unique_ptr<CompoundMoveBuilder> operations_research::sat::LsState::move

Definition at line 325 of file feasibility_jump.h.

◆ num_batches_before_change

int64_t operations_research::sat::LsState::num_batches_before_change = 0

When this reach zero, we restart / perturbate or trigger something.

Definition at line 338 of file feasibility_jump.h.

◆ num_restarts

int64_t operations_research::sat::LsState::num_restarts = 0

Global counters, incremented across restart.

Definition at line 334 of file feasibility_jump.h.

◆ num_solutions_imported

int64_t operations_research::sat::LsState::num_solutions_imported = 0

Definition at line 335 of file feasibility_jump.h.

◆ options

LsOptions operations_research::sat::LsState::options

Strategy.

Definition at line 331 of file feasibility_jump.h.

◆ saved_inner_objective_lb

IntegerValue operations_research::sat::LsState::saved_inner_objective_lb = 0

Tricky: If this changed since last time, we need to recompute the compound moves as the objective constraint bound changed.

Definition at line 345 of file feasibility_jump.h.

◆ saved_inner_objective_ub

IntegerValue operations_research::sat::LsState::saved_inner_objective_ub = 0

Definition at line 346 of file feasibility_jump.h.

◆ solution

std::vector<int64_t> operations_research::sat::LsState::solution

The score of a solution is just the sum of infeasibility of each constraint weighted by these weights.

Definition at line 305 of file feasibility_jump.h.

◆ weights

std::vector<double> operations_research::sat::LsState::weights

Definition at line 306 of file feasibility_jump.h.

The documentation for this struct was generated from the following file:

ortools/sat/feasibility_jump.h

Public Attributes