589 lines
16 KiB
Python
589 lines
16 KiB
Python
# Copyright 2010-2025 Google LLC
|
|
# 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.
|
|
|
|
# Home of constraint solver constraint_solver
|
|
|
|
load("@protobuf//bazel:cc_proto_library.bzl", "cc_proto_library")
|
|
load("@protobuf//bazel:java_proto_library.bzl", "java_proto_library")
|
|
load("@protobuf//bazel:proto_library.bzl", "proto_library")
|
|
load("@protobuf//bazel:py_proto_library.bzl", "py_proto_library")
|
|
load("@rules_cc//cc:cc_library.bzl", "cc_library")
|
|
load("@rules_python//python:py_library.bzl", "py_library")
|
|
|
|
package(default_visibility = ["//visibility:public"])
|
|
|
|
config_setting(
|
|
name = "on_linux",
|
|
constraint_values = ["@platforms//os:linux"],
|
|
)
|
|
|
|
config_setting(
|
|
name = "on_macos",
|
|
constraint_values = ["@platforms//os:macos"],
|
|
)
|
|
|
|
config_setting(
|
|
name = "on_windows",
|
|
constraint_values = ["@platforms//os:windows"],
|
|
)
|
|
|
|
proto_library(
|
|
name = "assignment_proto",
|
|
srcs = ["assignment.proto"],
|
|
visibility = ["//visibility:public"],
|
|
)
|
|
|
|
cc_proto_library(
|
|
name = "assignment_cc_proto",
|
|
visibility = ["//visibility:public"],
|
|
deps = [":assignment_proto"],
|
|
)
|
|
|
|
proto_library(
|
|
name = "search_limit_proto",
|
|
srcs = ["search_limit.proto"],
|
|
visibility = ["//visibility:public"],
|
|
)
|
|
|
|
cc_proto_library(
|
|
name = "search_limit_cc_proto",
|
|
visibility = ["//visibility:public"],
|
|
deps = [":search_limit_proto"],
|
|
)
|
|
|
|
java_proto_library(
|
|
name = "search_limit_java_proto",
|
|
visibility = ["//visibility:public"],
|
|
deps = [":search_limit_proto"],
|
|
)
|
|
|
|
proto_library(
|
|
name = "demon_profiler_proto",
|
|
srcs = ["demon_profiler.proto"],
|
|
visibility = ["//visibility:public"],
|
|
)
|
|
|
|
cc_proto_library(
|
|
name = "demon_profiler_cc_proto",
|
|
visibility = ["//visibility:public"],
|
|
deps = [":demon_profiler_proto"],
|
|
)
|
|
|
|
proto_library(
|
|
name = "search_stats_proto",
|
|
srcs = ["search_stats.proto"],
|
|
visibility = ["//visibility:public"],
|
|
)
|
|
|
|
cc_proto_library(
|
|
name = "search_stats_cc_proto",
|
|
visibility = ["//visibility:public"],
|
|
deps = [":search_stats_proto"],
|
|
)
|
|
|
|
java_proto_library(
|
|
name = "search_stats_java_proto",
|
|
visibility = ["//visibility:public"],
|
|
deps = [":search_stats_proto"],
|
|
)
|
|
|
|
proto_library(
|
|
name = "solver_parameters_proto",
|
|
srcs = ["solver_parameters.proto"],
|
|
visibility = ["//visibility:public"],
|
|
)
|
|
|
|
cc_proto_library(
|
|
name = "solver_parameters_cc_proto",
|
|
visibility = ["//visibility:public"],
|
|
deps = [":solver_parameters_proto"],
|
|
)
|
|
|
|
java_proto_library(
|
|
name = "solver_parameters_java_proto",
|
|
visibility = ["//visibility:public"],
|
|
deps = [":solver_parameters_proto"],
|
|
)
|
|
|
|
py_proto_library(
|
|
name = "assignment_py_pb2",
|
|
visibility = ["//visibility:public"],
|
|
deps = [":assignment_proto"],
|
|
)
|
|
|
|
py_proto_library(
|
|
name = "search_limit_py_pb2",
|
|
visibility = ["//visibility:public"],
|
|
deps = [":search_limit_proto"],
|
|
)
|
|
|
|
py_proto_library(
|
|
name = "demon_profiler_py_pb2",
|
|
visibility = ["//visibility:public"],
|
|
deps = [":demon_profiler_proto"],
|
|
)
|
|
|
|
py_proto_library(
|
|
name = "search_stats_py_pb2",
|
|
visibility = ["//visibility:public"],
|
|
deps = [":search_stats_proto"],
|
|
)
|
|
|
|
py_proto_library(
|
|
name = "solver_parameters_py_pb2",
|
|
visibility = ["//visibility:public"],
|
|
deps = [":solver_parameters_proto"],
|
|
)
|
|
|
|
py_library(
|
|
name = "constraint_solver_py_pb2",
|
|
visibility = ["//visibility:public"],
|
|
deps = [
|
|
":assignment_py_pb2",
|
|
":demon_profiler_py_pb2",
|
|
":search_limit_py_pb2",
|
|
":search_stats_py_pb2",
|
|
":solver_parameters_py_pb2",
|
|
],
|
|
)
|
|
|
|
# ----- Constraint Programming core engine -----
|
|
|
|
# This is the main library.
|
|
# TODO(user): split this monolithic library into independent components.
|
|
# Do the same for others.
|
|
cc_library(
|
|
name = "cp",
|
|
srcs = [
|
|
"alldiff_cst.cc",
|
|
"assignment.cc",
|
|
"constraint_solver.cc",
|
|
"constraints.cc",
|
|
"count_cst.cc",
|
|
"default_search.cc",
|
|
"demon_profiler.cc",
|
|
"deviation.cc",
|
|
"diffn.cc",
|
|
"element.cc",
|
|
"expr_array.cc",
|
|
"expr_cst.cc",
|
|
"expressions.cc",
|
|
"graph_constraints.cc",
|
|
"interval.cc",
|
|
"local_search.cc",
|
|
"model_cache.cc",
|
|
"pack.cc",
|
|
"range_cst.cc",
|
|
"resource.cc",
|
|
"sched_constraints.cc",
|
|
"sched_expr.cc",
|
|
"sched_search.cc",
|
|
"search.cc",
|
|
"table.cc",
|
|
"timetabling.cc",
|
|
"trace.cc",
|
|
"utilities.cc",
|
|
"visitor.cc",
|
|
],
|
|
hdrs = [
|
|
"constraint_solver.h",
|
|
"constraint_solveri.h",
|
|
],
|
|
visibility = ["//visibility:public"],
|
|
deps = [
|
|
":assignment_cc_proto",
|
|
":demon_profiler_cc_proto",
|
|
":search_limit_cc_proto",
|
|
":search_stats_cc_proto",
|
|
":solver_parameters_cc_proto",
|
|
"//ortools/base",
|
|
"//ortools/base:base_export",
|
|
"//ortools/base:bitmap",
|
|
"//ortools/base:file",
|
|
"//ortools/base:int_type",
|
|
"//ortools/base:intops",
|
|
"//ortools/base:iterator_adaptors",
|
|
"//ortools/base:map_util",
|
|
"//ortools/base:mathutil",
|
|
"//ortools/base:numbers",
|
|
"//ortools/base:recordio",
|
|
"//ortools/base:stl_util",
|
|
"//ortools/base:strong_vector",
|
|
"//ortools/base:sysinfo",
|
|
"//ortools/base:timer",
|
|
"//ortools/base:types",
|
|
"//ortools/graph:hamiltonian_path",
|
|
"//ortools/util:bitset",
|
|
"//ortools/util:cached_log",
|
|
"//ortools/util:monoid_operation_tree",
|
|
"//ortools/util:piecewise_linear_function",
|
|
"//ortools/util:range_minimum_query",
|
|
"//ortools/util:saturated_arithmetic",
|
|
"//ortools/util:sorted_interval_list",
|
|
"//ortools/util:string_array",
|
|
"//ortools/util:tuple_set",
|
|
"@abseil-cpp//absl/algorithm:container",
|
|
"@abseil-cpp//absl/base:core_headers",
|
|
"@abseil-cpp//absl/base:log_severity",
|
|
"@abseil-cpp//absl/base:nullability",
|
|
"@abseil-cpp//absl/container:flat_hash_map",
|
|
"@abseil-cpp//absl/container:flat_hash_set",
|
|
"@abseil-cpp//absl/flags:flag",
|
|
"@abseil-cpp//absl/log",
|
|
"@abseil-cpp//absl/log:check",
|
|
"@abseil-cpp//absl/log:vlog_is_on",
|
|
"@abseil-cpp//absl/random",
|
|
"@abseil-cpp//absl/random:distributions",
|
|
"@abseil-cpp//absl/status",
|
|
"@abseil-cpp//absl/strings",
|
|
"@abseil-cpp//absl/strings:str_format",
|
|
"@abseil-cpp//absl/time",
|
|
"@abseil-cpp//absl/types:span",
|
|
"@zlib",
|
|
],
|
|
)
|
|
|
|
# ----- Routing and ArcRouting -----
|
|
|
|
proto_library(
|
|
name = "routing_enums_proto",
|
|
srcs = ["routing_enums.proto"],
|
|
)
|
|
|
|
cc_proto_library(
|
|
name = "routing_enums_cc_proto",
|
|
deps = [":routing_enums_proto"],
|
|
)
|
|
|
|
java_proto_library(
|
|
name = "routing_enums_java_proto",
|
|
deps = [":routing_enums_proto"],
|
|
)
|
|
|
|
proto_library(
|
|
name = "routing_ils_proto",
|
|
srcs = ["routing_ils.proto"],
|
|
deps = [
|
|
":routing_enums_proto",
|
|
":routing_heuristic_parameters_proto"
|
|
],
|
|
)
|
|
|
|
cc_proto_library(
|
|
name = "routing_ils_cc_proto",
|
|
deps = [":routing_ils_proto"],
|
|
)
|
|
|
|
py_proto_library(
|
|
name = "routing_ils_py_pb2",
|
|
deps = [":routing_ils_proto"],
|
|
)
|
|
|
|
java_proto_library(
|
|
name = "routing_ils_java_proto",
|
|
deps = [":routing_ils_proto"],
|
|
)
|
|
|
|
proto_library(
|
|
name = "routing_parameters_proto",
|
|
srcs = ["routing_parameters.proto"],
|
|
deps = [
|
|
":routing_enums_proto",
|
|
":routing_heuristic_parameters_proto",
|
|
":routing_ils_proto",
|
|
":solver_parameters_proto",
|
|
"//ortools/sat:sat_parameters_proto",
|
|
"//ortools/util:optional_boolean_proto",
|
|
"@protobuf//:duration_proto",
|
|
],
|
|
)
|
|
|
|
cc_proto_library(
|
|
name = "routing_parameters_cc_proto",
|
|
deps = [":routing_parameters_proto"],
|
|
)
|
|
|
|
java_proto_library(
|
|
name = "routing_parameters_java_proto",
|
|
deps = [":routing_parameters_proto"],
|
|
)
|
|
|
|
py_proto_library(
|
|
name = "routing_parameters_py_pb2",
|
|
deps = [":routing_parameters_proto"],
|
|
)
|
|
|
|
py_proto_library(
|
|
name = "routing_enums_py_pb2",
|
|
deps = [":routing_enums_proto"],
|
|
)
|
|
|
|
cc_library(
|
|
name = "routing_parameters",
|
|
srcs = ["routing_parameters.cc"],
|
|
hdrs = ["routing_parameters.h"],
|
|
deps = [
|
|
":cp",
|
|
":routing_enums_cc_proto",
|
|
":routing_heuristic_parameters_cc_proto",
|
|
":routing_ils_cc_proto",
|
|
":routing_ils_parameters_utils",
|
|
":routing_parameters_cc_proto",
|
|
":routing_parameters_utils",
|
|
":solver_parameters_cc_proto",
|
|
"//ortools/base",
|
|
"//ortools/base:proto_enum_utils",
|
|
"//ortools/base:protoutil",
|
|
"//ortools/base:types",
|
|
"//ortools/port:proto_utils",
|
|
"//ortools/sat:sat_parameters_cc_proto",
|
|
"//ortools/util:optional_boolean_cc_proto",
|
|
"//ortools/util:testing_utils",
|
|
"@abseil-cpp//absl/container:flat_hash_map",
|
|
"@abseil-cpp//absl/log",
|
|
"@abseil-cpp//absl/strings",
|
|
"@abseil-cpp//absl/strings:str_format",
|
|
"@abseil-cpp//absl/time",
|
|
"@protobuf",
|
|
"@protobuf//:duration_cc_proto",
|
|
],
|
|
)
|
|
|
|
cc_library(
|
|
name = "routing_parameters_utils",
|
|
srcs = ["routing_parameters_utils.cc"],
|
|
hdrs = ["routing_parameters_utils.h"],
|
|
deps = [
|
|
":routing_heuristic_parameters_cc_proto",
|
|
":routing_parameters_cc_proto",
|
|
"//ortools/util:optional_boolean_cc_proto",
|
|
"@abseil-cpp//absl/types:span",
|
|
],
|
|
)
|
|
|
|
cc_library(
|
|
name = "routing_ils_parameters_utils",
|
|
srcs = ["routing_ils_parameters_utils.cc"],
|
|
hdrs = ["routing_ils_parameters_utils.h"],
|
|
visibility = ["//visibility:public"],
|
|
deps = [
|
|
":routing_enums_cc_proto",
|
|
":routing_ils_cc_proto",
|
|
"@abseil-cpp//absl/base:core_headers",
|
|
],
|
|
)
|
|
|
|
cc_library(
|
|
name = "routing_types",
|
|
hdrs = ["routing_types.h"],
|
|
visibility = ["//visibility:public"],
|
|
deps = [
|
|
"//ortools/util:piecewise_linear_function",
|
|
"//ortools/util:strong_integers",
|
|
],
|
|
)
|
|
|
|
cc_library(
|
|
name = "routing_utils",
|
|
srcs = ["routing_utils.cc"],
|
|
hdrs = ["routing_utils.h"],
|
|
visibility = ["//visibility:public"],
|
|
deps = [
|
|
"//ortools/util:saturated_arithmetic",
|
|
"@abseil-cpp//absl/log:check",
|
|
"@abseil-cpp//absl/types:span",
|
|
],
|
|
)
|
|
|
|
cc_library(
|
|
name = "routing_neighborhoods",
|
|
srcs = ["routing_neighborhoods.cc"],
|
|
hdrs = ["routing_neighborhoods.h"],
|
|
visibility = ["//visibility:public"],
|
|
deps = [
|
|
":cp",
|
|
":routing_types",
|
|
":routing_utils",
|
|
"//ortools/base:types",
|
|
"//ortools/util:bitset",
|
|
"//ortools/util:saturated_arithmetic",
|
|
"@abseil-cpp//absl/log:check",
|
|
"@abseil-cpp//absl/types:span",
|
|
],
|
|
)
|
|
|
|
cc_library(
|
|
name = "routing_index_manager",
|
|
srcs = ["routing_index_manager.cc"],
|
|
hdrs = ["routing_index_manager.h"],
|
|
visibility = ["//visibility:public"],
|
|
deps = [
|
|
":routing_types",
|
|
"//ortools/base",
|
|
"//ortools/base:base_export",
|
|
"//ortools/base:strong_vector",
|
|
"@abseil-cpp//absl/container:flat_hash_set",
|
|
"@abseil-cpp//absl/log:check",
|
|
"@abseil-cpp//absl/types:span",
|
|
],
|
|
)
|
|
|
|
cc_library(
|
|
name = "routing_breaks",
|
|
srcs = ["routing_breaks.cc"],
|
|
hdrs = ["routing_breaks.h"],
|
|
deps = [
|
|
":routing_filter_committables",
|
|
"//ortools/algorithms:binary_search",
|
|
"//ortools/util:saturated_arithmetic",
|
|
"@abseil-cpp//absl/log:check",
|
|
"@abseil-cpp//absl/types:span",
|
|
],
|
|
)
|
|
|
|
cc_library(
|
|
name = "routing",
|
|
srcs = [
|
|
"routing.cc",
|
|
"routing_constraints.cc",
|
|
"routing_decision_builders.cc",
|
|
"routing_filters.cc",
|
|
"routing_flow.cc",
|
|
"routing_ils.cc",
|
|
"routing_insertion_lns.cc",
|
|
"routing_lp_scheduling.cc",
|
|
"routing_sat.cc",
|
|
"routing_search.cc",
|
|
],
|
|
hdrs = [
|
|
"routing.h",
|
|
"routing_constraints.h",
|
|
"routing_decision_builders.h",
|
|
"routing_filter_committables.h",
|
|
"routing_filters.h",
|
|
"routing_ils.h",
|
|
"routing_insertion_lns.h",
|
|
"routing_lp_scheduling.h",
|
|
"routing_search.h",
|
|
],
|
|
copts = select({
|
|
"on_linux": [],
|
|
"on_macos": [],
|
|
"on_windows": ["/Zc:preprocessor"],
|
|
"//conditions:default": [],
|
|
}),
|
|
visibility = ["//visibility:public"],
|
|
deps = [
|
|
":cp",
|
|
":routing_breaks",
|
|
":routing_enums_cc_proto",
|
|
":routing_filter_committables",
|
|
":routing_heuristic_parameters_cc_proto",
|
|
":routing_ils_cc_proto",
|
|
":routing_index_manager",
|
|
":routing_neighborhoods",
|
|
":routing_parameters",
|
|
":routing_parameters_cc_proto",
|
|
":routing_parameters_utils",
|
|
":routing_types",
|
|
":routing_utils",
|
|
":solver_parameters_cc_proto",
|
|
"//ortools/base",
|
|
"//ortools/base:adjustable_priority_queue",
|
|
"//ortools/base:dump_vars",
|
|
"//ortools/base:map_util",
|
|
"//ortools/base:mathutil",
|
|
"//ortools/base:protoutil",
|
|
"//ortools/base:stl_util",
|
|
"//ortools/base:strong_vector",
|
|
"//ortools/base:types",
|
|
"//ortools/glop:lp_solver",
|
|
"//ortools/glop:parameters_cc_proto",
|
|
"//ortools/graph",
|
|
"//ortools/graph:christofides",
|
|
"//ortools/graph:connected_components",
|
|
"//ortools/graph:linear_assignment",
|
|
"//ortools/graph:min_cost_flow",
|
|
"//ortools/lp_data",
|
|
"//ortools/lp_data:base",
|
|
"//ortools/port:proto_utils",
|
|
"//ortools/sat:cp_model_cc_proto",
|
|
"//ortools/sat:cp_model_solver",
|
|
"//ortools/sat:integer_base",
|
|
"//ortools/sat:lp_utils",
|
|
"//ortools/sat:model",
|
|
"//ortools/sat:sat_parameters_cc_proto",
|
|
"//ortools/util:bitset",
|
|
"//ortools/util:flat_matrix",
|
|
"//ortools/util:optional_boolean_cc_proto",
|
|
"//ortools/util:piecewise_linear_function",
|
|
"//ortools/util:range_minimum_query",
|
|
"//ortools/util:range_query_function",
|
|
"//ortools/util:saturated_arithmetic",
|
|
"//ortools/util:sorted_interval_list",
|
|
"//ortools/util:time_limit",
|
|
"@abseil-cpp//absl/algorithm:container",
|
|
"@abseil-cpp//absl/base:core_headers",
|
|
"@abseil-cpp//absl/container:btree",
|
|
"@abseil-cpp//absl/container:flat_hash_map",
|
|
"@abseil-cpp//absl/container:flat_hash_set",
|
|
"@abseil-cpp//absl/container:inlined_vector",
|
|
"@abseil-cpp//absl/flags:flag",
|
|
"@abseil-cpp//absl/functional:any_invocable",
|
|
"@abseil-cpp//absl/functional:bind_front",
|
|
"@abseil-cpp//absl/hash",
|
|
"@abseil-cpp//absl/log",
|
|
"@abseil-cpp//absl/log:check",
|
|
"@abseil-cpp//absl/log:die_if_null",
|
|
"@abseil-cpp//absl/memory",
|
|
"@abseil-cpp//absl/status:statusor",
|
|
"@abseil-cpp//absl/strings",
|
|
"@abseil-cpp//absl/strings:str_format",
|
|
"@abseil-cpp//absl/time",
|
|
"@abseil-cpp//absl/types:span",
|
|
"@protobuf",
|
|
],
|
|
)
|
|
|
|
cc_library(
|
|
name = "routing_filter_committables",
|
|
srcs = ["routing_filter_committables.cc"],
|
|
hdrs = ["routing_filter_committables.h"],
|
|
deps = [
|
|
"//ortools/util:bitset",
|
|
"//ortools/util:saturated_arithmetic",
|
|
"@abseil-cpp//absl/log:check",
|
|
"@abseil-cpp//absl/types:span",
|
|
],
|
|
)
|
|
|
|
proto_library(
|
|
name = "routing_heuristic_parameters_proto",
|
|
srcs = ["routing_heuristic_parameters.proto"],
|
|
)
|
|
|
|
java_proto_library(
|
|
name = "routing_heuristic_parameters_java_proto",
|
|
deps = [":routing_heuristic_parameters_proto"],
|
|
)
|
|
|
|
cc_proto_library(
|
|
name = "routing_heuristic_parameters_cc_proto",
|
|
deps = [":routing_heuristic_parameters_proto"],
|
|
)
|
|
|
|
py_proto_library(
|
|
name = "routing_heuristic_parameters_py_pb2",
|
|
deps = [":routing_heuristic_parameters_proto"],
|
|
)
|