#include "ortools/constraint_solver/constraint_solver.h"
#include <algorithm>
#include <csetjmp>
#include <cstdint>
#include <deque>
#include <iosfwd>
#include <limits>
#include <memory>
#include <ostream>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>
#include "absl/flags/flag.h"
#include "absl/log/check.h"
#include "absl/time/time.h"
#include "ortools/base/logging.h"
#include "ortools/base/map_util.h"
#include "ortools/base/stl_util.h"
#include "ortools/base/sysinfo.h"
#include "ortools/base/timer.h"
#include "ortools/constraint_solver/constraint_solveri.h"
#include "ortools/util/tuple_set.h"
#include "zconf.h"
#include "zlib.h"

Classes
class	operations_research::Queue

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...

class	operations_research::LocalSearchMonitorPrimary
	-------— Local Search Monitor Primary -------— More...

Namespaces
namespace	operations_research
	In SWIG mode, we don't want anything besides these top-level includes.

Macros
#define	CP_TRY(search)

#define	CP_ON_FAIL else

#define	CP_DO_FAIL(search)

#define	CALL_EVENT_LISTENERS(Event)

Functions
	ABSL_FLAG (bool, cp_trace_propagation, false, "Trace propagation events (constraint and demon executions," " variable modifications).")
	These flags are used to set the fields in the DefaultSolverParameters proto.

	ABSL_FLAG (bool, cp_trace_search, false, "Trace search events")

	ABSL_FLAG (bool, cp_print_added_constraints, false, "show all constraints added to the solver.")

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

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

	ABSL_FLAG (bool, cp_disable_solve, false, "Force failure at the beginning of a search.")

	ABSL_FLAG (std::string, cp_profile_file, "", "Export profiling overview to file.")

	ABSL_FLAG (bool, cp_print_local_search_profile, false, "Print local search profiling data after solving.")

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

	ABSL_FLAG (bool, cp_name_cast_variables, false, "Name variables casted from expressions")

	ABSL_FLAG (bool, cp_use_small_table, true, "Use small compact table constraint when possible.")

	ABSL_FLAG (bool, cp_use_cumulative_edge_finder, true, "Use the O(n log n) cumulative edge finding algorithm described " "in 'Edge Finding Filtering Algorithm for Discrete Cumulative " "Resources in O(kn log n)' by Petr Vilim, CP 2009.")

	ABSL_FLAG (bool, cp_use_cumulative_time_table, true, "Use a O(n^2) cumulative time table propagation algorithm.")

	ABSL_FLAG (bool, cp_use_cumulative_time_table_sync, false, "Use a synchronized O(n^2 log n) cumulative time table propagation " "algorithm.")

	ABSL_FLAG (bool, cp_use_sequence_high_demand_tasks, true, "Use a sequence constraints for cumulative tasks that have a " "demand greater than half of the capacity of the resource.")

	ABSL_FLAG (bool, cp_use_all_possible_disjunctions, true, "Post temporal disjunctions for all pairs of tasks sharing a " "cumulative resource and that cannot overlap because the sum of " "their demand exceeds the capacity.")

	ABSL_FLAG (int, cp_max_edge_finder_size, 50, "Do not post the edge finder in the cumulative constraints if " "it contains more than this number of tasks")

	ABSL_FLAG (bool, cp_diffn_use_cumulative, true, "Diffn constraint adds redundant cumulative constraint")

	ABSL_FLAG (bool, cp_use_element_rmq, true, "If true, rmq's will be used in element expressions.")

	ABSL_FLAG (int, cp_check_solution_period, 1, "Number of solutions explored between two solution checks during " "local search.")

	ABSL_FLAG (int64_t, cp_random_seed, 12345, "Random seed used in several (but not all) random number " "generators used by the CP solver. Use -1 to auto-generate an" "undeterministic random seed.")

void	ConstraintSolverFailsHere ()

void	operations_research::InstallDemonProfiler (DemonProfiler *monitor)
	--— Forward Declarations and Profiling Support --—

