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"
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
40namespace operations_research {
41namespace 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.
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.
127class LinearProgrammingDispatcher;
130 public:
131 typedef glop::RowIndex ConstraintIndex;
132
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.
561CutGenerator 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)
bool AddLinearExpressionMultiple(IntegerValue multiplier, const std::vector< std::pair< glop::ColIndex, IntegerValue > > &terms)
std::vector< std::pair< glop::ColIndex, IntegerValue > > GetTerms()
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