1 // Copyright 2010-2021 Google LLC 2 // Licensed under the Apache License, Version 2.0 (the "License"); 3 // you may not use this file except in compliance with the License. 4 // You may obtain a copy of the License at 5 // 6 // http://www.apache.org/licenses/LICENSE-2.0 7 // 8 // Unless required by applicable law or agreed to in writing, software 9 // distributed under the License is distributed on an "AS IS" BASIS, 10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 11 // See the License for the specific language governing permissions and 12 // limitations under the License. 13 14 #ifndef OR_TOOLS_SAT_LINEAR_PROGRAMMING_CONSTRAINT_H_ 15 #define OR_TOOLS_SAT_LINEAR_PROGRAMMING_CONSTRAINT_H_ 16 17 #include <cstdint> 18 #include <limits> 19 #include <utility> 20 #include <vector> 21 22 #include "absl/container/flat_hash_map.h" 23 #include "ortools/base/int_type.h" 24 #include "ortools/base/strong_vector.h" 25 #include "ortools/glop/revised_simplex.h" 26 #include "ortools/lp_data/lp_data.h" 27 #include "ortools/lp_data/lp_data_utils.h" 28 #include "ortools/lp_data/lp_types.h" 29 #include "ortools/sat/cuts.h" 30 #include "ortools/sat/implied_bounds.h" 31 #include "ortools/sat/integer.h" 32 #include "ortools/sat/integer_expr.h" 33 #include "ortools/sat/linear_constraint.h" 34 #include "ortools/sat/linear_constraint_manager.h" 35 #include "ortools/sat/model.h" 36 #include "ortools/sat/util.h" 37 #include "ortools/sat/zero_half_cuts.h" 38 #include "ortools/util/rev.h" 39 #include "ortools/util/time_limit.h" 40 41 namespace operations_research { 42 namespace sat { 43 44 // Stores for each IntegerVariable its temporary LP solution. 45 // 46 // This is shared between all LinearProgrammingConstraint because in the corner 47 // case where we have many different LinearProgrammingConstraint and a lot of 48 // variable, we could theoretically use up a quadratic amount of memory 49 // otherwise. 50 // 51 // TODO(user): find a better way? 52 struct LinearProgrammingConstraintLpSolution 53 : public absl::StrongVector<IntegerVariable, double> { LinearProgrammingConstraintLpSolutionLinearProgrammingConstraintLpSolution54 LinearProgrammingConstraintLpSolution() {} 55 }; 56 57 // Helper struct to combine info generated from solving LP. 58 struct LPSolveInfo { 59 glop::ProblemStatus status; 60 double lp_objective = -std::numeric_limits<double>::infinity(); 61 IntegerValue new_obj_bound = kMinIntegerValue; 62 }; 63 64 // Simple class to combine linear expression efficiently. First in a sparse 65 // way that switch to dense when the number of non-zeros grows. 66 class ScatteredIntegerVector { 67 public: 68 // This must be called with the correct size before any other functions are 69 // used. 70 void ClearAndResize(int size); 71 72 // Does vector[col] += value and return false in case of overflow. 73 bool Add(glop::ColIndex col, IntegerValue value); 74 75 // Similar to Add() but for multiplier * terms. 76 // Returns false in case of overflow. 77 bool AddLinearExpressionMultiple( 78 IntegerValue multiplier, 79 const std::vector<std::pair<glop::ColIndex, IntegerValue>>& terms); 80 81 // This is not const only because non_zeros is sorted. Note that sorting the 82 // non-zeros make the result deterministic whether or not we were in sparse 83 // mode. 84 // 85 // TODO(user): Ideally we should convert to IntegerVariable as late as 86 // possible. Prefer to use GetTerms(). 87 void ConvertToLinearConstraint( 88 const std::vector<IntegerVariable>& integer_variables, 89 IntegerValue upper_bound, LinearConstraint* result); 90 91 // Similar to ConvertToLinearConstraint(). 92 std::vector<std::pair<glop::ColIndex, IntegerValue>> GetTerms(); 93 94 // We only provide the const []. 95 IntegerValue operator[](glop::ColIndex col) const { 96 return dense_vector_[col]; 97 } 98 IsSparse()99 const bool IsSparse() const { return is_sparse_; } 100 101 private: 102 // If is_sparse is true we maintain the non_zeros positions and bool vector 103 // of dense_vector_. Otherwise we don't. Note that we automatically switch 104 // from sparse to dense as needed. 105 bool is_sparse_ = true; 106 std::vector<glop::ColIndex> non_zeros_; 107 absl::StrongVector<glop::ColIndex, bool> is_zeros_; 108 109 // The dense representation of the vector. 110 absl::StrongVector<glop::ColIndex, IntegerValue> dense_vector_; 111 }; 112 113 // A SAT constraint that enforces a set of linear inequality constraints on 114 // integer variables using an LP solver. 115 // 116 // The propagator uses glop's revised simplex for feasibility and propagation. 117 // It uses the Reduced Cost Strengthening technique, a classic in mixed integer 118 // programming, for instance see the thesis of Tobias Achterberg, 119 // "Constraint Integer Programming", sections 7.7 and 8.8, algorithm 7.11. 120 // http://nbn-resolving.de/urn:nbn:de:0297-zib-11129 121 // 122 // Per-constraint bounds propagation is NOT done by this constraint, 123 // it should be done by redundant constraints, as reduced cost propagation 124 // may miss some filtering. 125 // 126 // Note that this constraint works with double floating-point numbers, so one 127 // could be worried that it may filter too much in case of precision issues. 128 // However, by default, we interpret the LP result by recomputing everything 129 // in integer arithmetic, so we are exact. 130 class LinearProgrammingDispatcher; 131 class LinearProgrammingConstraint : public PropagatorInterface, 132 ReversibleInterface { 133 public: 134 typedef glop::RowIndex ConstraintIndex; 135 136 explicit LinearProgrammingConstraint(Model* model); 137 138 // Add a new linear constraint to this LP. 139 void AddLinearConstraint(const LinearConstraint& ct); 140 141 // Set the coefficient of the variable in the objective. Calling it twice will 142 // overwrite the previous value. 143 void SetObjectiveCoefficient(IntegerVariable ivar, IntegerValue coeff); 144 145 // The main objective variable should be equal to the linear sum of 146 // the arguments passed to SetObjectiveCoefficient(). SetMainObjectiveVariable(IntegerVariable ivar)147 void SetMainObjectiveVariable(IntegerVariable ivar) { objective_cp_ = ivar; } ObjectiveVariable()148 IntegerVariable ObjectiveVariable() const { return objective_cp_; } 149 150 // Register a new cut generator with this constraint. 151 void AddCutGenerator(CutGenerator generator); 152 153 // Returns the LP value and reduced cost of a variable in the current 154 // solution. These functions should only be called when HasSolution() is true. 155 // 156 // Note that this solution is always an OPTIMAL solution of an LP above or 157 // at the current decision level. We "erase" it when we backtrack over it. HasSolution()158 bool HasSolution() const { return lp_solution_is_set_; } SolutionObjectiveValue()159 double SolutionObjectiveValue() const { return lp_objective_; } 160 double GetSolutionValue(IntegerVariable variable) const; 161 double GetSolutionReducedCost(IntegerVariable variable) const; SolutionIsInteger()162 bool SolutionIsInteger() const { return lp_solution_is_integer_; } 163 164 // PropagatorInterface API. 165 bool Propagate() override; 166 bool IncrementalPropagate(const std::vector<int>& watch_indices) override; 167 void RegisterWith(Model* model); 168 169 // ReversibleInterface API. 170 void SetLevel(int level) override; 171 NumVariables()172 int NumVariables() const { return integer_variables_.size(); } integer_variables()173 const std::vector<IntegerVariable>& integer_variables() const { 174 return integer_variables_; 175 } DimensionString()176 std::string DimensionString() const { return lp_data_.GetDimensionString(); } 177 178 // Returns a IntegerLiteral guided by the underlying LP constraints. 179 // 180 // This looks at all unassigned 0-1 variables, takes the one with 181 // a support value closest to 0.5, and tries to assign it to 1. 182 // If all 0-1 variables have an integer support, returns kNoLiteralIndex. 183 // Tie-breaking is done using the variable natural order. 184 // 185 // TODO(user): This fixes to 1, but for some problems fixing to 0 186 // or to the std::round(support value) might work better. When this is the 187 // case, change behaviour automatically? 188 std::function<IntegerLiteral()> HeuristicLpMostInfeasibleBinary(Model* model); 189 190 // Returns a IntegerLiteral guided by the underlying LP constraints. 191 // 192 // This computes the mean of reduced costs over successive calls, 193 // and tries to fix the variable which has the highest reduced cost. 194 // Tie-breaking is done using the variable natural order. 195 // Only works for 0/1 variables. 196 // 197 // TODO(user): Try to get better pseudocosts than averaging every time 198 // the heuristic is called. MIP solvers initialize this with strong branching, 199 // then keep track of the pseudocosts when doing tree search. Also, this 200 // version only branches on var >= 1 and keeps track of reduced costs from var 201 // = 1 to var = 0. This works better than the conventional MIP where the 202 // chosen variable will be argmax_var min(pseudocost_var(0->1), 203 // pseudocost_var(1->0)), probably because we are doing DFS search where MIP 204 // does BFS. This might depend on the model, more trials are necessary. We 205 // could also do exponential smoothing instead of decaying every N calls, i.e. 206 // pseudo = a * pseudo + (1-a) reduced. 207 std::function<IntegerLiteral()> HeuristicLpReducedCostBinary(Model* model); 208 209 // Returns a IntegerLiteral guided by the underlying LP constraints. 210 // 211 // This computes the mean of reduced costs over successive calls, 212 // and tries to fix the variable which has the highest reduced cost. 213 // Tie-breaking is done using the variable natural order. 214 std::function<IntegerLiteral()> HeuristicLpReducedCostAverageBranching(); 215 216 // Average number of nonbasic variables with zero reduced costs. average_degeneracy()217 double average_degeneracy() const { 218 return average_degeneracy_.CurrentAverage(); 219 } 220 total_num_simplex_iterations()221 int64_t total_num_simplex_iterations() const { 222 return total_num_simplex_iterations_; 223 } 224 225 // Returns some statistics about this LP. 226 std::string Statistics() const; 227 228 // Important: this is only temporarily valid. LatestOptimalConstraintOrNull()229 IntegerSumLE* LatestOptimalConstraintOrNull() const { 230 if (optimal_constraints_.empty()) return nullptr; 231 return optimal_constraints_.back().get(); 232 } 233 OptimalConstraints()234 const std::vector<std::unique_ptr<IntegerSumLE>>& OptimalConstraints() const { 235 return optimal_constraints_; 236 } 237 238 private: 239 // Helper methods for branching. Returns true if branching on the given 240 // variable helps with more propagation or finds a conflict. 241 bool BranchOnVar(IntegerVariable var); 242 LPSolveInfo SolveLpForBranching(); 243 244 // Helper method to fill reduced cost / dual ray reason in 'integer_reason'. 245 // Generates a set of IntegerLiterals explaining why the best solution can not 246 // be improved using reduced costs. This is used to generate explanations for 247 // both infeasibility and bounds deductions. 248 void FillReducedCostReasonIn(const glop::DenseRow& reduced_costs, 249 std::vector<IntegerLiteral>* integer_reason); 250 251 // Reinitialize the LP from a potentially new set of constraints. 252 // This fills all data structure and properly rescale the underlying LP. 253 // 254 // Returns false if the problem is UNSAT (it can happen when presolve is off 255 // and some LP constraint are trivially false). 256 bool CreateLpFromConstraintManager(); 257 258 // Solve the LP, returns false if something went wrong in the LP solver. 259 bool SolveLp(); 260 261 // Add a "MIR" cut obtained by first taking the linear combination of the 262 // row of the matrix according to "integer_multipliers" and then trying 263 // some integer rounding heuristic. 264 // 265 // Return true if a new cut was added to the cut manager. 266 bool AddCutFromConstraints( 267 const std::string& name, 268 const std::vector<std::pair<glop::RowIndex, IntegerValue>>& 269 integer_multipliers); 270 271 // Second half of AddCutFromConstraints(). 272 bool PostprocessAndAddCut( 273 const std::string& name, const std::string& info, 274 IntegerVariable first_new_var, IntegerVariable first_slack, 275 const std::vector<ImpliedBoundsProcessor::SlackInfo>& ib_slack_infos, 276 LinearConstraint* cut); 277 278 // Computes and adds the corresponding type of cuts. 279 // This can currently only be called at the root node. 280 void AddObjectiveCut(); 281 void AddCGCuts(); 282 void AddMirCuts(); 283 void AddZeroHalfCuts(); 284 285 // Updates the bounds of the LP variables from the CP bounds. 286 void UpdateBoundsOfLpVariables(); 287 288 // Use the dual optimal lp values to compute an EXACT lower bound on the 289 // objective. Fills its reason and perform reduced cost strenghtening. 290 // Returns false in case of conflict. 291 bool ExactLpReasonning(); 292 293 // Same as FillDualRayReason() but perform the computation EXACTLY. Returns 294 // false in the case that the problem is not provably infeasible with exact 295 // computations, true otherwise. 296 bool FillExactDualRayReason(); 297 298 // Returns number of non basic variables with zero reduced costs. 299 int64_t CalculateDegeneracy(); 300 301 // From a set of row multipliers (at LP scale), scale them back to the CP 302 // world and then make them integer (eventually multiplying them by a new 303 // scaling factor returned in *scaling). 304 // 305 // Note that this will loose some precision, but our subsequent computation 306 // will still be exact as it will work for any set of multiplier. 307 std::vector<std::pair<glop::RowIndex, IntegerValue>> ScaleLpMultiplier( 308 bool take_objective_into_account, 309 const std::vector<std::pair<glop::RowIndex, double>>& lp_multipliers, 310 glop::Fractional* scaling, int max_pow = 62) const; 311 312 // Computes from an integer linear combination of the integer rows of the LP a 313 // new constraint of the form "sum terms <= upper_bound". All computation are 314 // exact here. 315 // 316 // Returns false if we encountered any integer overflow. 317 bool ComputeNewLinearConstraint( 318 const std::vector<std::pair<glop::RowIndex, IntegerValue>>& 319 integer_multipliers, 320 ScatteredIntegerVector* scattered_vector, 321 IntegerValue* upper_bound) const; 322 323 // Simple heuristic to try to minimize |upper_bound - ImpliedLB(terms)|. This 324 // should make the new constraint tighter and correct a bit the imprecision 325 // introduced by rounding the floating points values. 326 void AdjustNewLinearConstraint( 327 std::vector<std::pair<glop::RowIndex, IntegerValue>>* integer_multipliers, 328 ScatteredIntegerVector* scattered_vector, 329 IntegerValue* upper_bound) const; 330 331 // Shortcut for an integer linear expression type. 332 using LinearExpression = std::vector<std::pair<glop::ColIndex, IntegerValue>>; 333 334 // Converts a dense representation of a linear constraint to a sparse one 335 // expressed in terms of IntegerVariable. 336 void ConvertToLinearConstraint( 337 const absl::StrongVector<glop::ColIndex, IntegerValue>& dense_vector, 338 IntegerValue upper_bound, LinearConstraint* result); 339 340 // Compute the implied lower bound of the given linear expression using the 341 // current variable bound. Return kMinIntegerValue in case of overflow. 342 IntegerValue GetImpliedLowerBound(const LinearConstraint& terms) const; 343 344 // Tests for possible overflow in the propagation of the given linear 345 // constraint. 346 bool PossibleOverflow(const LinearConstraint& constraint); 347 348 // Reduce the coefficient of the constraint so that we cannot have overflow 349 // in the propagation of the given linear constraint. Note that we may loose 350 // some strength by doing so. 351 // 352 // We make sure that any partial sum involving any variable value in their 353 // domain do not exceed 2 ^ max_pow. 354 void PreventOverflow(LinearConstraint* constraint, int max_pow = 62); 355 356 // Fills integer_reason_ with the reason for the implied lower bound of the 357 // given linear expression. We relax the reason if we have some slack. 358 void SetImpliedLowerBoundReason(const LinearConstraint& terms, 359 IntegerValue slack); 360 361 // Fills the deductions vector with reduced cost deductions that can be made 362 // from the current state of the LP solver. The given delta should be the 363 // difference between the cp objective upper bound and lower bound given by 364 // the lp. 365 void ReducedCostStrengtheningDeductions(double cp_objective_delta); 366 367 // Returns the variable value on the same scale as the CP variable value. 368 glop::Fractional GetVariableValueAtCpScale(glop::ColIndex var); 369 370 // Gets or creates an LP variable that mirrors a CP variable. 371 // The variable should be a positive reference. 372 glop::ColIndex GetOrCreateMirrorVariable(IntegerVariable positive_variable); 373 374 // This must be called on an OPTIMAL LP and will update the data for 375 // LPReducedCostAverageDecision(). 376 void UpdateAverageReducedCosts(); 377 378 // Callback underlying LPReducedCostAverageBranching(). 379 IntegerLiteral LPReducedCostAverageDecision(); 380 381 // Updates the simplex iteration limit for the next visit. 382 // As per current algorithm, we use a limit which is dependent on size of the 383 // problem and drop it significantly if degeneracy is detected. We use 384 // DUAL_FEASIBLE status as a signal to correct the prediction. The next limit 385 // is capped by 'min_iter' and 'max_iter'. Note that this is enabled only for 386 // linearization level 2 and above. 387 void UpdateSimplexIterationLimit(const int64_t min_iter, 388 const int64_t max_iter); 389 390 // This epsilon is related to the precision of the value/reduced_cost returned 391 // by the LP once they have been scaled back into the CP domain. So for large 392 // domain or cost coefficient, we may have some issues. 393 static constexpr double kCpEpsilon = 1e-4; 394 395 // Same but at the LP scale. 396 static constexpr double kLpEpsilon = 1e-6; 397 398 // Anything coming from the LP with a magnitude below that will be assumed to 399 // be zero. 400 static constexpr double kZeroTolerance = 1e-12; 401 402 // Class responsible for managing all possible constraints that may be part 403 // of the LP. 404 LinearConstraintManager constraint_manager_; 405 406 // Initial problem in integer form. 407 // We always sort the inner vectors by increasing glop::ColIndex. 408 struct LinearConstraintInternal { 409 IntegerValue lb; 410 IntegerValue ub; 411 LinearExpression terms; 412 }; 413 LinearExpression integer_objective_; 414 IntegerValue integer_objective_offset_ = IntegerValue(0); 415 IntegerValue objective_infinity_norm_ = IntegerValue(0); 416 absl::StrongVector<glop::RowIndex, LinearConstraintInternal> integer_lp_; 417 absl::StrongVector<glop::RowIndex, IntegerValue> infinity_norms_; 418 419 // Underlying LP solver API. 420 glop::LinearProgram lp_data_; 421 glop::RevisedSimplex simplex_; 422 int64_t next_simplex_iter_ = 500; 423 424 // For the scaling. 425 glop::LpScalingHelper scaler_; 426 427 // Temporary data for cuts. 428 ZeroHalfCutHelper zero_half_cut_helper_; 429 CoverCutHelper cover_cut_helper_; 430 IntegerRoundingCutHelper integer_rounding_cut_helper_; 431 LinearConstraint cut_; 432 433 ScatteredIntegerVector tmp_scattered_vector_; 434 435 std::vector<double> tmp_lp_values_; 436 std::vector<IntegerValue> tmp_var_lbs_; 437 std::vector<IntegerValue> tmp_var_ubs_; 438 std::vector<glop::RowIndex> tmp_slack_rows_; 439 std::vector<IntegerValue> tmp_slack_bounds_; 440 441 // Used by ScaleLpMultiplier(). 442 mutable std::vector<std::pair<glop::RowIndex, double>> tmp_cp_multipliers_; 443 444 // Structures used for mirroring IntegerVariables inside the underlying LP 445 // solver: an integer variable var is mirrored by mirror_lp_variable_[var]. 446 // Note that these indices are dense in [0, mirror_lp_variable_.size()] so 447 // they can be used as vector indices. 448 // 449 // TODO(user): This should be absl::StrongVector<glop::ColIndex, 450 // IntegerVariable>. 451 std::vector<IntegerVariable> integer_variables_; 452 absl::flat_hash_map<IntegerVariable, glop::ColIndex> mirror_lp_variable_; 453 454 // We need to remember what to optimize if an objective is given, because 455 // then we will switch the objective between feasibility and optimization. 456 bool objective_is_defined_ = false; 457 IntegerVariable objective_cp_; 458 459 // Singletons from Model. 460 const SatParameters& parameters_; 461 Model* model_; 462 TimeLimit* time_limit_; 463 IntegerTrail* integer_trail_; 464 Trail* trail_; 465 IntegerEncoder* integer_encoder_; 466 ModelRandomGenerator* random_; 467 468 // Used while deriving cuts. 469 ImpliedBoundsProcessor implied_bounds_processor_; 470 471 // The dispatcher for all LP propagators of the model, allows to find which 472 // LinearProgrammingConstraint has a given IntegerVariable. 473 LinearProgrammingDispatcher* dispatcher_; 474 475 std::vector<IntegerLiteral> integer_reason_; 476 std::vector<IntegerLiteral> deductions_; 477 std::vector<IntegerLiteral> deductions_reason_; 478 479 // Repository of IntegerSumLE that needs to be kept around for the lazy 480 // reasons. Those are new integer constraint that are created each time we 481 // solve the LP to a dual-feasible solution. Propagating these constraints 482 // both improve the objective lower bound but also perform reduced cost 483 // fixing. 484 int rev_optimal_constraints_size_ = 0; 485 std::vector<std::unique_ptr<IntegerSumLE>> optimal_constraints_; 486 487 // Last OPTIMAL solution found by a call to the underlying LP solver. 488 // On IncrementalPropagate(), if the bound updates do not invalidate this 489 // solution, Propagate() will not find domain reductions, no need to call it. 490 int lp_solution_level_ = 0; 491 bool lp_solution_is_set_ = false; 492 bool lp_solution_is_integer_ = false; 493 double lp_objective_; 494 std::vector<double> lp_solution_; 495 std::vector<double> lp_reduced_cost_; 496 497 // If non-empty, this is the last known optimal lp solution at root-node. If 498 // the variable bounds changed, or cuts where added, it is possible that this 499 // solution is no longer optimal though. 500 std::vector<double> level_zero_lp_solution_; 501 502 // True if the last time we solved the exact same LP at level zero, no cuts 503 // and no lazy constraints where added. 504 bool lp_at_level_zero_is_final_ = false; 505 506 // Same as lp_solution_ but this vector is indexed differently. 507 LinearProgrammingConstraintLpSolution& expanded_lp_solution_; 508 509 // Linear constraints cannot be created or modified after this is registered. 510 bool lp_constraint_is_registered_ = false; 511 512 std::vector<CutGenerator> cut_generators_; 513 514 // Store some statistics for HeuristicLPReducedCostAverage(). 515 bool compute_reduced_cost_averages_ = false; 516 int num_calls_since_reduced_cost_averages_reset_ = 0; 517 std::vector<double> sum_cost_up_; 518 std::vector<double> sum_cost_down_; 519 std::vector<int> num_cost_up_; 520 std::vector<int> num_cost_down_; 521 std::vector<double> rc_scores_; 522 523 // All the entries before rev_rc_start_ in the sorted positions correspond 524 // to fixed variables and can be ignored. 525 int rev_rc_start_ = 0; 526 RevRepository<int> rc_rev_int_repository_; 527 std::vector<std::pair<double, int>> positions_by_decreasing_rc_score_; 528 529 // Defined as average number of nonbasic variables with zero reduced costs. 530 IncrementalAverage average_degeneracy_; 531 bool is_degenerate_ = false; 532 533 // Used by the strong branching heuristic. 534 int branching_frequency_ = 1; 535 int64_t count_since_last_branching_ = 0; 536 537 // Sum of all simplex iterations performed by this class. This is useful to 538 // test the incrementality and compare to other solvers. 539 int64_t total_num_simplex_iterations_ = 0; 540 541 // Some stats on the LP statuses encountered. 542 int64_t num_solves_ = 0; 543 std::vector<int64_t> num_solves_by_status_; 544 }; 545 546 // A class that stores which LP propagator is associated to each variable. 547 // We need to give the hash_map a name so it can be used as a singleton in our 548 // model. 549 // 550 // Important: only positive variable do appear here. 551 class LinearProgrammingDispatcher 552 : public absl::flat_hash_map<IntegerVariable, 553 LinearProgrammingConstraint*> { 554 public: LinearProgrammingDispatcher(Model * model)555 explicit LinearProgrammingDispatcher(Model* model) {} 556 }; 557 558 // A class that stores the collection of all LP constraints in a model. 559 class LinearProgrammingConstraintCollection 560 : public std::vector<LinearProgrammingConstraint*> { 561 public: LinearProgrammingConstraintCollection()562 LinearProgrammingConstraintCollection() {} 563 }; 564 565 // Cut generator for the circuit constraint, where in any feasible solution, the 566 // arcs that are present (variable at 1) must form a circuit through all the 567 // nodes of the graph. Self arc are forbidden in this case. 568 // 569 // In more generality, this currently enforce the resulting graph to be strongly 570 // connected. Note that we already assume basic constraint to be in the lp, so 571 // we do not add any cuts for components of size 1. 572 CutGenerator CreateStronglyConnectedGraphCutGenerator( 573 int num_nodes, const std::vector<int>& tails, const std::vector<int>& heads, 574 const std::vector<Literal>& literals, Model* model); 575 576 // Almost the same as CreateStronglyConnectedGraphCutGenerator() but for each 577 // components, computes the demand needed to serves it, and depending on whether 578 // it contains the depot (node zero) or not, compute the minimum number of 579 // vehicle that needs to cross the component border. 580 CutGenerator CreateCVRPCutGenerator(int num_nodes, 581 const std::vector<int>& tails, 582 const std::vector<int>& heads, 583 const std::vector<Literal>& literals, 584 const std::vector<int64_t>& demands, 585 int64_t capacity, Model* model); 586 } // namespace sat 587 } // namespace operations_research 588 589 #endif // OR_TOOLS_SAT_LINEAR_PROGRAMMING_CONSTRAINT_H_ 590