DemonProfiler *	operations_research::BuildDemonProfiler (Solver *solver)

void	operations_research::DeleteDemonProfiler (DemonProfiler *monitor)

void	operations_research::InstallLocalSearchProfiler (LocalSearchProfiler *monitor)

LocalSearchProfiler *	operations_research::BuildLocalSearchProfiler (Solver *solver)

void	operations_research::DeleteLocalSearchProfiler (LocalSearchProfiler *monitor)

void	operations_research::CleanVariableOnFail (IntVar *var)
	---------------— Queue class ---------------—

void	operations_research::RestoreBoolValue (IntVar *var)
	--— Trail --—

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

bool	operations_research::LocalOptimumReached (Search *search)
	Returns true if a local optimum has been reached and cannot be improved.

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

void	operations_research::AcceptNeighbor (Search *search)
	Notifies the search that a neighbor has been accepted by local search.

void	operations_research::AcceptUncheckedNeighbor (Search *search)

PropagationMonitor *	operations_research::BuildTrace (Solver *s)

LocalSearchMonitor *	operations_research::BuildLocalSearchMonitorPrimary (Solver *s)

ModelCache *	operations_research::BuildModelCache (Solver *solver)

PropagationMonitor *	operations_research::BuildPrintTrace (Solver *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 *const o)

Macro Definition Documentation

◆ CALL_EVENT_LISTENERS

#define CALL_EVENT_LISTENERS ( Event )

