OR-Tools  8.2
lp_solver.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_GLOP_LP_SOLVER_H_
15#define OR_TOOLS_GLOP_LP_SOLVER_H_
16
17#include <memory>
18
19#include "ortools/glop/parameters.pb.h"
24
25namespace operations_research {
26namespace glop {
27
28// A full-fledged linear programming solver.
29class LPSolver {
30 public:
31 LPSolver();
32
33 // Sets and gets the solver parameters.
34 // See the proto for an extensive documentation.
35 void SetParameters(const GlopParameters& parameters);
36 const GlopParameters& GetParameters() const;
37 GlopParameters* GetMutableParameters();
38
39 // Solves the given linear program and returns the solve status. See the
40 // ProblemStatus documentation for a description of the different values.
41 //
42 // The solution can be retrieved afterwards using the getter functions below.
43 // Note that depending on the returned ProblemStatus the solution values may
44 // not mean much, so it is important to check the returned status.
45 //
46 // Incrementality: From one Solve() call to the next, the internal state is
47 // not cleared and the solver may take advantage of its current state if the
48 // given lp is only slightly modified. If the modification is too important,
49 // or if the solver does not see how to reuse the previous state efficiently,
50 // it will just solve the problem from scratch. On the other hand, if the lp
51 // is the same, calling Solve() again should basically resume the solve from
52 // the last position. To disable this behavior, simply call Clear() before.
53 ABSL_MUST_USE_RESULT ProblemStatus Solve(const LinearProgram& lp);
54
55 // Same as Solve() but use the given time limit rather than constructing a new
56 // one from the current GlopParameters.
57 ABSL_MUST_USE_RESULT ProblemStatus SolveWithTimeLimit(const LinearProgram& lp,
59
60 // Puts the solver in a clean state.
61 //
62 // Calling Solve() for the first time, or calling Clear() then Solve() on the
63 // same problem is guaranted to be deterministic and to always give the same
64 // result, assuming that no time limit was specified.
65 void Clear();
66
67 // Advanced usage. This should be called before calling Solve(). It will
68 // configure the solver to try to start from the given point for the next
69 // Solve() only. Note that calling Clear() will invalidate this information.
70 //
71 // If the set of variables/constraints with a BASIC status does not form a
72 // basis a warning will be logged and the code will ignore it. Otherwise, the
73 // non-basic variables will be initialized to their given status and solving
74 // will start from there (even if the solution is not primal/dual feasible).
75 //
76 // Important: There is no facility to transform this information in sync with
77 // presolve. So you should probably disable presolve when using this since
78 // otherwise there is a good chance that the matrix will change and that the
79 // given basis will make no sense. Even worse if it happens to be factorizable
80 // but doesn't correspond to what was intended.
83
84 // This loads a given solution and computes related quantities so that the
85 // getters below will refer to it.
86 //
87 // Depending on the given solution status, this also checks the solution
88 // feasibility or optimality. The exact behavior and tolerances are controlled
89 // by the solver parameters. Because of this, the returned ProblemStatus may
90 // be changed from the one passed in the ProblemSolution to ABNORMAL or
91 // IMPRECISE. Note that this is the same logic as the one used by Solve() to
92 // verify the solver solution.
94 const ProblemSolution& solution);
95
96 // Returns the objective value of the solution with its offset and scaling.
98
99 // Accessors to information related to variables.
100 const DenseRow& variable_values() const { return primal_values_; }
101 const DenseRow& reduced_costs() const { return reduced_costs_; }
103 return variable_statuses_;
104 }
105
106 // Accessors to information related to constraints. The activity of a
107 // constraint is the sum of its linear terms evaluated with variables taking
108 // their values at the current solution.
109 //
110 // Note that the dual_values() do not take into account an eventual objective
111 // scaling of the solved LinearProgram.
112 const DenseColumn& dual_values() const { return dual_values_; }
114 return constraint_activities_;
115 }
117 return constraint_statuses_;
118 }
119
120 // Returns the primal maximum infeasibility of the solution.
121 // This indicates by how much the variable and constraint bounds are violated.
123
124 // Returns the dual maximum infeasibility of the solution.
125 // This indicates by how much the variable costs (i.e. objective) should be
126 // modified for the solution to be an exact optimal solution.
128
129 // Returns true if the solution status was OPTIMAL and it seems that there is
130 // more than one basic optimal solution. Note that this solver always returns
131 // an optimal BASIC solution and that there is only a finite number of them.
132 // Moreover, given one basic solution, since the basis is always refactorized
133 // at optimality before reporting the numerical result, then all the
134 // quantities (even the floating point ones) should be always the same.
135 //
136 // TODO(user): Test this behavior extensively if a client relies on it.
138
139 // Returns the number of simplex iterations used by the last Solve().
141
142 // Returns the "deterministic time" since the creation of the solver. Note
143 // That this time is only increased when some operations take place in this
144 // class.
145 //
146 // TODO(user): Currently, this is only modified when the simplex code is
147 // executed.
148 //
149 // TODO(user): Improve the correlation with the running time.
150 double DeterministicTime() const;
151
152 private:
153 // Resizes all the solution vectors to the given sizes.
154 // This is used in case of error to make sure all the getter functions will
155 // not crash when given row/col inside the initial linear program dimension.
156 void ResizeSolution(RowIndex num_rows, ColIndex num_cols);
157
158 // Make sure the primal and dual values are within their bounds in order to
159 // have a strong guarantee on the optimal solution. See
160 // provide_strong_optimal_guarantee in the GlopParameters proto.
161 void MovePrimalValuesWithinBounds(const LinearProgram& lp);
162 void MoveDualValuesWithinBounds(const LinearProgram& lp);
163
164 // Runs the revised simplex algorithm if needed (i.e. if the program was not
165 // already solved by the preprocessors).
166 void RunRevisedSimplexIfNeeded(ProblemSolution* solution,
168
169 // Checks that the returned solution values and statuses are consistent.
170 // Returns true if this is the case. See the code for the exact check
171 // performed.
172 bool IsProblemSolutionConsistent(const LinearProgram& lp,
173 const ProblemSolution& solution) const;
174
175 // Returns true if there may be multiple optimal solutions.
176 // The return value is true if:
177 // - a non-fixed variable, at one of its boumds, has its reduced
178 // cost close to zero.
179 // or if:
180 // - a non-equality constraint (i.e. l <= a.x <= r, with l != r), is at one of
181 // its bounds (a.x = r or a.x = l) and has its dual value close to zero.
182 bool IsOptimalSolutionOnFacet(const LinearProgram& lp);
183
184 // Computes derived quantities from the solution.
185 void ComputeReducedCosts(const LinearProgram& lp);
186 void ComputeConstraintActivities(const LinearProgram& lp);
187
188 // Computes the primal/dual objectives (without the offset). Note that the
189 // dual objective needs the reduced costs in addition to the dual values.
190 double ComputeObjective(const LinearProgram& lp);
191 double ComputeDualObjective(const LinearProgram& lp);
192
193 // Given a relative precision on the primal values of up to
194 // solution_feasibility_tolerance(), this returns an upper bound on the
195 // expected precision of the objective.
196 double ComputeMaxExpectedObjectiveError(const LinearProgram& lp);
197
198 // Returns the max absolute cost pertubation (resp. rhs perturbation) so that
199 // the pair (primal values, dual values) is an EXACT optimal solution to the
200 // perturbed problem. Note that this assumes that
201 // MovePrimalValuesWithinBounds() and MoveDualValuesWithinBounds() have
202 // already been called. The Boolean is_too_large is set to true if any of the
203 // perturbation exceed the tolerance (which depends of the coordinate).
204 //
205 // These bounds are computed using the variable and constraint statuses by
206 // enforcing the complementary slackness optimal conditions. Note that they
207 // are almost the same as ComputeActivityInfeasibility() and
208 // ComputeReducedCostInfeasibility() but looks for optimality rather than just
209 // feasibility.
210 //
211 // Note(user): We could get EXACT bounds on these perturbations by changing
212 // the rounding mode appropriately during these computations. But this is
213 // probably not needed.
214 Fractional ComputeMaxCostPerturbationToEnforceOptimality(
215 const LinearProgram& lp, bool* is_too_large);
216 Fractional ComputeMaxRhsPerturbationToEnforceOptimality(
217 const LinearProgram& lp, bool* is_too_large);
218
219 // Computes the maximum of the infeasibilities associated with each values.
220 // The returned infeasibilities are the maximum of the "absolute" errors of
221 // each vector coefficients.
222 //
223 // These function also set is_too_large to true if any infeasibility is
224 // greater than the tolerance (which depends of the coordinate).
225 double ComputePrimalValueInfeasibility(const LinearProgram& lp,
226 bool* is_too_large);
227 double ComputeActivityInfeasibility(const LinearProgram& lp,
228 bool* is_too_large);
229 double ComputeDualValueInfeasibility(const LinearProgram& lp,
230 bool* is_too_large);
231 double ComputeReducedCostInfeasibility(const LinearProgram& lp,
232 bool* is_too_large);
233
234 // On a call to Solve(), this is initialized to an exact copy of the given
235 // linear program. It is later modified by the preprocessors and then solved
236 // by the revised simplex.
237 //
238 // This is not efficient memory-wise but allows to check optimality with
239 // respect to the given LinearProgram that is guaranteed to not have been
240 // modified. It also allows for a nicer Solve() API with a const
241 // LinearProgram& input.
242 LinearProgram current_linear_program_;
243
244 // The revised simplex solver.
245 std::unique_ptr<RevisedSimplex> revised_simplex_;
246
247 // The number of revised simplex iterations used by the last Solve().
248 int num_revised_simplex_iterations_;
249
250 // The current ProblemSolution.
251 // TODO(user): use a ProblemSolution directly?
252 DenseRow primal_values_;
253 DenseColumn dual_values_;
254 VariableStatusRow variable_statuses_;
255 ConstraintStatusColumn constraint_statuses_;
256
257 // Quantities computed from the solution and the linear program.
258 DenseRow reduced_costs_;
259 DenseColumn constraint_activities_;
260 Fractional problem_objective_value_;
261 bool may_have_multiple_solutions_;
262 Fractional max_absolute_primal_infeasibility_;
263 Fractional max_absolute_dual_infeasibility_;
264
265 // Proto holding all the parameters of the algorithm.
266 GlopParameters parameters_;
267
268 // The number of times Solve() was called. Used to number dump files.
269 int num_solves_;
270
271 DISALLOW_COPY_AND_ASSIGN(LPSolver);
272};
273
274} // namespace glop
275} // namespace operations_research
276
277#endif // OR_TOOLS_GLOP_LP_SOLVER_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
const GlopParameters & GetParameters() const
Definition: lp_solver.cc:117
void SetInitialBasis(const VariableStatusRow &variable_statuses, const ConstraintStatusColumn &constraint_statuses)
Definition: lp_solver.cc:230
bool MayHaveMultipleOptimalSolutions() const
Definition: lp_solver.cc:488
const DenseColumn & dual_values() const
Definition: lp_solver.h:112
const VariableStatusRow & variable_statuses() const
Definition: lp_solver.h:102
GlopParameters * GetMutableParameters()
Definition: lp_solver.cc:119
Fractional GetMaximumDualInfeasibility() const
Definition: lp_solver.cc:484
const ConstraintStatusColumn & constraint_statuses() const
Definition: lp_solver.h:116
Fractional GetMaximumPrimalInfeasibility() const
Definition: lp_solver.cc:480
Fractional GetObjectiveValue() const
Definition: lp_solver.cc:476
ProblemStatus LoadAndVerifySolution(const LinearProgram &lp, const ProblemSolution &solution)
Definition: lp_solver.cc:284
const DenseRow & variable_values() const
Definition: lp_solver.h:100
const DenseRow & reduced_costs() const
Definition: lp_solver.h:101
ABSL_MUST_USE_RESULT ProblemStatus Solve(const LinearProgram &lp)
Definition: lp_solver.cc:121
ABSL_MUST_USE_RESULT ProblemStatus SolveWithTimeLimit(const LinearProgram &lp, TimeLimit *time_limit)
Definition: lp_solver.cc:127
void SetParameters(const GlopParameters &parameters)
Definition: lp_solver.cc:113
const DenseColumn & constraint_activities() const
Definition: lp_solver.h:113
SatParameters parameters
SharedTimeLimit * time_limit
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...