constraint_solver.h File Reference

Detailed Description

Declaration of the core objects for the constraint solver.

The literature around constraint programming is extremely dense but one can find some basic introductions in the following links:

• http://en.wikipedia.org/wiki/Constraint_programming
• http://kti.mff.cuni.cz/~bartak/constraints/index.html

Here is a very simple Constraint Programming problem:

If we see 56 legs and 20 heads, how many two-legged pheasants and four-legged rabbits are we looking at?

Here is some simple Constraint Programming code to find out:

void pheasant() {
  Solver s("pheasant");
  // Create integer variables to represent the number of pheasants and
  // rabbits, with a minimum of 0 and a maximum of 20.
  IntVar* const p = s.MakeIntVar(0, 20, "pheasant"));
  IntVar* const r = s.MakeIntVar(0, 20, "rabbit"));
  // The number of heads is the sum of pheasants and rabbits.
  IntExpr* const heads = s.MakeSum(p, r);
  // The number of legs is the sum of pheasants * 2 and rabbits * 4.
  IntExpr* const legs = s.MakeSum(s.MakeProd(p, 2), s.MakeProd(r, 4));
  // Constraints: the number of legs is 56 and heads is 20.
  Constraint* const ct_legs = s.MakeEquality(legs, 56);
  Constraint* const ct_heads = s.MakeEquality(heads, 20);
  s.AddConstraint(ct_legs);
  s.AddConstraint(ct_heads);
  DecisionBuilder* const db = s.MakePhase(p, r,
                                          Solver::CHOOSE_FIRST_UNBOUND,
                                          Solver::ASSIGN_MIN_VALUE);
  s.NewSearch(db);
  CHECK(s.NextSolution());
  LOG(INFO) << "rabbits -> " << r->Value() << ", pheasants -> "
            << p->Value();
  LOG(INFO) << s.DebugString();
  s.EndSearch();
}

which outputs:

rabbits -> 8, pheasants -> 12
Solver(name = "pheasant",
       state = OUTSIDE_SEARCH,
       branches = 0,
       fails = 0,
       decisions = 0
       propagation loops = 11,
       demons Run = 25,
       Run time = 0 ms)

Definition in file constraint_solver.h.

#include <stddef.h>
#include <stdint.h>
#include <deque>
#include <functional>
#include <memory>
#include <ostream>
#include <random>
#include <string>
#include <utility>
#include <vector>
#include "absl/base/attributes.h"
#include "absl/base/log_severity.h"
#include "absl/container/flat_hash_map.h"
#include "absl/container/flat_hash_set.h"
#include "absl/flags/declare.h"
#include "absl/flags/flag.h"
#include "absl/log/check.h"
#include "absl/random/random.h"
#include "absl/strings/str_format.h"
#include "absl/strings/string_view.h"
#include "absl/time/time.h"
#include "absl/types/span.h"
#include "ortools/base/base_export.h"
#include "ortools/base/logging.h"
#include "ortools/base/map_util.h"
#include "ortools/base/timer.h"
#include "ortools/base/types.h"
#include "ortools/constraint_solver/search_stats.pb.h"
#include "ortools/constraint_solver/solver_parameters.pb.h"
#include "ortools/util/piecewise_linear_function.h"
#include "ortools/util/saturated_arithmetic.h"
#include "ortools/util/sorted_interval_list.h"
#include "ortools/util/tuple_set.h"

Go to the source code of this file.

Classes
struct	operations_research::DefaultPhaseParameters
	This struct holds all parameters for the default search. More...
class	operations_research::Solver
	Solver Class. More...
struct	operations_research::Solver::IntegerCastInfo
struct	operations_research::Solver::PathEnergyCostConstraintSpecification
struct	operations_research::Solver::PathEnergyCostConstraintSpecification::EnergyCost
struct	operations_research::Solver::SearchLogParameters
	Creates a search monitor from logging parameters. More...
class	operations_research::BaseObject
class	operations_research::PropagationBaseObject
	NOLINT. More...
class	operations_research::Decision
class	operations_research::DecisionVisitor
class	operations_research::DecisionBuilder
class	operations_research::ProfiledDecisionBuilder
class	operations_research::Demon
class	operations_research::ModelVisitor
	Model visitor. More...
class	operations_research::Constraint
class	operations_research::CastConstraint
class	operations_research::SearchMonitor
	A search monitor is a simple set of callbacks to monitor all search events. More...
class	operations_research::Rev< T >
class	operations_research::NumericalRev< T >
	Subclass of Rev<T> which adds numerical operations. More...
class	operations_research::RevArray< T >
class	operations_research::NumericalRevArray< T >
	Subclass of RevArray<T> which adds numerical operations. More...
class	operations_research::IntExpr
class	operations_research::IntVarIterator
class	operations_research::InitAndGetValues
struct	operations_research::InitAndGetValues::Iterator
class	operations_research::IntVar
class	operations_research::SolutionCollector
struct	operations_research::SolutionCollector::SolutionData
class	operations_research::BaseObjectiveMonitor
class	operations_research::ObjectiveMonitor
class	operations_research::OptimizeVar
class	operations_research::SearchLimit
	Base class of all search limits. More...
class	operations_research::RegularLimit
class	operations_research::ImprovementSearchLimit
class	operations_research::IntervalVar
class	operations_research::SequenceVar
class	operations_research::AssignmentElement
class	operations_research::IntVarElement
class	operations_research::IntervalVarElement
class	operations_research::SequenceVarElement
class	operations_research::AssignmentContainer< V, E >
class	operations_research::Assignment
class	operations_research::Pack
class	operations_research::DisjunctiveConstraint
class	operations_research::SolutionPool

Namespaces
namespace	operations_research
	OR-Tools root namespace.

Functions
OR_DLL	ABSL_DECLARE_FLAG (int64_t, cp_random_seed)
OR_DLL	ABSL_DECLARE_FLAG (bool, cp_disable_solve)
int64_t	operations_research::CpRandomSeed ()
std::ostream &	operations_research::operator<< (std::ostream &out, const Solver *const s)
int64_t	operations_research::Zero ()
	NOLINT.
int64_t	operations_research::One ()
	This method returns 1.
std::ostream &	operations_research::operator<< (std::ostream &out, const BaseObject *const o)
std::ostream &	operations_research::operator<< (std::ostream &out, const Assignment &assignment)
void	operations_research::SetAssignmentFromAssignment (Assignment *target_assignment, const std::vector< IntVar * > &target_vars, const Assignment *source_assignment, const std::vector< IntVar * > &source_vars)
	NOLINT.

Function Documentation

ABSL_DECLARE_FLAG() [1/2]

OR_DLL ABSL_DECLARE_FLAG	(	bool	,
		cp_disable_solve	)

ABSL_DECLARE_FLAG() [2/2]

OR_DLL ABSL_DECLARE_FLAG	(	int64_t	,
		cp_random_seed	)