linear_relaxation.cc File Reference

#include "ortools/sat/linear_relaxation.h"
#include <algorithm>
#include <cstdint>
#include <limits>
#include <numeric>
#include <optional>
#include <utility>
#include <vector>
#include "absl/base/attributes.h"
#include "absl/container/btree_map.h"
#include "absl/container/flat_hash_map.h"
#include "absl/container/flat_hash_set.h"
#include "absl/log/check.h"
#include "absl/meta/type_traits.h"
#include "absl/types/span.h"
#include "google/protobuf/message.h"
#include "ortools/base/logging.h"
#include "ortools/base/stl_util.h"
#include "ortools/base/strong_vector.h"
#include "ortools/sat/circuit.h"
#include "ortools/sat/clause.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_mapping.h"
#include "ortools/sat/cp_model_utils.h"
#include "ortools/sat/cuts.h"
#include "ortools/sat/diffn_cuts.h"
#include "ortools/sat/implied_bounds.h"
#include "ortools/sat/integer.h"
#include "ortools/sat/integer_expr.h"
#include "ortools/sat/intervals.h"
#include "ortools/sat/linear_constraint.h"
#include "ortools/sat/model.h"
#include "ortools/sat/precedences.h"
#include "ortools/sat/presolve_util.h"
#include "ortools/sat/routing_cuts.h"
#include "ortools/sat/sat_base.h"
#include "ortools/sat/sat_parameters.pb.h"
#include "ortools/sat/sat_solver.h"
#include "ortools/sat/scheduling_cuts.h"
#include "ortools/sat/util.h"
#include "ortools/util/logging.h"
#include "ortools/util/saturated_arithmetic.h"
#include "ortools/util/sorted_interval_list.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
void	operations_research::sat::AppendRelaxationForEqualityEncoding (IntegerVariable var, const Model &model, LinearRelaxation *relaxation, int *num_tight, int *num_loose)
void	operations_research::sat::AppendPartialGreaterThanEncodingRelaxation (IntegerVariable var, const Model &model, LinearRelaxation *relaxation)
void	operations_research::sat::AppendBoolOrRelaxation (const ConstraintProto &ct, Model *model, LinearRelaxation *relaxation)
void	operations_research::sat::AppendBoolAndRelaxation (const ConstraintProto &ct, Model *model, LinearRelaxation *relaxation, ActivityBoundHelper *activity_helper)
void	operations_research::sat::AppendAtMostOneRelaxation (const ConstraintProto &ct, Model *model, LinearRelaxation *relaxation)
void	operations_research::sat::AppendExactlyOneRelaxation (const ConstraintProto &ct, Model *model, LinearRelaxation *relaxation)
std::vector< Literal >	operations_research::sat::CreateAlternativeLiteralsWithView (int num_literals, Model *model, LinearRelaxation *relaxation)
void	operations_research::sat::AppendCircuitRelaxation (const ConstraintProto &ct, Model *model, LinearRelaxation *relaxation)
	Routing relaxation and cut generators.
void	operations_research::sat::AppendRoutesRelaxation (const ConstraintProto &ct, Model *model, LinearRelaxation *relaxation)
void	operations_research::sat::AddCircuitCutGenerator (const ConstraintProto &ct, Model *m, LinearRelaxation *relaxation)
void	operations_research::sat::AddRoutesCutGenerator (const ConstraintProto &ct, Model *m, LinearRelaxation *relaxation)
std::optional< int >	operations_research::sat::DetectMakespan (const std::vector< IntervalVariable > &intervals, const std::vector< AffineExpression > &demands, const AffineExpression &capacity, Model *model)
void	operations_research::sat::AppendNoOverlapRelaxationAndCutGenerator (const ConstraintProto &ct, Model *model, LinearRelaxation *relaxation)
void	operations_research::sat::AppendCumulativeRelaxationAndCutGenerator (const ConstraintProto &ct, Model *model, LinearRelaxation *relaxation)
void	operations_research::sat::AddCumulativeRelaxation (const AffineExpression &capacity, SchedulingConstraintHelper *helper, SchedulingDemandHelper *demands, const std::optional< AffineExpression > &makespan, Model *model, LinearRelaxation *relaxation)
	Scheduling relaxations and cut generators.
void	operations_research::sat::AppendNoOverlap2dRelaxation (const ConstraintProto &ct, Model *model, LinearRelaxation *relaxation)
	Adds the energetic relaxation sum(areas) <= bounding box area.
void	operations_research::sat::AppendLinMaxRelaxationPart1 (const ConstraintProto &ct, Model *model, LinearRelaxation *relaxation)
void	operations_research::sat::AppendMaxAffineRelaxation (const ConstraintProto &ct, Model *model, LinearRelaxation *relaxation)
void	operations_research::sat::AddMaxAffineCutGenerator (const ConstraintProto &ct, Model *model, LinearRelaxation *relaxation)
void	operations_research::sat::AppendLinMaxRelaxationPart2 (IntegerVariable target, const std::vector< Literal > &alternative_literals, const std::vector< LinearExpression > &exprs, Model *model, LinearRelaxation *relaxation)
void	operations_research::sat::AppendLinearConstraintRelaxation (const ConstraintProto &ct, bool linearize_enforced_constraints, Model *model, LinearRelaxation *relaxation, ActivityBoundHelper *activity_helper)
void	operations_research::sat::TryToLinearizeConstraint (const CpModelProto &model_proto, const ConstraintProto &ct, int linearization_level, Model *model, LinearRelaxation *relaxation, ActivityBoundHelper *helper=nullptr)
	Adds linearization of different types of constraints.
void	operations_research::sat::AddIntProdCutGenerator (const ConstraintProto &ct, int linearization_level, Model *m, LinearRelaxation *relaxation)
	Cut generators.
void	operations_research::sat::AppendSquareRelaxation (const ConstraintProto &ct, Model *m, LinearRelaxation *relaxation)
void	operations_research::sat::AddSquareCutGenerator (const ConstraintProto &ct, int linearization_level, Model *m, LinearRelaxation *relaxation)
void	operations_research::sat::AddAllDiffRelaxationAndCutGenerator (const ConstraintProto &ct, int linearization_level, Model *m, LinearRelaxation *relaxation)
bool	operations_research::sat::IntervalIsVariable (const IntervalVariable interval, IntervalsRepository *intervals_repository)
void	operations_research::sat::AddCumulativeCutGenerator (const AffineExpression &capacity, SchedulingConstraintHelper *helper, SchedulingDemandHelper *demands_helper, const std::optional< AffineExpression > &makespan, Model *m, LinearRelaxation *relaxation)
void	operations_research::sat::AddNoOverlapCutGenerator (SchedulingConstraintHelper *helper, const std::optional< AffineExpression > &makespan, Model *m, LinearRelaxation *relaxation)
void	operations_research::sat::AddNoOverlap2dCutGenerator (const ConstraintProto &ct, Model *m, LinearRelaxation *relaxation)
void	operations_research::sat::AddLinMaxCutGenerator (const ConstraintProto &ct, Model *m, LinearRelaxation *relaxation)
void	operations_research::sat::AppendElementEncodingRelaxation (Model *m, LinearRelaxation *relaxation)
LinearRelaxation	operations_research::sat::ComputeLinearRelaxation (const CpModelProto &model_proto, Model *m)
	Builds the linear relaxation of a CpModelProto.