operations_research::sat::FeasibilityJumpSolver Class Reference

#include <feasibility_jump.h>

Inheritance diagram for operations_research::sat::FeasibilityJumpSolver:

Public Member Functions
	FeasibilityJumpSolver (const absl::string_view name, SubSolver::SubsolverType type, const LinearModel *linear_model, SatParameters params, std::shared_ptr< SharedLsStates > ls_states, ModelSharedTimeLimit *shared_time_limit, SharedResponseManager *shared_response, SharedBoundsManager *shared_bounds, SharedStatistics *shared_stats, SharedStatTables *stat_tables)
	~FeasibilityJumpSolver () override
	If VLOG_IS_ON(1), it will export a bunch of statistics.
void	Synchronize () final
	No synchronization needed for TaskIsAvailable().
bool	IsDone () final
	Shall we delete this subsolver?
bool	TaskIsAvailable () final
std::function< void()>	GenerateTask (int64_t) final
Public Member Functions inherited from operations_research::sat::SubSolver
	SubSolver (absl::string_view name, SubsolverType type)
virtual	~SubSolver ()=default
double	deterministic_time () const
std::string	name () const
	Returns the name of this SubSolver. Used in logs.
SubsolverType	type () const
	Returns the type of the subsolver.
void	AddTaskDuration (double duration_in_seconds)
void	AddTaskDeterministicDuration (double deterministic_duration)
std::string	TimingInfo () const
std::string	DeterministicTimingInfo () const

Additional Inherited Members
Public Types inherited from operations_research::sat::SubSolver
enum	SubsolverType { FULL_PROBLEM , FIRST_SOLUTION , INCOMPLETE , HELPER }

Detailed Description

Implements and heuristic similar to the one described in the paper: "Feasibility Jump: an LP-free Lagrangian MIP heuristic", Bjørnar Luteberget, Giorgio Sartor, 2023, Mathematical Programming Computation.

This is basically a Guided local search (GLS) with a nice algo to know what value an integer variable should move to (its jump value). For binary, it can only be swapped, so the situation is easier.

Todo

(user): If we have more than one of these solver, we might want to share the evaluator memory between them. Right now we basically keep a copy of the model and its transpose for each FeasibilityJumpSolver.

Definition at line 467 of file feasibility_jump.h.

Constructor & Destructor Documentation

FeasibilityJumpSolver()

operations_research::sat::FeasibilityJumpSolver::FeasibilityJumpSolver ( const absl::string_view name, SubSolver::SubsolverType type, const LinearModel * linear_model, SatParameters params, std::shared_ptr< SharedLsStates > ls_states, ModelSharedTimeLimit * shared_time_limit, SharedResponseManager * shared_response, SharedBoundsManager * shared_bounds, SharedStatistics * shared_stats, SharedStatTables * stat_tables )

inline

Definition at line 469 of file feasibility_jump.h.

~FeasibilityJumpSolver()

operations_research::sat::FeasibilityJumpSolver::~FeasibilityJumpSolver ( )

override

If VLOG_IS_ON(1), it will export a bunch of statistics.

Definition at line 119 of file feasibility_jump.cc.

Member Function Documentation

GenerateTask()

std::function< void()> operations_research::sat::FeasibilityJumpSolver::GenerateTask ( int64_t task_id )

finalvirtual

Returns a task to run. The task_id is just an ever increasing counter that correspond to the number of total calls to GenerateTask().

Todo

(user): We could use a more complex selection logic and pass in the deterministic time limit this subtask should run for. Unclear at this stage.

This is only called by the main thread.

We delay initialization to the first task as it might be a bit slow to scan the whole model, so we want to do this part in parallel.

Load the next state to work on.

If we found a new best solution, we will restart all violation ls (we still finish each batch though). We will also reset the luby sequence.

This is not used once we have a solution, and setting it to false allow to fix the logs.

Choose a base solution for this neighborhood.

Todo

(user): Tune the improvement constant, maybe use luby.

Between chunk, we synchronize bounds.

Update the variable domains with the last information.

Checks the current solution is compatible with updated domains.

Make sure the solution is within the potentially updated domain. This also initialize var_domains_.CanIncrease()/CanDecrease().

Check if compound move search might backtrack out of the new domains.

Search for feasible solution. We always recompute that since we might have loaded from a different state.

Checks for infeasibility induced by the non supported constraints.

Update dtime. Since we execute only one task at the time, this is safe.

Todo

(user): Find better names. DeterministicTime() is maintained by this class while deterministic_time() is the one saved in the SubSolver base class).

Because deterministic_time() is computed with a sum of difference, it might be slighlty different than DeterministicTime() and we don't want to go backward, even by 1e-18.

Implements operations_research::sat::SubSolver.

Definition at line 340 of file feasibility_jump.cc.

IsDone()

bool operations_research::sat::FeasibilityJumpSolver::IsDone ( )

inlinefinalvirtual

Shall we delete this subsolver?

We are done after the first task is done in the FIRST_SOLUTION mode.

Reimplemented from operations_research::sat::SubSolver.

Definition at line 495 of file feasibility_jump.h.

Synchronize()

void operations_research::sat::FeasibilityJumpSolver::Synchronize ( )

inlinefinalvirtual

No synchronization needed for TaskIsAvailable().

Implements operations_research::sat::SubSolver.

Definition at line 492 of file feasibility_jump.h.

TaskIsAvailable()

bool operations_research::sat::FeasibilityJumpSolver::TaskIsAvailable ( )

inlinefinalvirtual

Returns true iff GenerateTask() can be called. This is only called by the main thread in a sequential fashion.

Implements operations_research::sat::SubSolver.

Definition at line 503 of file feasibility_jump.h.

---

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

• ortools/sat/feasibility_jump.h
• ortools/sat/feasibility_jump.cc