14#ifndef OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_LP_SCHEDULING_H_
15#define OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_LP_SCHEDULING_H_
17#include "absl/container/flat_hash_map.h"
18#include "absl/memory/memory.h"
24#include "ortools/sat/cp_model.pb.h"
48 return propagated_bounds_[PositiveNode(
index)];
52 const int64 negated_upper_bound = propagated_bounds_[NegativeNode(
index)];
66 static const int kNoParent;
67 static const int kParentToBePropagated;
71 int PositiveNode(
int index)
const {
return 2 *
index; }
72 int NegativeNode(
int index)
const {
return 2 *
index + 1; }
74 void AddNodeToQueue(
int node) {
75 if (!node_in_queue_[node]) {
76 bf_queue_.push_back(node);
77 node_in_queue_[node] =
true;
84 void AddArcs(
int first_index,
int second_index,
int64 offset);
86 bool InitializeArcsAndBounds(
const std::function<
int64(
int64)>& next_accessor,
89 bool UpdateCurrentLowerBoundOfNode(
int node,
int64 new_lb,
int64 offset);
91 bool DisassembleSubtree(
int source,
int target);
93 bool CleanupAndReturnFalse() {
95 for (
int node_to_cleanup : bf_queue_) {
96 node_in_queue_[node_to_cleanup] =
false;
102 const RoutingDimension& dimension_;
103 const int64 num_nodes_;
108 std::vector<std::vector<ArcInfo>> outgoing_arcs_;
110 std::deque<int> bf_queue_;
111 std::vector<bool> node_in_queue_;
112 std::vector<int> tree_parent_node_of_;
116 std::vector<int64> propagated_bounds_;
119 std::vector<int> tmp_dfs_stack_;
122 std::vector<std::pair<int64, int64>>
123 visited_pickup_delivery_indices_for_pair_;
142 int64 upper_bound) = 0;
144 const std::vector<int64>& starts,
145 const std::vector<int64>& ends) = 0;
174 const std::vector<std::pair<int, double>>& variable_coeffs) {
177 for (
const auto& variable_coeff : variable_coeffs) {
187 const std::vector<std::pair<int, double>>& weighted_variables) {
192 const int under_lower_bound_ct =
199 const int above_upper_bound_ct =
205 const int within_bounds_ct =
208 return within_bounds;
219 linear_program_.
Clear();
221 allowed_intervals_.clear();
227 int64 upper_bound)
override {
232 const int64 kMaxValue = 1e10;
233 const double lp_min = lower_bound;
234 const double lp_max =
236 if (lp_min <= lp_max) {
245 const std::vector<int64>& ends)
override {
250 allowed_intervals_[
index] =
251 absl::make_unique<SortedDisjointIntervalList>(starts, ends);
263 for (glop::ColIndex i(0); i < linear_program_.
num_variables(); ++i) {
287 absl::ToDoubleSeconds(duration_limit));
299 linear_program_.
Clear();
302 for (
const auto& allowed_interval : allowed_intervals_) {
303 const double value_double =
GetValue(allowed_interval.first);
308 allowed_interval.second.get();
310 if (it == interval_list->
end() ||
value < it->start) {
330 absl::flat_hash_map<int, std::unique_ptr<SortedDisjointIntervalList>>
337 parameters_.set_num_search_workers(1);
340 parameters_.set_cp_model_presolve(
true);
341 parameters_.set_max_presolve_iterations(0);
342 parameters_.set_catch_sigint_signal(
false);
343 parameters_.set_mip_max_bound(1e8);
344 parameters_.set_search_branching(sat::SatParameters::LP_SEARCH);
350 objective_coefficients_.clear();
351 objective_offset_ = 0;
352 variable_offset_.clear();
353 constraint_offset_.clear();
354 first_constraint_to_offset_ = 0;
357 const int index = model_.variables_size();
358 if (
index >= variable_offset_.size()) {
359 variable_offset_.resize(
index + 1, 0);
361 sat::IntegerVariableProto*
const variable = model_.add_variables();
362 variable->add_domain(0);
363 variable->add_domain(
static_cast<int64>(parameters_.mip_max_bound()));
367 int64 upper_bound)
override {
372 variable_offset_[
index] = 0;
373 const int64 offset_upper_bound =
374 std::min<int64>(
CapSub(upper_bound, variable_offset_[
index]),
375 parameters_.mip_max_bound());
376 const int64 offset_lower_bound =
378 if (offset_lower_bound > offset_upper_bound)
return false;
379 sat::IntegerVariableProto*
const variable = model_.mutable_variables(
index);
380 variable->set_domain(0, offset_lower_bound);
381 variable->set_domain(1, offset_upper_bound);
385 const std::vector<int64>& ends)
override {
388 for (
int i = 0; i < starts.size(); ++i) {
394 model_.mutable_constraints(window_ct)->add_enforcement_literal(variable);
403 if (
index >= objective_coefficients_.size()) {
404 objective_coefficients_.resize(
index + 1, 0);
407 sat::CpObjectiveProto*
const objective = model_.mutable_objective();
408 objective->add_vars(
index);
413 return (
index < objective_coefficients_.size())
414 ? objective_coefficients_[
index]
418 model_.mutable_objective()->Clear();
419 objective_offset_ = 0;
423 const int ct_index = model_.constraints_size();
424 if (ct_index >= constraint_offset_.size()) {
425 constraint_offset_.resize(ct_index + 1, 0);
427 sat::LinearConstraintProto*
const ct =
428 model_.add_constraints()->mutable_linear();
429 ct->add_domain(lower_bound);
430 ct->add_domain(upper_bound);
436 sat::LinearConstraintProto*
const ct =
437 model_.mutable_constraints(ct_index)->mutable_linear();
440 constraint_offset_[ct_index] =
441 CapAdd(constraint_offset_[ct_index],
446 sat::LinearArgumentProto*
const ct =
447 model_.add_constraints()->mutable_lin_max();
448 ct->mutable_target()->add_vars(max_var);
449 ct->mutable_target()->add_coeffs(1);
450 for (
const int var : vars) {
451 sat::LinearExpressionProto*
const expr =
ct->add_exprs();
457 sat::IntegerArgumentProto*
const ct =
458 model_.add_constraints()->mutable_int_prod();
459 ct->set_target(product_var);
460 for (
const int var : vars) {
466 model_.mutable_constraints(
ct)->add_enforcement_literal(condition);
470 for (
int ct_index = first_constraint_to_offset_;
471 ct_index < constraint_offset_.size(); ++ct_index) {
472 if (!model_.mutable_constraints(ct_index)->has_linear())
continue;
473 sat::LinearConstraintProto*
const ct =
474 model_.mutable_constraints(ct_index)->mutable_linear();
475 ct->set_domain(0,
CapSub(
ct->domain(0), constraint_offset_[ct_index]));
476 ct->set_domain(1,
CapSub(
ct->domain(1), constraint_offset_[ct_index]));
478 first_constraint_to_offset_ = constraint_offset_.size();
479 parameters_.set_max_time_in_seconds(absl::ToDoubleSeconds(duration_limit));
480 VLOG(2) << model_.DebugString();
481 if (hint_.vars_size() == model_.variables_size()) {
482 *model_.mutable_solution_hint() = hint_;
487 VLOG(2) << response_.DebugString();
488 if (response_.status() == sat::CpSolverStatus::OPTIMAL ||
489 (response_.status() == sat::CpSolverStatus::FEASIBLE &&
490 !model_.has_objective())) {
492 for (
int i = 0; i < response_.solution_size(); ++i) {
494 hint_.add_values(response_.solution(i));
505 return response_.solution(
index) + variable_offset_[
index];
510 sat::CpModelProto model_;
511 sat::CpSolverResponse response_;
512 sat::SatParameters parameters_;
513 std::vector<double> objective_coefficients_;
514 double objective_offset_;
515 std::vector<int64> variable_offset_;
516 std::vector<int64> constraint_offset_;
517 int first_constraint_to_offset_;
518 sat::PartialVariableAssignment hint_;
526 bool use_precedence_propagator);
533 int vehicle,
const std::function<
int64(
int64)>& next_accessor,
535 std::vector<int64>* break_values,
int64*
cost,
int64* transit_cost,
536 bool clear_lp =
true);
540 std::vector<int64>* cumul_values,
541 std::vector<int64>* break_values,
int64*
cost,
542 int64* transit_cost,
bool clear_lp =
true);
546 std::vector<int64>* cumul_values,
547 std::vector<int64>* break_values);
550 int vehicle,
const std::function<
int64(
int64)>& next_accessor,
552 std::vector<int64>* break_values);
567 bool ComputeRouteCumulBounds(
const std::vector<int64>& route,
568 const std::vector<int64>& fixed_transits,
575 bool SetRouteCumulConstraints(
576 int vehicle,
const std::function<
int64(
int64)>& next_accessor,
577 int64 cumul_offset,
bool optimize_costs,
579 int64* route_cost_offset);
587 void SetGlobalConstraints(
bool optimize_costs,
590 void SetValuesFromLP(
const std::vector<int>& lp_variables,
int64 offset,
592 std::vector<int64>* lp_values);
603 std::unique_ptr<CumulBoundsPropagator> propagator_;
604 std::vector<int64> current_route_min_cumuls_;
605 std::vector<int64> current_route_max_cumuls_;
608 std::vector<int> current_route_cumul_variables_;
609 std::vector<int> index_to_cumul_variable_;
614 std::vector<int> current_route_break_variables_;
618 std::vector<int> all_break_variables_;
622 std::vector<int> vehicle_to_all_break_variables_offset_;
625 int min_start_cumul_;
626 std::vector<std::pair<int64, int64>>
627 visited_pickup_delivery_indices_for_pair_;
639 RoutingSearchParameters::SchedulingSolver solver_type);
646 int vehicle,
const std::function<
int64(
int64)>& next_accessor,
647 int64* optimal_cost);
652 int vehicle,
const std::function<
int64(
int64)>& next_accessor,
653 int64* optimal_cost_without_transits);
661 int vehicle,
const std::function<
int64(
int64)>& next_accessor,
662 std::vector<int64>* optimal_cumuls, std::vector<int64>* optimal_breaks);
668 int vehicle,
const std::function<
int64(
int64)>& next_accessor,
669 std::vector<int64>* packed_cumuls, std::vector<int64>* packed_breaks);
676 std::vector<std::unique_ptr<RoutingLinearSolverWrapper>> solver_;
689 const std::function<
int64(
int64)>& next_accessor,
690 int64* optimal_cost_without_transits);
697 std::vector<int64>* optimal_cumuls,
698 std::vector<int64>* optimal_breaks);
708 std::vector<int64>* packed_cumuls,
709 std::vector<int64>* packed_breaks);
716 std::unique_ptr<RoutingLinearSolverWrapper> solver_;
#define DCHECK_GE(val1, val2)
#define DCHECK_LT(val1, val2)
#define CHECK_LE(val1, val2)
#define DCHECK_EQ(val1, val2)
#define VLOG(verboselevel)
const RoutingDimension & dimension() const
int64 CumulMax(int index) const
bool PropagateCumulBounds(const std::function< int64(int64)> &next_accessor, int64 cumul_offset)
int64 CumulMin(int index) const
CumulBoundsPropagator(const RoutingDimension *dimension)
bool OptimizeAndPack(const std::function< int64(int64)> &next_accessor, RoutingLinearSolverWrapper *solver, std::vector< int64 > *cumul_values, std::vector< int64 > *break_values)
DimensionCumulOptimizerCore(const RoutingDimension *dimension, bool use_precedence_propagator)
bool Optimize(const std::function< int64(int64)> &next_accessor, RoutingLinearSolverWrapper *solver, std::vector< int64 > *cumul_values, std::vector< int64 > *break_values, int64 *cost, int64 *transit_cost, bool clear_lp=true)
DimensionSchedulingStatus OptimizeAndPackSingleRoute(int vehicle, const std::function< int64(int64)> &next_accessor, RoutingLinearSolverWrapper *solver, std::vector< int64 > *cumul_values, std::vector< int64 > *break_values)
const RoutingDimension * dimension() const
DimensionSchedulingStatus OptimizeSingleRoute(int vehicle, const std::function< int64(int64)> &next_accessor, RoutingLinearSolverWrapper *solver, std::vector< int64 > *cumul_values, std::vector< int64 > *break_values, int64 *cost, int64 *transit_cost, bool clear_lp=true)
bool ComputeCumuls(const std::function< int64(int64)> &next_accessor, std::vector< int64 > *optimal_cumuls, std::vector< int64 > *optimal_breaks)
bool IsFeasible(const std::function< int64(int64)> &next_accessor)
GlobalDimensionCumulOptimizer(const RoutingDimension *dimension)
const RoutingDimension * dimension() const
bool ComputeCumulCostWithoutFixedTransits(const std::function< int64(int64)> &next_accessor, int64 *optimal_cost_without_transits)
bool ComputePackedCumuls(const std::function< int64(int64)> &next_accessor, std::vector< int64 > *packed_cumuls, std::vector< int64 > *packed_breaks)
DimensionSchedulingStatus ComputePackedRouteCumuls(int vehicle, const std::function< int64(int64)> &next_accessor, std::vector< int64 > *packed_cumuls, std::vector< int64 > *packed_breaks)
LocalDimensionCumulOptimizer(const RoutingDimension *dimension, RoutingSearchParameters::SchedulingSolver solver_type)
DimensionSchedulingStatus ComputeRouteCumuls(int vehicle, const std::function< int64(int64)> &next_accessor, std::vector< int64 > *optimal_cumuls, std::vector< int64 > *optimal_breaks)
DimensionSchedulingStatus ComputeRouteCumulCost(int vehicle, const std::function< int64(int64)> &next_accessor, int64 *optimal_cost)
const RoutingDimension * dimension() const
DimensionSchedulingStatus ComputeRouteCumulCostWithoutFixedTransits(int vehicle, const std::function< int64(int64)> &next_accessor, int64 *optimal_cost_without_transits)
static int64 FastInt64Round(double x)
void SetCoefficient(int ct_index, int index, double coefficient) override
int64 GetObjectiveValue() const override
int NumVariables() const override
bool IsCPSATSolver() override
void SetVariableDisjointBounds(int index, const std::vector< int64 > &starts, const std::vector< int64 > &ends) override
int CreateNewPositiveVariable() override
double GetValue(int index) const override
DimensionSchedulingStatus Solve(absl::Duration duration_limit) override
~RoutingCPSatWrapper() override
void AddMaximumConstraint(int max_var, std::vector< int > vars) override
void AddProductConstraint(int product_var, std::vector< int > vars) override
bool SetVariableBounds(int index, int64 lower_bound, int64 upper_bound) override
void SetEnforcementLiteral(int ct, int condition) override
double GetObjectiveCoefficient(int index) const override
bool SolutionIsInteger() const override
int CreateNewConstraint(int64 lower_bound, int64 upper_bound) override
int64 GetVariableLowerBound(int index) const override
void SetObjectiveCoefficient(int index, double coefficient) override
void ClearObjective() override
Dimensions represent quantities accumulated at nodes along the routes.
int64 GetObjectiveValue() const override
int NumVariables() const override
bool IsCPSATSolver() override
void SetVariableDisjointBounds(int index, const std::vector< int64 > &starts, const std::vector< int64 > &ends) override
int CreateNewPositiveVariable() override
double GetValue(int index) const override
DimensionSchedulingStatus Solve(absl::Duration duration_limit) override
void SetCoefficient(int ct, int index, double coefficient) override
void AddMaximumConstraint(int max_var, std::vector< int > vars) override
void AddProductConstraint(int product_var, std::vector< int > vars) override
bool SetVariableBounds(int index, int64 lower_bound, int64 upper_bound) override
void SetEnforcementLiteral(int ct, int condition) override
double GetObjectiveCoefficient(int index) const override
RoutingGlopWrapper(const glop::GlopParameters ¶meters)
bool SolutionIsInteger() const override
int CreateNewConstraint(int64 lower_bound, int64 upper_bound) override
int64 GetVariableLowerBound(int index) const override
void SetObjectiveCoefficient(int index, double coefficient) override
void ClearObjective() override
virtual void SetCoefficient(int ct, int index, double coefficient)=0
virtual int NumVariables() const =0
virtual int CreateNewConstraint(int64 lower_bound, int64 upper_bound)=0
int AddReifiedLinearConstraint(int64 lower_bound, int64 upper_bound, const std::vector< std::pair< int, double > > &weighted_variables)
virtual void SetVariableDisjointBounds(int index, const std::vector< int64 > &starts, const std::vector< int64 > &ends)=0
virtual double GetObjectiveCoefficient(int index) const =0
virtual int64 GetObjectiveValue() const =0
virtual void AddProductConstraint(int product_var, std::vector< int > vars)=0
virtual int CreateNewPositiveVariable()=0
virtual int64 GetVariableLowerBound(int index) const =0
virtual bool SetVariableBounds(int index, int64 lower_bound, int64 upper_bound)=0
virtual bool IsCPSATSolver()=0
virtual void ClearObjective()=0
virtual double GetValue(int index) const =0
virtual DimensionSchedulingStatus Solve(absl::Duration duration_limit)=0
virtual void SetObjectiveCoefficient(int index, double coefficient)=0
int AddVariable(int64 lower_bound, int64 upper_bound)
virtual void SetEnforcementLiteral(int ct, int condition)=0
int AddLinearConstraint(int64 lower_bound, int64 upper_bound, const std::vector< std::pair< int, double > > &variable_coeffs)
virtual bool SolutionIsInteger() const =0
virtual ~RoutingLinearSolverWrapper()
virtual void AddMaximumConstraint(int max_var, std::vector< int > vars)=0
This class represents a sorted list of disjoint, closed intervals.
ConstIterator end() const
Iterator FirstIntervalGreaterOrEqual(int64 value) const
Returns an iterator to either:
GlopParameters * GetMutableParameters()
Fractional GetObjectiveValue() const
const DenseRow & variable_values() const
ABSL_MUST_USE_RESULT ProblemStatus Solve(const LinearProgram &lp)
void SetParameters(const GlopParameters ¶meters)
void SetVariableBounds(ColIndex col, Fractional lower_bound, Fractional upper_bound)
void SetCoefficient(RowIndex row, ColIndex col, Fractional value)
void SetConstraintBounds(RowIndex row, Fractional lower_bound, Fractional upper_bound)
ColIndex CreateNewVariable()
bool SolutionIsInteger(const DenseRow &solution, Fractional absolute_tolerance) const
const DenseRow & objective_coefficients() const
void NotifyThatColumnsAreClean()
void SetObjectiveCoefficient(ColIndex col, Fractional value)
ColIndex num_variables() const
RowIndex CreateNewConstraint()
const DenseRow & variable_lower_bounds() const
void SetMaximizationProblem(bool maximize)
Class that owns everything related to a particular optimization model.
This file implements a wrapper around the CP-SAT model proto.
static const int64 kint64max
static const int64 kint64min
std::function< SatParameters(Model *)> NewSatParameters(const std::string ¶ms)
Creates parameters for the solver, which you can add to the model with.
CpSolverResponse SolveCpModel(const CpModelProto &model_proto, Model *model)
Solves the given CpModelProto.
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 CapAdd(int64 x, int64 y)
int64 CapProd(int64 x, int64 y)
int64 CapSub(int64 x, int64 y)
DimensionSchedulingStatus