DotNet Reference

.Net Reference

CpSolver.cs
Go to the documentation of this file.
1// Copyright 2010-2021 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
14using System;
15using System.Collections.Generic;
16using System.Runtime.CompilerServices;
17
18namespace Google.OrTools.Sat
19{
29public class CpSolver
30{
32 public CpSolverStatus Solve(CpModel model, SolutionCallback cb = null)
33 {
34 // Setup search.
35 CreateSolveWrapper();
36 if (string_parameters_ is not null)
37 {
38 solve_wrapper_.SetStringParameters(string_parameters_);
39 }
40 if (log_callback_ is not null)
41 {
42 solve_wrapper_.AddLogCallbackFromClass(log_callback_);
43 }
44 if (cb is not null)
45 {
46 solve_wrapper_.AddSolutionCallback(cb);
47 }
48
49 response_ = solve_wrapper_.Solve(model.Model);
50
51 // Cleanup search.
52 if (cb is not null)
53 {
54 solve_wrapper_.ClearSolutionCallback(cb);
55 }
56 ReleaseSolveWrapper();
57
58 return response_.Status;
59 }
60
62 [ObsoleteAttribute("This method is obsolete. Call Solve instead.", false)]
63 public CpSolverStatus SolveWithSolutionCallback(CpModel model, SolutionCallback cb)
64 {
65 return Solve(model, cb);
66 }
67
69 [ObsoleteAttribute("This method is obsolete. Call Solve instead with the enumerate_all_solutions parameter.",
70 false)]
71 public CpSolverStatus SearchAllSolutions(CpModel model, SolutionCallback cb)
72 {
73 string old_parameters = string_parameters_;
74 string_parameters_ += " enumerate_all_solutions:true";
75 Solve(model, cb);
76 string_parameters_ = old_parameters;
77 return response_.Status;
78 }
79
81 [MethodImpl(MethodImplOptions.Synchronized)]
82 public void StopSearch()
83 {
84 if (solve_wrapper_ is not null)
85 {
86 solve_wrapper_.StopSearch();
87 }
88 }
89
90 [MethodImpl(MethodImplOptions.Synchronized)]
91 private void CreateSolveWrapper()
92 {
93 solve_wrapper_ = new SolveWrapper();
94 }
95
96 [MethodImpl(MethodImplOptions.Synchronized)]
97 private void ReleaseSolveWrapper()
98 {
99 solve_wrapper_ = null;
100 }
101
103 public String ResponseStats()
104 {
105 return CpSatHelper.SolverResponseStats(response_);
106 }
107
109 public double ObjectiveValue
110 {
111 get {
112 return response_.ObjectiveValue;
113 }
114 }
115
121 public double BestObjectiveBound
122 {
123 get {
124 return response_.BestObjectiveBound;
125 }
126 }
127
129 public string StringParameters
130 {
131 get {
132 return string_parameters_;
133 }
134 set {
135 string_parameters_ = value;
136 }
137 }
138
139 public void SetLogCallback(StringToVoidDelegate del)
140 {
141 log_callback_ = new LogCallbackDelegate(del);
142 }
143
144 public CpSolverResponse Response
145 {
146 get {
147 return response_;
148 }
149 }
150
156 public long Value(IntVar intVar)
157 {
158 int index = intVar.GetIndex();
159 long value = index >= 0 ? response_.Solution[index] : -response_.Solution[-index - 1];
160 return value;
161 }
162
168 public long Value(LinearExpr e)
169 {
170 long constant = 0;
171 long coefficient = 1;
172 LinearExpr expr = e;
173 if (terms_ is null)
174 {
175 terms_ = new Queue<Term>();
176 }
177 else
178 {
179 terms_.Clear();
180 }
181
182 do
183 {
184 switch (expr)
185 {
186 case LinearExprBuilder a:
187 constant += coefficient * a.Offset;
188 if (coefficient == 1)
189 {
190 foreach (Term sub in a.Terms)
191 {
192 terms_.Enqueue(sub);
193 }
194 }
195 else
196 {
197 foreach (Term sub in a.Terms)
198 {
199 terms_.Enqueue(new Term(sub.expr, sub.coefficient * coefficient));
200 }
201 }
202 break;
203 case IntVar intVar:
204 int index = intVar.GetIndex();
205 long value = index >= 0 ? response_.Solution[index] : -response_.Solution[-index - 1];
206 constant += coefficient * value;
207 break;
208 case NotBoolVar:
209 throw new ArgumentException("Cannot evaluate a literal in an integer expression.");
210 default:
211 throw new ArgumentException("Cannot evaluate '" + expr + "' in an integer expression");
212 }
213
214 if (!terms_.TryDequeue(out var term))
215 {
216 break;
217 }
218 expr = term.expr;
219 coefficient = term.coefficient;
220 } while (true);
221
222 return constant;
223 }
224
230 public Boolean BooleanValue(ILiteral literal)
231 {
232 if (literal is BoolVar || literal is NotBoolVar)
233 {
234 int index = literal.GetIndex();
235 if (index >= 0)
236 {
237 return response_.Solution[index] != 0;
238 }
239 else
240 {
241 return response_.Solution[-index - 1] == 0;
242 }
243 }
244 else
245 {
246 throw new ArgumentException("Cannot evaluate '" + literal.ToString() + "' as a boolean literal");
247 }
248 }
249
251 public long NumBranches()
252 {
253 return response_.NumBranches;
254 }
255
257 public long NumConflicts()
258 {
259 return response_.NumConflicts;
260 }
261
263 public double WallTime()
264 {
265 return response_.WallTime;
266 }
267
269 {
270 return response_.SufficientAssumptionsForInfeasibility;
271 }
272
279 public String SolutionInfo()
280 {
281 return response_.SolutionInfo;
282 }
283
284 private CpSolverResponse response_;
285 private LogCallback log_callback_;
286 private string string_parameters_;
287 private SolveWrapper solve_wrapper_;
288 private Queue<Term> terms_;
289}
290
291class LogCallbackDelegate : LogCallback
292{
293 public LogCallbackDelegate(StringToVoidDelegate del)
294 {
295 this.delegate_ = del;
296 }
297
298 public override void NewMessage(string message)
299 {
300 delegate_(message);
301 }
302
303 private StringToVoidDelegate delegate_;
304}
305
306} // namespace Google.OrTools.Sat
Holds a Boolean variable.
Wrapper class around the cp_model proto.
Definition: CpModel.cs:24
CpModelProto Model
The underlying CpModelProto.
Definition: CpModel.cs:41
Wrapper around the SAT solver.
Definition: CpSolver.cs:30
double WallTime()
Returns the wall time of the search.
Definition: CpSolver.cs:263
String ResponseStats()
Statistics on the solution found as a string.
Definition: CpSolver.cs:103
CpSolverStatus SolveWithSolutionCallback(CpModel model, SolutionCallback cb)
Deprecated, use Solve() instead.
Definition: CpSolver.cs:63
void StopSearch()
Stops the search asynchronously.
Definition: CpSolver.cs:82
long Value(LinearExpr e)
Returns the value of a linear expression in the last solution found.
Definition: CpSolver.cs:168
void SetLogCallback(StringToVoidDelegate del)
Definition: CpSolver.cs:139
long NumConflicts()
Returns the number of conflicts created during search.
Definition: CpSolver.cs:257
IList< int > SufficientAssumptionsForInfeasibility()
Definition: CpSolver.cs:268
double BestObjectiveBound
The best lower bound found when minimizing, of the best upper bound found when maximizing
Definition: CpSolver.cs:122
CpSolverStatus SearchAllSolutions(CpModel model, SolutionCallback cb)
Deprecated, use Solve() instead.
Definition: CpSolver.cs:71
double ObjectiveValue
The best objective value found during search.
Definition: CpSolver.cs:110
CpSolverResponse Response
Definition: CpSolver.cs:145
long NumBranches()
Returns the number of branches explored during search.
Definition: CpSolver.cs:251
Boolean BooleanValue(ILiteral literal)
Returns the Boolean value of a literal in the last solution found.
Definition: CpSolver.cs:230
CpSolverStatus Solve(CpModel model, SolutionCallback cb=null)
Solves the given model, and returns the solve status.
Definition: CpSolver.cs:32
long Value(IntVar intVar)
Returns the value of an integer variable in the last solution found.
Definition: CpSolver.cs:156
String SolutionInfo()
Returns some information on how the solution was found, or the reason why the model or the parameters...
Definition: CpSolver.cs:279
string StringParameters
The parameters of the search, stored as a string.
Definition: CpSolver.cs:130
Holds a integer variable with a discrete domain.
int GetIndex()
Returns the index of the variable in the underlying CpModelProto.
A builder class for linear expressions.
Holds a linear expression: sum (ai * xi) + b.
override void NewMessage(string message)
Definition: CpSolver.cs:298
LogCallbackDelegate(StringToVoidDelegate del)
Definition: CpSolver.cs:293
Holds a Boolean variable or its negation.
int GetIndex()
Returns the logical index of the literal.