OR-Tools  8.2
cp_model_postsolve.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_CP_MODEL_POSTSOLVE_H_
15 #define OR_TOOLS_SAT_CP_MODEL_POSTSOLVE_H_
16 
17 #include <vector>
18 
20 #include "ortools/sat/cp_model.pb.h"
21 
22 namespace operations_research {
23 namespace sat {
24 
25 // Postsolves the given response using information filled by our presolver.
26 //
27 // This works as follow:
28 // - First we fix fixed variables of the mapping_model according to the solution
29 // of the presolved problem and the index mapping.
30 // - Then, we process the mapping constraints in "reverse" order, and unit
31 // propagate each of them when necessary. By construction this should never
32 // give rise to any conflicts. And after each constraints, we should have
33 // a feasible solution to the presolved problem + all already postsolved
34 // constraints. This is the invariant we maintain.
35 // - Finally, we arbitrarily fix any free variables left and update the given
36 // response with the new solution.
37 //
38 // Note: Most of the postsolve operations require the constraints to have been
39 // written in the correct way by the presolve.
40 //
41 // TODO(user): We could use the search strategy to fix free variables to some
42 // chosen values? The feature might never be needed though.
43 void PostsolveResponse(const int64 num_variables_in_original_model,
44  const CpModelProto& mapping_proto,
45  const std::vector<int>& postsolve_mapping,
46  CpSolverResponse* response);
47 
48 } // namespace sat
49 } // namespace operations_research
50 
51 #endif // OR_TOOLS_SAT_CP_MODEL_POSTSOLVE_H_
SharedResponseManager * response
int64_t int64
void PostsolveResponse(const int64 num_variables_in_original_model, const CpModelProto &mapping_proto, const std::vector< int > &postsolve_mapping, CpSolverResponse *response)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...