 |
Google OR-Tools v9.15
a fast and portable software suite for combinatorial optimization
|
|
Google OR-Tools v9.15
a fast and portable software suite for combinatorial optimization
|
#include "ortools/sat/routing_cuts.h"#include <algorithm>#include <atomic>#include <cmath>#include <cstdint>#include <cstdlib>#include <functional>#include <limits>#include <memory>#include <numeric>#include <queue>#include <stack>#include <string>#include <tuple>#include <utility>#include <vector>#include "absl/algorithm/container.h"#include "absl/cleanup/cleanup.h"#include "absl/container/flat_hash_map.h"#include "absl/container/flat_hash_set.h"#include "absl/flags/flag.h"#include "absl/log/check.h"#include "absl/log/log.h"#include "absl/log/vlog_is_on.h"#include "absl/numeric/bits.h"#include "absl/numeric/int128.h"#include "absl/random/distributions.h"#include "absl/strings/str_cat.h"#include "absl/types/span.h"#include "ortools/base/logging.h"#include "ortools/base/mathutil.h"#include "ortools/base/stl_util.h"#include "ortools/base/strong_vector.h"#include "ortools/graph/connected_components.h"#include "ortools/graph/graph.h"#include "ortools/graph/max_flow.h"#include "ortools/sat/clause.h"#include "ortools/sat/cp_model.pb.h"#include "ortools/sat/cp_model_utils.h"#include "ortools/sat/cuts.h"#include "ortools/sat/implied_bounds.h"#include "ortools/sat/integer.h"#include "ortools/sat/integer_base.h"#include "ortools/sat/linear_constraint.h"#include "ortools/sat/linear_constraint_manager.h"#include "ortools/sat/model.h"#include "ortools/sat/precedences.h"#include "ortools/sat/routes_support_graph.pb.h"#include "ortools/sat/sat_base.h"#include "ortools/sat/sat_parameters.pb.h"#include "ortools/sat/synchronization.h"#include "ortools/sat/util.h"#include "ortools/util/strong_integers.h"Go to the source code of this file.
Namespaces | |
| namespace | operations_research |
| OR-Tools root namespace. | |
| namespace | operations_research::sat |
Functions | |
| ABSL_FLAG (bool, cp_model_dump_routes_support_graphs, false, "DEBUG ONLY. When set to true, SolveCpModel() dumps the arcs with " "non-zero LP values of the routes constraints, at decision level 0, " "which are used to subsequently generate cuts. The values are " "written as a SupportGraphProto in text format to " "'FLAGS_cp_model_dump_prefix'support_graph_{counter}.pb.txt.") | |
| RoutingCumulExpressions | operations_research::sat::DetectDimensionsAndCumulExpressions (int num_nodes, absl::Span< const int > tails, absl::Span< const int > heads, absl::Span< const Literal > literals, const ConditionalLinear2Bounds &binary_relation_repository) |
| std::pair< IntegerValue, IntegerValue > | operations_research::sat::GetDifferenceBounds (const NodeExpression &x_expr, const NodeExpression &y_expr, const sat::Relation &r, const std::pair< IntegerValue, IntegerValue > &x_var_bounds, const std::pair< IntegerValue, IntegerValue > &y_var_bounds) |
| std::pair< int, int > | operations_research::sat::MaybeFillMissingRoutesConstraintNodeExpressions (const CpModelProto &input_model, CpModelProto &output_model) |
| void | operations_research::sat::GenerateInterestingSubsets (int num_nodes, absl::Span< const std::pair< int, int > > arcs, int stop_at_num_components, std::vector< int > *subset_data, std::vector< absl::Span< const int > > *subsets) |
| void | operations_research::sat::ExtractAllSubsetsFromForest (absl::Span< const int > parent, std::vector< int > *subset_data, std::vector< absl::Span< const int > > *subsets, int node_limit) |
| std::vector< int > | operations_research::sat::ComputeGomoryHuTree (int num_nodes, absl::Span< const ArcWithLpValue > relevant_arcs) |
| void | operations_research::sat::SymmetrizeArcs (std::vector< ArcWithLpValue > *arcs) |
| int | operations_research::sat::TryAllSubsets (std::string cut_name, absl::Span< const int > subset_data, std::vector< absl::Span< const int > > subsets, RoutingCutHelper &helper, LinearConstraintManager *manager) |
| void | operations_research::sat::SeparateSubtourInequalities (RoutingCutHelper &helper, LinearConstraintManager *manager) |
| CutGenerator | operations_research::sat::CreateStronglyConnectedGraphCutGenerator (int num_nodes, absl::Span< const int > tails, absl::Span< const int > heads, absl::Span< const Literal > literals, Model *model) |
| CutGenerator | operations_research::sat::CreateCVRPCutGenerator (int num_nodes, absl::Span< const int > tails, absl::Span< const int > heads, absl::Span< const Literal > literals, absl::Span< const AffineExpression > flat_node_dim_expressions, Model *model) |
| void | operations_research::sat::SeparateFlowInequalities (int num_nodes, absl::Span< const int > tails, absl::Span< const int > heads, absl::Span< const AffineExpression > arc_capacities, std::function< void(const std::vector< bool > &in_subset, IntegerValue *min_incoming_flow, IntegerValue *min_outgoing_flow)> get_flows, const util_intops::StrongVector< IntegerVariable, double > &lp_values, LinearConstraintManager *manager, Model *model) |
| CutGenerator | operations_research::sat::CreateFlowCutGenerator (int num_nodes, const std::vector< int > &tails, const std::vector< int > &heads, const std::vector< AffineExpression > &arc_capacities, std::function< void(const std::vector< bool > &in_subset, IntegerValue *min_incoming_flow, IntegerValue *min_outgoing_flow)> get_flows, Model *model) |
| ABSL_FLAG | ( | bool | , |
| cp_model_dump_routes_support_graphs | , | ||
| false | , | ||
| "DEBUG ONLY. When set to | true, | ||
| SolveCpModel() dumps the arcs with " "non-zero LP values of the routes | constraints, | ||
| at decision level | 0, | ||
| " "which are used to subsequently generate cuts. The values are " "written as a SupportGraphProto in text format to " " 'FLAGS_cp_model_dump_prefix 'support_graph_{counter}.pb.txt." | ) |
1.15.0