operations_research::bop::BopRandomFirstSolutionGenerator Class Reference

#include <bop_fs.h>

Inheritance diagram for operations_research::bop::BopRandomFirstSolutionGenerator:

Public Member Functions
	BopRandomFirstSolutionGenerator (absl::string_view name, const BopParameters &parameters, sat::SatSolver *sat_propagator, absl::BitGenRef random)
	~BopRandomFirstSolutionGenerator () override
bool	ShouldBeRun (const ProblemState &problem_state) const override
	Only run the RandomFirstSolution when there is an objective to minimize.
Status	Optimize (const BopParameters &parameters, const ProblemState &problem_state, LearnedInfo *learned_info, TimeLimit *time_limit) override
Public Member Functions inherited from operations_research::bop::BopOptimizerBase
	BopOptimizerBase (absl::string_view name)
virtual	~BopOptimizerBase ()
const std::string &	name () const
	Returns the name given at construction.

Additional Inherited Members
Public Types inherited from operations_research::bop::BopOptimizerBase
enum	Status {   OPTIMAL_SOLUTION_FOUND , SOLUTION_FOUND , INFEASIBLE , LIMIT_REACHED ,   INFORMATION_FOUND , CONTINUE , ABORT }
Static Public Member Functions inherited from operations_research::bop::BopOptimizerBase
static std::string	GetStatusString (Status status)
	Returns a string describing the status.
Protected Attributes inherited from operations_research::bop::BopOptimizerBase
const std::string	name_
StatsGroup	stats_

Detailed Description

This class implements an optimizer that tries various random search strategies, each with a really low conflict limit. It can be used to generate a first solution or to improve an existing one.

By opposition to all the other optimizers, this one doesn't return right away when a new solution is found. Instead, it continues to improve it as long as it has time.

Todo

(user): Coupled with some Local Search it might be used to diversify the solutions. To try.

Definition at line 77 of file bop_fs.h.

Constructor & Destructor Documentation

BopRandomFirstSolutionGenerator()

operations_research::bop::BopRandomFirstSolutionGenerator::BopRandomFirstSolutionGenerator	(	absl::string_view	name,
		const BopParameters &	parameters,
		sat::SatSolver *	sat_propagator,
		absl::BitGenRef	random )

BopRandomFirstSolutionGenerator

Definition at line 236 of file bop_fs.cc.

~BopRandomFirstSolutionGenerator()

operations_research::bop::BopRandomFirstSolutionGenerator::~BopRandomFirstSolutionGenerator ( )

overridedefault

Member Function Documentation

Optimize()

BopOptimizerBase::Status operations_research::bop::BopRandomFirstSolutionGenerator::Optimize ( const BopParameters & parameters, const ProblemState & problem_state, LearnedInfo * learned_info, TimeLimit * time_limit )

overridevirtual

Tries to infer more information about the problem state, i.e. reduces the gap by increasing the lower bound or finding a better solution. Returns SOLUTION_FOUND when a new solution with a better objective cost is found before a time limit. The learned information is cleared and the filled with any new information about the problem, e.g. a new lower bound.

Preconditions: ShouldBeRun() must returns true.

Save the current solver heuristics.

Optimization: Since each Solve() is really fast, we want to limit as much as possible the work around one.

The solution is proved optimal (if any).

Special assignment preference parameters.

Assign SAT assignment preference based on the LP solution.

The solution is proved optimal (if any).

The number of failure is a good approximation of the number of conflicts.

Note

the number of failures of the SAT solver is not reinitialized.

Restore sat_propagator_ to its original state.

Note

if the function is aborted before that, it means we solved the problem to optimality (or proven it to be infeasible), so we don't need to do any extra work in these cases since the sat_propagator_ will not be used anymore.

This can be proved during the call to RestoreSolverToAssumptionLevel().

The solution is proved optimal (if any).

Implements operations_research::bop::BopOptimizerBase.

Definition at line 251 of file bop_fs.cc.

ShouldBeRun()

bool operations_research::bop::BopRandomFirstSolutionGenerator::ShouldBeRun ( const ProblemState & problem_state ) const

overridevirtual

Only run the RandomFirstSolution when there is an objective to minimize.

Implements operations_research::bop::BopOptimizerBase.

Definition at line 246 of file bop_fs.cc.

---

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

• ortools/bop/bop_fs.h
• ortools/bop/bop_fs.cc