or-tools/src/constraint_solver/constraint_solver.cc File Reference

#include "constraint_solver/constraint_solver.h"
#include <setjmp.h>
#include <string.h>
#include <iosfwd>
#include "base/callback.h"
#include "base/commandlineflags.h"
#include "base/integral_types.h"
#include "base/logging.h"
#include "base/macros.h"
#include "base/scoped_ptr.h"
#include "base/stringprintf.h"
#include "base/file.h"
#include "base/recordio.h"
#include "base/stringpiece.h"
#include "zlib.h"
#include "base/concise_iterator.h"
#include "base/map-util.h"
#include "base/stl_util.h"
#include "constraint_solver/constraint_solveri.h"
#include "constraint_solver/model.pb.h"
#include "util/const_int_array.h"
#include "util/tuple_set.h"

Go to the source code of this file.

Namespaces

namespace operations_research

Classes

class operations_research::Queue

namespace More...

struct operations_research::StateInfo

StateMarker / StateInfo struct. More...

struct operations_research::StateMarker

struct operations_research::Trail

class operations_research::Search

Search class. More...

class operations_research::Trace

Trace. More...

Defines

#define CP_FAST_BACKTRACK

Backtrack is implemented using 3 primitives: CP_TRY to start searching CP_DO_FAIL to signal a failure.

#define CP_TRY(search)

We cannot use a method/function for this as we would lose the context in the setjmp implementation.

#define CP_ON_FAIL else

#define CP_DO_FAIL(search) longjmp(search->fail_buffer_, 1)

CP_FAST_BACKTRACK.

Enumerations

enum SentinelMarker

Functions

DEFINE_bool (cp_trace_propagation, false,"Trace propagation events (constraint and demon executions,"" variable modifications).")

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License.

DEFINE_bool (cp_trace_search, false,"Trace search events")

DEFINE_bool (cp_show_constraints, false,"show all constraints added to the solver.")

DEFINE_bool (cp_print_model, false,"use PrintModelVisitor on model before solving.")

DEFINE_bool (cp_model_stats, false,"use StatisticsModelVisitor on model before solving.")

DEFINE_string (cp_export_file,"","Export model to file using CPModelProto.")

DEFINE_bool (cp_no_solve, false,"Force failure at the beginning of a search.")

DEFINE_string (cp_profile_file,"","Export profiling overview to file.")

DEFINE_bool (cp_verbose_fail, false,"Verbose output when failing.")

DEFINE_bool (cp_name_variables, false,"Force all variables to have names.")

void ConstraintSolverFailsHere ()

DemonProfiler * operations_research::BuildDemonProfiler (Solver *const solver)

Forward Declarations and Profiling Support.

void operations_research::DeleteDemonProfiler (DemonProfiler *const monitor)

void operations_research::InstallDemonProfiler (DemonProfiler *const monitor)

Exported Functions.

void operations_research::RestoreBoolValue (IntVar *const var)

namespace

void operations_research::InternalSaveBooleanVarValue (Solver *const solver, IntVar *const var)

bool operations_research::LocalOptimumReached (Search *const search)

Utility methods to ensure the communication between local search and the search.

bool operations_research::AcceptDelta (Search *const search, Assignment *delta, Assignment *deltadelta)

Returns true if the search accepts the delta (actually checking this by calling AcceptDelta on the monitors of the search).

void operations_research::AcceptNeighbor (Search *const search)

Notifies the search that a neighbor has been accepted by local search.

Action * operations_research::NewDomainIntVarCleaner ()

namespace

PropagationMonitor * operations_research::BuildTrace (Solver *const s)

ModelCache * operations_research::BuildModelCache (Solver *const solver)

namespace

DependencyGraph * operations_research::BuildDependencyGraph (Solver *const solver)

void operations_research::SetQueueCleanerOnFail (Solver *const solver, IntVar *const var)

PropagationMonitor * operations_research::BuildPrintTrace (Solver *const s)

std::ostream & operations_research::operator<< (std::ostream &out, const Solver *const s)

