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