Value:

  do {                                                        \
    ForAll(GetEventListeners(Solver::MonitorEvent::k##Event), \
           &SearchMonitor::Event);                            \
  } while (false)

Definition at line 1224 of file constraint_solver.cc.

◆ CP_DO_FAIL

#define CP_DO_FAIL ( search )

Value:

longjmp(search->fail_buffer_, 1)

Definition at line 1134 of file constraint_solver.cc.

◆ CP_ON_FAIL

#define CP_ON_FAIL else

Definition at line 1133 of file constraint_solver.cc.

◆ CP_TRY

#define CP_TRY ( search )

Value:

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

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. 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 the default failing and backtracking using setjmp/longjmp. You can still use exceptions by defining CP_USE_EXCEPTIONS_FOR_BACKTRACK We cannot use a method/function for this as we would lose the context in the setjmp implementation.

Definition at line 1129 of file constraint_solver.cc.

Function Documentation

◆ ABSL_FLAG() [1/21]

ABSL_FLAG	(	bool	,
		cp_diffn_use_cumulative	,
		true	,
		"Diffn constraint adds redundant cumulative constraint"	)

◆ ABSL_FLAG() [2/21]

ABSL_FLAG	(	bool	,
		cp_disable_solve	,
		false	,
		"Force failure at the beginning of a search."	)

◆ ABSL_FLAG() [3/21]

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

◆ ABSL_FLAG() [4/21]

ABSL_FLAG	(	bool	,
		cp_name_cast_variables	,
		false	,
		"Name variables casted from expressions"	)

◆ ABSL_FLAG() [5/21]

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

◆ ABSL_FLAG() [6/21]

ABSL_FLAG	(	bool	,
		cp_print_added_constraints	,
		false	,
		"show all constraints added to the solver."	)

◆ ABSL_FLAG() [7/21]

ABSL_FLAG	(	bool	,
		cp_print_local_search_profile	,
		false	,
		"Print local search profiling data after solving."	)

◆ ABSL_FLAG() [8/21]

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

◆ ABSL_FLAG() [9/21]

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

These flags are used to set the fields in the DefaultSolverParameters proto.

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.

◆ ABSL_FLAG() [10/21]

ABSL_FLAG	(	bool	,
		cp_trace_search	,
		false	,
		"Trace search events"	)

◆ ABSL_FLAG() [11/21]

ABSL_FLAG	(	bool	,
		cp_use_all_possible_disjunctions	,
		true	,
		"Post temporal disjunctions for all pairs of tasks sharing a " "cumulative resource and that cannot overlap because the sum of " "their demand exceeds the capacity."	)

◆ ABSL_FLAG() [12/21]

ABSL_FLAG	(	bool	,
		cp_use_cumulative_edge_finder	,
		true	,
		"Use the O(n log n) cumulative edge finding algorithm described " "in 'Edge Finding Filtering Algorithm for Discrete Cumulative " "Resources in O(kn log n)' by Petr	Vilim,
		CP 2009."	)

◆ ABSL_FLAG() [13/21]

ABSL_FLAG	(	bool	,
		cp_use_cumulative_time_table	,
		true	,
		"Use a O(n^2) cumulative time table propagation algorithm."	)

◆ ABSL_FLAG() [14/21]

ABSL_FLAG	(	bool	,
		cp_use_cumulative_time_table_sync	,
		false	,
		"Use a synchronized O(n^2 log n) cumulative time table propagation " "algorithm."	)

◆ ABSL_FLAG() [15/21]

ABSL_FLAG	(	bool	,
		cp_use_element_rmq	,
		true	,
		"If	true,
		rmq 's will be used in element expressions."	)

◆ ABSL_FLAG() [16/21]

ABSL_FLAG	(	bool	,
		cp_use_sequence_high_demand_tasks	,
		true	,
		"Use a sequence constraints for cumulative tasks that have a " "demand greater than half of the capacity of the resource."	)

◆ ABSL_FLAG() [17/21]

ABSL_FLAG	(	bool	,
		cp_use_small_table	,
		true	,
		"Use small compact table constraint when possible."	)

◆ ABSL_FLAG() [18/21]

ABSL_FLAG	(	int	,
		cp_check_solution_period	,
		1	,
		"Number of solutions explored between two solution checks during " "local search."	)

◆ ABSL_FLAG() [19/21]

ABSL_FLAG	(	int	,
		cp_max_edge_finder_size	,
		50	,
		"Do not post the edge finder in the cumulative constraints if " "it contains more than this number of tasks"	)

◆ ABSL_FLAG() [20/21]

ABSL_FLAG	(	int64_t	,
		cp_random_seed	,
		12345	,
		"Random seed used in several (but not all) random number " "generators used by the CP solver. Use -1 to auto-generate an" "undeterministic random seed."	)

◆ ABSL_FLAG() [21/21]

ABSL_FLAG	(	std::string	,
		cp_profile_file	,
		""	,
		"Export profiling overview to file."	)

◆ ConstraintSolverFailsHere()

void ConstraintSolverFailsHere ( )

Definition at line 99 of file constraint_solver.cc.

Variable Documentation

◆ compressed

std::string compressed

Definition at line 691 of file constraint_solver.cc.

◆ next

Block* next

Definition at line 692 of file constraint_solver.cc.

Classes

Namespaces

Macros

Functions

Macro Definition Documentation

◆ CALL_EVENT_LISTENERS

◆ CP_DO_FAIL

◆ CP_ON_FAIL

◆ CP_TRY

Function Documentation

◆ ABSL_FLAG() [1/21]

◆ ABSL_FLAG() [2/21]

◆ ABSL_FLAG() [3/21]

◆ ABSL_FLAG() [4/21]

◆ ABSL_FLAG() [5/21]

◆ ABSL_FLAG() [6/21]

◆ ABSL_FLAG() [7/21]

◆ ABSL_FLAG() [8/21]

◆ ABSL_FLAG() [9/21]

◆ ABSL_FLAG() [10/21]

◆ ABSL_FLAG() [11/21]

◆ ABSL_FLAG() [12/21]

◆ ABSL_FLAG() [13/21]

◆ ABSL_FLAG() [14/21]

◆ ABSL_FLAG() [15/21]

◆ ABSL_FLAG() [16/21]

◆ ABSL_FLAG() [17/21]

◆ ABSL_FLAG() [18/21]

◆ ABSL_FLAG() [19/21]

◆ ABSL_FLAG() [20/21]

◆ ABSL_FLAG() [21/21]

◆ ConstraintSolverFailsHere()

Variable Documentation

◆ compressed

◆ next