Useful Operators.

std::ostream & operations_research::operator<< (std::ostream &out, const BaseObject *o)

NOLINT.

Define Documentation

#define CP_DO_FAIL ( search ) longjmp(search->fail_buffer_, 1)

CP_FAST_BACKTRACK.

Definition at line 977 of file constraint_solver.cc.

#define CP_FAST_BACKTRACK

Backtrack is implemented using 3 primitives: CP_TRY to start searching CP_DO_FAIL to signal a failure.

The program will continue on the CP_ON_FAIL primitive. CP_FAST_BACKTRACK protects an implementation of backtrack using setjmp/longjmp. The clean portable way is to use exceptions, unfortunately, it can be much slower. Thus we use ideas from Prolog, CP/CLP implementations, continuations in C and implement failing and backtracking using setjmp/longjmp.

Definition at line 968 of file constraint_solver.cc.

#define CP_ON_FAIL else

Definition at line 976 of file constraint_solver.cc.

#define CP_TRY ( search )

Value:

CHECK(!search->jmpbuf_filled_) << "Fail() called outside search"; \
  search->jmpbuf_filled_ = true;                                    \
  if (setjmp(search->fail_buffer_) == 0)

We cannot use a method/function for this as we would lose the context in the setjmp implementation.

Definition at line 972 of file constraint_solver.cc.

Function Documentation

void ConstraintSolverFailsHere ( )

Definition at line 59 of file constraint_solver.cc.

DEFINE_bool	(	cp_name_variables	,
		false	,
		"Force all variables to have names."
	)

DEFINE_bool	(	cp_verbose_fail	,
		false	,
		"Verbose output when failing."
	)

DEFINE_bool	(	cp_no_solve	,
		false	,
		"Force failure at the beginning of a search."
	)

DEFINE_bool	(	cp_model_stats	,
		false	,
		"use StatisticsModelVisitor on model before solving."
	)

DEFINE_bool	(	cp_print_model	,
		false	,
		"use PrintModelVisitor on model before solving."
	)

DEFINE_bool	(	cp_show_constraints	,
		false	,
		"show all constraints added to the solver."
	)

DEFINE_bool	(	cp_trace_search	,
		false	,
		"Trace search events"
	)

DEFINE_bool	(	cp_trace_propagation	,
		false	,
		"Trace propagation events (constraint and demon executions,"" variable modifications)."
	)

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License.

You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

This file implements the core objects of the constraint solver: Solver, Search, Queue, ... along with the main resolution loop.

DEFINE_string	(	cp_profile_file	,
		""	,
		"Export profiling overview to file."
	)

DEFINE_string	(	cp_export_file	,
		""	,
		"Export model to file using CPModelProto."
	)

Variable Documentation

T* address_

Definition at line 445 of file constraint_solver.cc.

const int block_size_

Definition at line 462 of file constraint_solver.cc.

Block* blocks_

Definition at line 638 of file constraint_solver.cc.

scoped_array<addrval<T> > buffer_

Definition at line 641 of file constraint_solver.cc.

bool buffer_used_

Definition at line 642 of file constraint_solver.cc.

string compressed

Definition at line 606 of file constraint_solver.cc.

Constraint* const constraint_

Definition at line 2373 of file constraint_solver.cc.

int current_

Definition at line 643 of file constraint_solver.cc.

scoped_array<addrval<T> > data_

Definition at line 640 of file constraint_solver.cc.

Decision* const decision_

Definition at line 2121 of file constraint_solver.cc.

Demon* demon

Definition at line 152 of file constraint_solver.cc.

const int depth_

Definition at line 1025 of file constraint_solver.cc.

Cell* first_

Definition at line 221 of file constraint_solver.cc.

Block* free_blocks_

Definition at line 639 of file constraint_solver.cc.

Cell* free_cells_

Definition at line 223 of file constraint_solver.cc.

Cell* last_

Definition at line 222 of file constraint_solver.cc.

Block* next

Definition at line 153 of file constraint_solver.cc.

