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"
27#include "ortools/sat/util.h"
28
29namespace operations_research {
30namespace 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...