Home Original page

Google OR-Tools: ortools/constraint_solver/constraint_solver.h File Reference

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:

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");

IntVar* const p = s.MakeIntVar(0, 20, "pheasant"));

IntVar* const r = s.MakeIntVar(0, 20, "rabbit"));

IntExpr* const heads = s.MakeSum(p, r);

IntExpr* const legs = s.MakeSum(s.MakeProd(p, 2), s.MakeProd(r, 4));

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"