OR-Tools  8.2
feasibility_pump.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_FEASIBILITY_PUMP_H_
15 #define OR_TOOLS_SAT_FEASIBILITY_PUMP_H_
16 
23 #include "ortools/sat/integer.h"
25 #include "ortools/sat/sat_solver.h"
27 #include "ortools/sat/util.h"
28 
29 namespace operations_research {
30 namespace sat {
31 
33  public:
34  explicit FeasibilityPump(Model* model);
36 
37  typedef glop::RowIndex ConstraintIndex;
38 
39  void SetMaxFPIterations(int max_iter) {
40  max_fp_iterations_ = std::max(1, max_iter);
41  }
42 
43  // Add a new linear constraint to this LP.
45 
46  // Set the coefficient of the variable in the objective. Calling it twice will
47  // overwrite the previous value. Note that this doesn't set the objective
48  // coefficient if the variable doesn't appear in any constraints. So this has
49  // to be called after all the constraints are added.
50  void SetObjectiveCoefficient(IntegerVariable ivar, IntegerValue coeff);
51 
52  // Returns the LP value of a variable in the current
53  // solution. These functions should only be called when HasSolution() is true.
54  bool HasLPSolution() const { return lp_solution_is_set_; }
55  double LPSolutionObjectiveValue() const { return lp_objective_; }
56  double GetLPSolutionValue(IntegerVariable variable) const;
57  bool LPSolutionIsInteger() const { return lp_solution_is_integer_; }
58  double LPSolutionFractionality() const { return lp_solution_fractionality_; }
59 
60  // Returns the Integer solution value of a variable in the current rounded
61  // solution. These functions should only be called when HasIntegerSolution()
62  // is true.
63  bool HasIntegerSolution() const { return integer_solution_is_set_; }
65  return integer_solution_objective_;
66  }
68  return integer_solution_is_feasible_;
69  }
70  int64 GetIntegerSolutionValue(IntegerVariable variable) const;
71 
72  // Returns false if the model is proven to be infeasible.
73  bool Solve();
74 
75  private:
76  // Solve the LP, returns false if something went wrong in the LP solver.
77  bool SolveLp();
78 
79  // Calls the specified rounding method in the parameters. Returns false if the
80  // rounding couldn't be finished.
81  bool Round();
82 
83  // Round the fractional LP solution values to nearest integer values. This
84  // rounding always finishes so always returns true.
85  bool NearestIntegerRounding();
86 
87  // Counts the number of up and down locks as defined below.
88  // #up_locks = #upper bounded constraints with positive coeff for var
89  // + #lower bounded constraints with negative coeff for var.
90  // #down_locks = #lower bounded constraints with positive coeff for var
91  // + #upper bounded constraints with negative coeff for var.
92  // Rounds the variable in the direction of lesser locks. When the
93  // fractionality is low (less than 0.1), this reverts to nearest integer
94  // rounding to avoid rounding almost integer values in wrong direction.
95  // This rounding always finishes so always returns true.
96  bool LockBasedRounding();
97 
98  // Similar to LockBasedRounding except this only considers locks of active
99  // constraints.
100  bool ActiveLockBasedRounding();
101 
102  // This is expensive rounding algorithm. We round variables one by one and
103  // propagate the bounds in between. If none of the rounded values fall in
104  // the continuous domain specified by lower and upper bound, we use the
105  // current lower/upper bound (whichever one is closest) instead of rounding
106  // the fractional lp solution value. If both the rounded values are in the
107  // domain, we round to nearest integer. This idea was presented in the paper
108  // "Feasibility pump 2.0" (2009) by Matteo Fischetti, Domenico Salvagnin.
109  //
110  // This rounding might not finish either because the time limit is reached or
111  // the model is detected to be unsat. Returns false in those cases.
112  bool PropagationRounding();
113 
114  void FillIntegerSolutionStats();
115 
116  // Loads the lp_data_.
117  void InitializeWorkingLP();
118 
119  // Changes the LP objective and bounds of the norm constraints so the new
120  // objective also tries to minimize the distance to the rounded solution.
121  void L1DistanceMinimize();
122 
123  // Stores the solutions in the shared repository. Stores LP solution if it is
124  // integer and stores the integer solution if it is feasible.
125  void MaybePushToRepo();
126 
127  void PrintStats();
128 
129  // Returns the variable value on the same scale as the CP variable value.
130  double GetVariableValueAtCpScale(glop::ColIndex var);
131 
132  // Shortcut for an integer linear expression type.
133  using LinearExpression = std::vector<std::pair<glop::ColIndex, IntegerValue>>;
134 
135  // Gets or creates an LP variable that mirrors a model variable.
136  // The variable should be a positive reference.
137  glop::ColIndex GetOrCreateMirrorVariable(IntegerVariable positive_variable);
138 
139  // Updates the bounds of the LP variables from the CP bounds.
140  void UpdateBoundsOfLpVariables();
141 
142  // This epsilon is related to the precision of the value returned by the LP
143  // once they have been scaled back into the CP domain. So for large domain or
144  // cost coefficient, we may have some issues.
145  static const double kCpEpsilon;
146 
147  // Initial problem in integer form.
148  // We always sort the inner vectors by increasing glop::ColIndex.
149  struct LinearConstraintInternal {
150  IntegerValue lb;
151  IntegerValue ub;
152  LinearExpression terms;
153  };
154  LinearExpression integer_objective_;
155  IntegerValue objective_infinity_norm_ = IntegerValue(0);
156  double objective_normalization_factor_ = 0.0;
157  double mixing_factor_ = 1.0;
158 
160  int model_vars_size_ = 0;
161 
162  // Underlying LP solver API.
163  glop::LinearProgram lp_data_;
164  glop::RevisedSimplex simplex_;
165 
166  glop::ColMapping norm_variables_;
167  glop::ColToRowMapping norm_lhs_constraints_;
168  glop::ColToRowMapping norm_rhs_constraints_;
169 
170  // For the scaling.
171  glop::LpScalingHelper scaler_;
172 
173  // Structures used for mirroring IntegerVariables inside the underlying LP
174  // solver: an integer variable var is mirrored by mirror_lp_variable_[var].
175  // Note that these indices are dense in [0, mirror_lp_variable_.size()] so
176  // they can be used as vector indices.
177  std::vector<IntegerVariable> integer_variables_;
178  absl::flat_hash_map<IntegerVariable, glop::ColIndex> mirror_lp_variable_;
179 
180  // True if the variable was binary before we apply scaling.
181  std::vector<bool> var_is_binary_;
182 
183  // The following lock information is computed only once.
184  // Number of constraints restricting variable to take higher (resp. lower)
185  // values.
186  std::vector<int> var_up_locks_;
187  std::vector<int> var_down_locks_;
188 
189  // We need to remember what to optimize if an objective is given, because
190  // then we will switch the objective between feasibility and optimization.
191  bool objective_is_defined_ = false;
192 
193  // Singletons from Model.
194  const SatParameters& sat_parameters_;
195  TimeLimit* time_limit_;
196  IntegerTrail* integer_trail_;
197  Trail* trail_;
198  IntegerEncoder* integer_encoder_;
199  SharedIncompleteSolutionManager* incomplete_solutions_;
200  SatSolver* sat_solver_;
201  IntegerDomains* domains_;
202  const CpModelMapping* mapping_;
203 
204  // Last OPTIMAL/Feasible solution found by a call to the underlying LP solver.
205  bool lp_solution_is_set_ = false;
206  bool lp_solution_is_integer_ = false;
207  double lp_objective_;
208  std::vector<double> lp_solution_;
209  std::vector<double> best_lp_solution_;
210  // We use max fractionality of all variables.
211  double lp_solution_fractionality_;
212 
213  // Rounded Integer solution. This might not be feasible.
214  bool integer_solution_is_set_ = false;
215  bool integer_solution_is_feasible_ = false;
216  int64 integer_solution_objective_;
217  std::vector<int64> integer_solution_;
218  std::vector<int64> best_integer_solution_;
219  int num_infeasible_constraints_;
220  // We use max infeasibility of all constraints.
221  int64 integer_solution_infeasibility_;
222 
223  // Sum of all simplex iterations performed by this class. This is useful to
224  // test the incrementality and compare to other solvers.
225  int64 total_num_simplex_iterations_ = 0;
226 
227  // TODO(user): Tune default value. Expose as parameter.
228  int max_fp_iterations_ = 20;
229 
230  bool model_is_unsat_ = false;
231 };
232 
233 } // namespace sat
234 } // namespace operations_research
235 
236 #endif // OR_TOOLS_SAT_FEASIBILITY_PUMP_H_
int64 max
Definition: alldiff_cst.cc:139
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
Definition: time_limit.h:105
double GetLPSolutionValue(IntegerVariable variable) const
int64 GetIntegerSolutionValue(IntegerVariable variable) const
void AddLinearConstraint(const LinearConstraint &ct)
void SetObjectiveCoefficient(IntegerVariable ivar, IntegerValue coeff)
Class that owns everything related to a particular optimization model.
Definition: sat/model.h:38
const Constraint * ct
IntVar * var
Definition: expr_array.cc:1858
GRBmodel * model
int64_t int64
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...