T old_value_

Definition at line 446 of file constraint_solver.cc.

scoped_ptr<TrailPacker<T> > packer_

Definition at line 636 of file constraint_solver.cc.

ResultCallback1<Solver::DecisionModification, Solver*>* const selector_

Definition at line 1044 of file constraint_solver.cc.

int size_

Definition at line 644 of file constraint_solver.cc.

scoped_array<char> tmp_block_

Definition at line 523 of file constraint_solver.cc.

const uint64 tmp_size_

Definition at line 522 of file constraint_solver.cc.


Namespaces
namespace	operations_research
Classes
class	operations_research::Queue
	namespace More...
struct	operations_research::StateInfo
	StateMarker / StateInfo struct. More...
struct	operations_research::StateMarker
struct	operations_research::Trail
class	operations_research::Search
	Search class. More...
class	operations_research::Trace
	Trace. More...
Defines
#define	CP_FAST_BACKTRACK
	Backtrack is implemented using 3 primitives: CP_TRY to start searching CP_DO_FAIL to signal a failure.
#define	CP_TRY(search)
	We cannot use a method/function for this as we would lose the context in the setjmp implementation.
#define	CP_ON_FAIL else
#define	CP_DO_FAIL(search) longjmp(search->fail_buffer_, 1)
	CP_FAST_BACKTRACK.
Enumerations
enum	SentinelMarker
Functions
	DEFINE_bool (cp_trace_propagation, false,"Trace propagation events (constraint and demon executions,"" variable modifications).")
	Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License.
	DEFINE_bool (cp_trace_search, false,"Trace search events")
	DEFINE_bool (cp_show_constraints, false,"show all constraints added to the solver.")
	DEFINE_bool (cp_print_model, false,"use PrintModelVisitor on model before solving.")
	DEFINE_bool (cp_model_stats, false,"use StatisticsModelVisitor on model before solving.")
	DEFINE_string (cp_export_file,"","Export model to file using CPModelProto.")
	DEFINE_bool (cp_no_solve, false,"Force failure at the beginning of a search.")
	DEFINE_string (cp_profile_file,"","Export profiling overview to file.")
	DEFINE_bool (cp_verbose_fail, false,"Verbose output when failing.")
	DEFINE_bool (cp_name_variables, false,"Force all variables to have names.")
void	ConstraintSolverFailsHere ()
DemonProfiler *	operations_research::BuildDemonProfiler (Solver *const solver)
	Forward Declarations and Profiling Support.
void	operations_research::DeleteDemonProfiler (DemonProfiler *const monitor)
void	operations_research::InstallDemonProfiler (DemonProfiler *const monitor)
	Exported Functions.
void	operations_research::RestoreBoolValue (IntVar *const var)
	namespace
void	operations_research::InternalSaveBooleanVarValue (Solver const solver, IntVar const var)
bool	operations_research::LocalOptimumReached (Search *const search)
	Utility methods to ensure the communication between local search and the search.
bool	operations_research::AcceptDelta (Search const search, Assignment delta, Assignment *deltadelta)
	Returns true if the search accepts the delta (actually checking this by calling AcceptDelta on the monitors of the search).
void	operations_research::AcceptNeighbor (Search *const search)
	Notifies the search that a neighbor has been accepted by local search.
Action *	operations_research::NewDomainIntVarCleaner ()
	namespace
PropagationMonitor *	operations_research::BuildTrace (Solver *const s)
ModelCache *	operations_research::BuildModelCache (Solver *const solver)
	namespace
DependencyGraph *	operations_research::BuildDependencyGraph (Solver *const solver)
void	operations_research::SetQueueCleanerOnFail (Solver const solver, IntVar const var)
PropagationMonitor *	operations_research::BuildPrintTrace (Solver *const s)
std::ostream &	operations_research::operator<< (std::ostream &out, const Solver *const s)
	Useful Operators.
std::ostream &	operations_research::operator<< (std::ostream &out, const BaseObject *o)
	NOLINT.