routing_cuts.cc File Reference

#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/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
	In SWIG mode, we don't want anything besides these top-level includes.
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 BinaryRelationRepository &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)

Function Documentation

ABSL_FLAG()

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

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.