GHOST
Loading...
Searching...
No Matches
solver.hpp
Go to the documentation of this file.
1/*
2 * GHOST (General meta-Heuristic Optimization Solving Tool) is a C++ framework
3 * designed to help developers to model and implement optimization problem
4 * solving. It contains a meta-heuristic solver aiming to solve any kind of
5 * combinatorial and optimization real-time problems represented by a CSP/COP/EF-CSP/EF-COP.
6 *
7 * First developed to solve game-related optimization problems, GHOST can be used for
8 * any kind of applications where solving combinatorial and optimization problems. In
9 * particular, it had been designed to be able to solve not-too-complex problem instances
10 * within some milliseconds, making it very suitable for highly reactive or embedded systems.
11 * Please visit https://github.com/richoux/GHOST for further information.
12 *
13 * Copyright (C) 2014-2025 Florian Richoux
14 *
15 * This file is part of GHOST.
16 * GHOST is free software: you can redistribute it and/or
17 * modify it under the terms of the GNU General Public License as published
18 * by the Free Software Foundation, either version 3 of the License, or
19 * (at your option) any later version.
20
21 * GHOST is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 * GNU General Public License for more details.
25
26 * You should have received a copy of the GNU General Public License
27 * along with GHOST. If not, see http://www.gnu.org/licenses/.
28 */
29
30#pragma once
31
32#include <iostream>
33#include <iomanip>
34#include <cmath>
35#include <limits>
36#include <random>
37#include <algorithm>
38#include <vector>
39#include <deque>
40#include <chrono>
41#include <memory>
42#include <iterator>
43#include <thread>
44#include <future>
45
46#include "variable.hpp"
47#include "constraint.hpp"
48#include "objective.hpp"
49#include "auxiliary_data.hpp"
50#include "model.hpp"
51#include "model_builder.hpp"
52#include "options.hpp"
53#include "search_unit.hpp"
54
55#include "algorithms/variable_heuristic.hpp"
56#include "algorithms/variable_candidates_heuristic.hpp"
57#include "algorithms/value_heuristic.hpp"
58#include "algorithms/error_projection_algorithm.hpp"
59
60#include "algorithms/uniform_variable_heuristic.hpp"
61#include "algorithms/adaptive_search_variable_candidates_heuristic.hpp"
62#include "algorithms/adaptive_search_value_heuristic.hpp"
63#include "algorithms/adaptive_search_error_projection_algorithm.hpp"
64
65#include "algorithms/antidote_search_variable_heuristic.hpp"
66#include "algorithms/antidote_search_variable_candidates_heuristic.hpp"
67#include "algorithms/antidote_search_value_heuristic.hpp"
68
69#include "algorithms/culprit_search_error_projection_algorithm.hpp"
70
71#if defined GHOST_RANDOM_WALK || defined GHOST_HILL_CLIMBING
72#include "algorithms/all_free_variable_candidates_heuristic.hpp"
73#include "algorithms/null_error_projection_algorithm.hpp"
74#endif
75
76#if defined GHOST_RANDOM_WALK
77#include "algorithms/random_walk_value_heuristic.hpp"
78#endif
79
80#include "macros.hpp"
81
82namespace ghost
83{
118 template<typename ModelBuilderType> class Solver final
119 {
120 Model _model;
121 ModelBuilderType _model_builder; // Factory building the model
122
123 int _number_variables; // Size of the vector of variables.
124 int _number_constraints; // Size of the vector of constraints.
125
126 double _best_sat_error;
127 double _best_opt_cost;
128 double _cost_before_postprocess;
129
130 // global statistics, cumulation of all threads stats.
131 int _restarts_total;
132 int _resets_total;
133 int _local_moves_total;
134 int _search_iterations_total;
135 int _local_minimum_total;
136 int _plateau_moves_total;
137 int _plateau_force_trying_another_variable_total;
138
139 // stats of the winning thread
140 int _restarts;
141 int _resets;
142 int _local_moves;
143 int _search_iterations;
144 int _local_minimum;
145 int _plateau_moves;
146 int _plateau_force_trying_another_variable;
147
148 std::string _variable_heuristic;
149 std::string _variable_candidates_heuristic;
150 std::string _value_heuristic;
151 std::string _error_projection_algorithm;
152
153 // From search_unit_data
154 // Matrix to know which constraints contain a given variable
155 // matrix_var_ctr[ variable_id ] = { constraint_id_1, ..., constraint_id_k }
156 std::vector<std::vector<int> > _matrix_var_ctr;
157
158 Options _options; // Options for the solver (see the struct Options).
159
160 // Prefilter domains before running the AC3 algorithm, if the model contains some unary constraints
161 void prefiltering( std::vector< std::vector<int>> &domains )
162 {
163 for( auto& constraint : _model.constraints )
164 {
165 auto var_index = constraint->_variables_index;
166 if( var_index.size() == 1 )
167 {
168 std::vector<int> values_to_remove;
169 int index = var_index[0];
170 for( auto value : domains[index] )
171 {
172 _model.variables[index].set_value( value );
173 if( constraint->error() > 0.0 )
174 values_to_remove.push_back( value );
175 }
176
177 for( int value : values_to_remove )
178 domains[index].erase( std::find( domains[index].begin(), domains[index].end(), value ) );
179 }
180 }
181 }
182
183 // AC3 algorithm for complete_search. This method is handling the filtering, and return filtered domains.
184 // The vector of vector 'domains' is passed by copy on purpose.
185 // The value of variable[ index_v ] has already been set before the call
186 std::vector< std::vector<int>> ac3_filtering( int index_v, std::vector< std::vector<int>> domains )
187 {
188 // queue of (constraint id, variable id)
189 std::deque<std::pair<int, int>> ac3queue;
190
191 for( int constraint_id : _matrix_var_ctr[ index_v ] )
192 for( int variable_id : _model.constraints[ constraint_id ]->_variables_index )
193 {
194 if( variable_id <= index_v )
195 continue;
196
197 ac3queue.push_back( std::make_pair( constraint_id, variable_id ) );
198 }
199
200 std::vector<int> values_to_remove;
201 while( !ac3queue.empty() )
202 {
203 int constraint_id = ac3queue.front().first;
204 int variable_id = ac3queue.front().second;
205 ac3queue.pop_front();
206 values_to_remove.clear();
207 for( auto value : domains[variable_id] )
208 {
209 _model.variables[variable_id].set_value( value );
210 if( !has_support( constraint_id, variable_id, value, index_v, domains ) )
211 {
212 values_to_remove.push_back( value );
213 for( int c_id : _matrix_var_ctr[ variable_id ] )
214 {
215 if( c_id == constraint_id )
216 continue;
217
218 for( int v_id : _model.constraints[ c_id ]->_variables_index )
219 {
220 if( v_id <= index_v || v_id == variable_id )
221 continue;
222
223 if( std::find_if( ac3queue.begin(),
224 ac3queue.end(),
225 [&]( auto& elem ){ return elem.first == c_id && elem.second == v_id; } ) == ac3queue.end() )
226 {
227 ac3queue.push_back( std::make_pair( c_id, v_id ) );
228 }
229 }
230 }
231 }
232 }
233
234 for( int value : values_to_remove )
235 domains[variable_id].erase( std::find( domains[variable_id].begin(), domains[variable_id].end(), value ) );
236
237 // once a domain is empty, no need to go further
238 if( domains[variable_id].empty() )
239 return domains;
240 }
241
242 return domains;
243 }
244
245 // Method called by ac3_filtering, to compute if variable_id assigned to value has some support for the constraint
246 // constraint_id, but testing iteratively all combination of values for free variables until finding a local solution,
247 // or exhausting all possibilities. Return true if and only if a support exists.
248 // Values of variable[ index_v ] and variable[ variable_id ] have already been set before the call
249 bool has_support( int constraint_id, int variable_id, int value, int index_v, const std::vector< std::vector<int>>& domains )
250 {
251 std::vector<int> constraint_scope;
252 for( auto var_index : _model.constraints[ constraint_id ]->_variables_index )
253 if( var_index > index_v && var_index != variable_id )
254 constraint_scope.push_back( var_index );
255
256 // Case where there are no free variables
257 if( constraint_scope.empty() )
258 return _model.constraints[ constraint_id ]->error() == 0.0;
259
260 // From here, there are some free variables to assign
261 std::vector<int> indexes( constraint_scope.size() + 1, 0 );
262 int fake_index = static_cast<int>( indexes.size() ) - 1;
263
264 while( indexes[ fake_index ] == 0 )
265 {
266 for( int i = 0 ; i < fake_index ; ++i )
267 {
268 int assignment_index = constraint_scope[i];
269 int assignment_value = domains[ assignment_index ][ indexes[ i ] ];
270 _model.variables[ assignment_index ].set_value( assignment_value );
271 }
272
273 if( _model.constraints[ constraint_id ]->error() == 0.0 )
274 return true;
275 else
276 {
277 bool changed;
278 int index = 0;
279 do
280 {
281 changed = false;
282 ++indexes[ index ];
283 if( index < fake_index && indexes[ index ] >= static_cast<int>( domains[ constraint_scope[ index ] ].size() ) )
284 {
285 indexes[ index ] = 0;
286 changed = true;
287 ++index;
288 }
289 }
290 while( changed );
291 }
292 }
293
294 return false;
295 }
296
297 // Recursive call of complete_search. Search for all solutions of the problem instance.
298 // index_v is the index of the last variable assigned. Return the vector of some found solutions.
299 // The value of variable[ index_v ] has already been set before the call
300 std::vector<std::vector<int>> complete_search( int index_v, std::vector< std::vector<int>> domains )
301 {
302 // should never be called
303 if( index_v >= _model.variables.size() )
304 return std::vector<std::vector<int>>();
305
306 std::vector< std::vector<int>> new_domains;
307 if( index_v > 0 )
308 {
309 new_domains = ac3_filtering( index_v, domains );
310 auto empty_domain = std::find_if( new_domains.cbegin(), new_domains.cend(), [&]( auto& domain ){ return domain.empty(); } );
311
312 if( empty_domain != new_domains.cend() )
313 return std::vector<std::vector<int>>();
314 }
315 else
316 {
317 new_domains = domains; // already filtered
318 }
319
320 int next_var = index_v + 1;
321 std::vector<std::vector<int>> solutions;
322 for( auto value : new_domains[next_var] )
323 {
324 _model.variables[next_var].set_value( value );
325
326 // last variable
327 if( next_var == _model.variables.size() - 1 )
328 {
329 std::vector<int> solution;
330 for( auto& var : _model.variables )
331 solution.emplace_back( var.get_value() );
332
333 solutions.emplace_back( solution );
334 }
335 else // not the last variable: recursive call
336 {
337 auto partial_solutions = complete_search( next_var, new_domains );
338 if( !partial_solutions.empty() )
339 std::copy_if( partial_solutions.begin(),
340 partial_solutions.end(),
341 std::back_inserter( solutions ),
342 [&]( auto& solution ){ return !solution.empty(); } );
343 }
344 }
345
346 return solutions;
347 }
348
349 public:
357 Solver( const ModelBuilderType& model_builder )
358 : _model_builder( model_builder ),
359 _best_sat_error( std::numeric_limits<double>::max() ),
360 _best_opt_cost( std::numeric_limits<double>::max() ),
361 _cost_before_postprocess( std::numeric_limits<double>::max() ),
362 _restarts_total( 0 ),
363 _resets_total( 0 ),
364 _local_moves_total( 0 ),
365 _search_iterations_total( 0 ),
366 _local_minimum_total( 0 ),
367 _plateau_moves_total( 0 ),
368 _plateau_force_trying_another_variable_total( 0 ),
369 _restarts( 0 ),
370 _resets( 0 ),
371 _local_moves( 0 ),
372 _search_iterations( 0 ),
373 _local_minimum( 0 ),
374 _plateau_moves( 0 ),
375 _plateau_force_trying_another_variable( 0 )
376 { }
377
431 bool fast_search( double& final_cost,
432 std::vector<int>& final_solution,
433 double timeout,
434 Options& options )
435 {
436 std::chrono::time_point<std::chrono::steady_clock> start_wall_clock( std::chrono::steady_clock::now() );
437 std::chrono::time_point<std::chrono::steady_clock> start_search;
438 std::chrono::time_point<std::chrono::steady_clock> start_postprocess;
439 std::chrono::duration<double,std::micro> elapsed_time( 0 );
440 std::chrono::duration<double,std::micro> timer_postprocess( 0 );
441
442 /*****************
443 * Initialization *
444 ******************/
445 // Only to get the number of variables and constraints
446 _model_builder.declare_variables();
447 _number_variables = _model_builder.get_number_variables();
448
449 _options = options;
450
451 if( _options.tabu_time_local_min < 0 )
452 _options.tabu_time_local_min = std::max( std::min( 5, static_cast<int>( _number_variables ) - 1 ), static_cast<int>( std::ceil( _number_variables / 5 ) ) ) + 1;
453 //_options.tabu_time_local_min = std::max( 2, _tabu_threshold ) );
454
455 if( _options.tabu_time_selected < 0 )
456 _options.tabu_time_selected = 0;
457
460
461 if( _options.reset_threshold < 0 )
462 _options.reset_threshold = _options.tabu_time_local_min;
463// _options.reset_threshold = static_cast<int>( std::ceil( 1.5 * _options.reset_threshold ) );
464// _options.reset_threshold = 2 * static_cast<int>( std::ceil( std::sqrt( _number_variables ) ) );
465
466 if( _options.restart_threshold < 0 )
467 _options.restart_threshold = _number_variables;
468
469 if( _options.number_variables_to_reset < 0 )
470 _options.number_variables_to_reset = std::max( 2, static_cast<int>( std::ceil( _number_variables * 0.1 ) ) ); // 10%
471
472 if( _options.number_start_samplings < 0 )
473 _options.number_start_samplings = 10;
474
475#if defined GHOST_RANDOM_WALK || defined GHOST_HILL_CLIMBING
477 _options.number_start_samplings = 1;
478 _options.tabu_time_local_min = 0;
479 _options.tabu_time_selected = 0;
480#endif
481
482 double chrono_search;
483 double chrono_full_computation;
484
485 // In case final_solution is not a vector of the correct size,
486 // ie, equals to the number of variables.
487 final_solution.resize( _number_variables );
488 bool solution_found = false;
489 bool is_sequential;
490 bool is_optimization;
491
492#if defined GHOST_DEBUG || defined GHOST_TRACE || defined GHOST_BENCH
493 // this is to make proper benchmarks/debugging with 1 thread.
494 is_sequential = !_options.parallel_runs;
495#else
496 is_sequential = ( !_options.parallel_runs || _options.number_threads == 1 );
497#endif
498
499 // sequential runs
500 if( is_sequential )
501 {
502#if defined GHOST_RANDOM_WALK
503 SearchUnit search_unit( _model_builder.build_model(),
504 _options,
505 std::make_unique<algorithms::UniformVariableHeuristic>(),
506 std::make_unique<algorithms::AllFreeVariableCandidatesHeuristic>(),
507 std::make_unique<algorithms::RandomWalkValueHeuristic>(),
508 std::make_unique<algorithms::NullErrorProjection>() );
509#elif defined GHOST_HILL_CLIMBING
510 SearchUnit search_unit( _model_builder.build_model(),
511 _options,
512 std::make_unique<algorithms::UniformVariableHeuristic>(),
513 std::make_unique<algorithms::AllFreeVariableCandidatesHeuristic>(),
514 std::make_unique<algorithms::AdaptiveSearchValueHeuristic>(),
515 std::make_unique<algorithms::NullErrorProjection>() );
516#else
517 SearchUnit search_unit( _model_builder.build_model(),
518 _options );
519#endif
520 is_optimization = search_unit.data.is_optimization;
521 std::future<bool> unit_future = search_unit.solution_found.get_future();
522
523 start_search = std::chrono::steady_clock::now();
524 search_unit.local_search( timeout );
525 elapsed_time = std::chrono::steady_clock::now() - start_search;
526 chrono_search = elapsed_time.count();
527
528 solution_found = unit_future.get();
529 _best_sat_error = search_unit.data.best_sat_error;
530 _best_opt_cost = search_unit.data.best_opt_cost;
531 _restarts = search_unit.data.restarts;
532 _resets = search_unit.data.resets;
533 _local_moves = search_unit.data.local_moves;
534 _search_iterations = search_unit.data.search_iterations;
535 _local_minimum = search_unit.data.local_minimum;
536 _plateau_moves = search_unit.data.plateau_moves;
537 _plateau_force_trying_another_variable = search_unit.data.plateau_force_trying_another_variable;
538
539 _variable_heuristic = search_unit.variable_heuristic->get_name();
540 _variable_candidates_heuristic = search_unit.variable_candidates_heuristic->get_name();
541 _value_heuristic = search_unit.value_heuristic->get_name();
542 _error_projection_algorithm = search_unit.error_projection_algorithm->get_name();
543
544 _model = std::move( search_unit.transfer_model() );
545 }
546 else // call threads
547 {
548 std::vector<SearchUnit> units;
549 units.reserve( _options.number_threads );
550 std::vector<std::thread> unit_threads;
551
552 for( int i = 0 ; i < _options.number_threads; ++i )
553 {
554 // Instantiate one model per thread
555#if defined GHOST_RANDOM_WALK
556 units.emplace_back( _model_builder.build_model(),
557 _options,
558 std::make_unique<algorithms::UniformVariableHeuristic>(),
559 std::make_unique<algorithms::AllFreeVariableCandidatesHeuristic>(),
560 std::make_unique<algorithms::RandomWalkValueHeuristic>(),
561 std::make_unique<algorithms::NullErrorProjection>() );
562#elif defined GHOST_HILL_CLIMBING
563 units.emplace_back( _model_builder.build_model(),
564 _options,
565 std::make_unique<algorithms::UniformVariableHeuristic>(),
566 std::make_unique<algorithms::AllFreeVariableCandidatesHeuristic>(),
567 std::make_unique<algorithms::AdaptiveSearchValueHeuristic>(),
568 std::make_unique<algorithms::NullErrorProjection>() );
569#else
570 units.emplace_back( _model_builder.build_model(),
571 _options );
572#endif
573 }
574
575 is_optimization = units[0].data.is_optimization;
576
577 std::vector<std::future<bool>> units_future;
578 std::vector<bool> units_terminated( _options.number_threads, false );
579
580 start_search = std::chrono::steady_clock::now();
581
582 for( int i = 0 ; i < _options.number_threads; ++i )
583 {
584 unit_threads.emplace_back( &SearchUnit::local_search, &units.at(i), timeout );
585 units.at( i ).get_thread_id( unit_threads.at( i ).get_id() );
586 units_future.emplace_back( units.at( i ).solution_found.get_future() );
587 }
588
589 int thread_number = 0;
590 int winning_thread = 0;
591 bool end_of_computation = false;
592 int number_timeouts = 0;
593
594 while( !end_of_computation )
595 {
596 for( thread_number = 0 ; thread_number < _options.number_threads ; ++thread_number )
597 {
598 if( !units_terminated[ thread_number ] && units_future.at( thread_number ).wait_for( std::chrono::microseconds( 0 ) ) == std::future_status::ready )
599 {
600 if( is_optimization )
601 {
602 ++number_timeouts;
603 units_terminated[ thread_number ] = true;
604
605 if( units_future.at( thread_number ).get() ) // equivalent to if( units.at( thread_number ).best_sat_error == 0.0 )
606 {
607 solution_found = true;
608 if( _best_opt_cost > units.at( thread_number ).data.best_opt_cost )
609 {
610 _best_opt_cost = units.at( thread_number ).data.best_opt_cost;
611 winning_thread = thread_number;
612 }
613 }
614
615 if( number_timeouts >= _options.number_threads )
616 {
617 end_of_computation = true;
618 break;
619 }
620 }
621 else // then it is a satisfaction problem
622 {
623 if( units_future.at( thread_number ).get() )
624 {
625 solution_found = true;
626 units_terminated[ thread_number ] = true;
627 winning_thread = thread_number;
628 end_of_computation = true;
629 break;
630 }
631 else
632 {
633 ++number_timeouts;
634 units_terminated[ thread_number ] = true;
635 if( number_timeouts >= _options.number_threads )
636 {
637 end_of_computation = true;
638 break;
639 }
640 }
641 }
642 }
643 }
644 }
645
646 elapsed_time = std::chrono::steady_clock::now() - start_search;
647 chrono_search = elapsed_time.count();
648
649 // Collect all interesting data before terminating threads.
650 // Stats first...
651 for( int i = 0 ; i < _options.number_threads ; ++i )
652 {
653 units.at(i).stop_search();
654
655 _restarts_total += units.at(i).data.restarts;
656 _resets_total += units.at(i).data.resets;
657 _local_moves_total += units.at(i).data.local_moves;
658 _search_iterations_total += units.at(i).data.search_iterations;
659 _local_minimum_total += units.at(i).data.local_minimum;
660 _plateau_moves_total += units.at(i).data.plateau_moves;
661 _plateau_force_trying_another_variable_total += units.at(i).data.plateau_force_trying_another_variable;
662 }
663
664 // ..then the most important: the best solution found so far.
665 if( solution_found )
666 {
667#if defined GHOST_TRACE
668 std::cout << "Parallel run, thread number " << winning_thread << " has found a solution.\n";
669#endif
670 _best_sat_error = units.at( winning_thread ).data.best_sat_error;
671 _best_opt_cost = units.at( winning_thread ).data.best_opt_cost;
672
673 _restarts = units.at( winning_thread ).data.restarts;
674 _resets = units.at( winning_thread ).data.resets;
675 _local_moves = units.at( winning_thread ).data.local_moves;
676 _search_iterations = units.at( winning_thread ).data.search_iterations;
677 _local_minimum = units.at( winning_thread ).data.local_minimum;
678 _plateau_moves = units.at( winning_thread ).data.plateau_moves;
679 _plateau_force_trying_another_variable = units.at( winning_thread ).data.plateau_force_trying_another_variable;
680
681 _variable_heuristic = units.at( winning_thread ).variable_heuristic->get_name();
682 _variable_candidates_heuristic = units.at( winning_thread ).variable_candidates_heuristic->get_name();
683 _value_heuristic = units.at( winning_thread ).value_heuristic->get_name();
684 _error_projection_algorithm = units.at( winning_thread ).error_projection_algorithm->get_name();
685
686 _model = std::move( units.at( winning_thread ).transfer_model() );
687 }
688 else
689 {
690#if defined GHOST_TRACE
691 std::cout << "Parallel run, no solutions found.\n";
692#endif
693 int best_non_solution = 0;
694 for( int i = 0 ; i < _options.number_threads ; ++i )
695 {
696 if( _best_sat_error > units.at( i ).data.best_sat_error )
697 {
698 best_non_solution = i;
699 _best_sat_error = units.at( i ).data.best_sat_error;
700 }
701 if( is_optimization && _best_sat_error == 0.0 )
702 if( units.at( i ).data.best_sat_error == 0.0 && _best_opt_cost > units.at( i ).data.best_opt_cost )
703 {
704 best_non_solution = i;
705 _best_opt_cost = units.at( i ).data.best_opt_cost;
706 }
707 }
708
709 _restarts = units.at( best_non_solution ).data.restarts;
710 _resets = units.at( best_non_solution ).data.resets;
711 _local_moves = units.at( best_non_solution ).data.local_moves;
712 _search_iterations = units.at( best_non_solution ).data.search_iterations;
713 _local_minimum = units.at( best_non_solution ).data.local_minimum;
714 _plateau_moves = units.at( best_non_solution ).data.plateau_moves;
715 _plateau_force_trying_another_variable = units.at( best_non_solution ).data.plateau_force_trying_another_variable;
716
717 _variable_heuristic = units.at( best_non_solution ).variable_heuristic->get_name();
718 _variable_candidates_heuristic = units.at( best_non_solution ).variable_candidates_heuristic->get_name();
719 _value_heuristic = units.at( best_non_solution ).value_heuristic->get_name();
720 _error_projection_algorithm = units.at( best_non_solution ).error_projection_algorithm->get_name();
721
722 _model = std::move( units.at( best_non_solution ).transfer_model() );
723 }
724
725 for( auto& thread: unit_threads )
726 {
727#if defined GHOST_TRACE
728 std::cout << "Joining and terminating thread number " << thread.get_id() << "\n";
729#endif
730 thread.join();
731 }
732 }
733
734 if( solution_found && is_optimization )
735 {
736 _cost_before_postprocess = _best_opt_cost;
737
738 start_postprocess = std::chrono::steady_clock::now();
739 _best_opt_cost = _model.objective->postprocess( _best_opt_cost );
740 timer_postprocess = std::chrono::steady_clock::now() - start_postprocess;
741 }
742
743 if( is_optimization )
744 {
745 if( _model.objective->is_maximization() )
746 {
747 _best_opt_cost = -_best_opt_cost;
748 _cost_before_postprocess = -_cost_before_postprocess;
749 }
750
751 final_cost = _best_opt_cost;
752 }
753 else
754 final_cost = _best_sat_error;
755
756 std::transform( _model.variables.begin(),
757 _model.variables.end(),
758 final_solution.begin(),
759 [&](auto& var){ return var.get_value(); } );
760
761 elapsed_time = std::chrono::steady_clock::now() - start_wall_clock;
762 chrono_full_computation = elapsed_time.count();
763
764#if defined GHOST_DEBUG || defined GHOST_TRACE || defined GHOST_BENCH
765 std::cout << "@@@@@@@@@@@@" << "\n"
766 << "Variable heuristic: " << _variable_heuristic << "\n"
767 << "Variable candidate heuristic: " << _variable_candidates_heuristic << "\n"
768 << "Value heuristic: " << _value_heuristic << "\n"
769 << "Error projection algorithm: " << _error_projection_algorithm << "\n"
770 << "Started from a custom variables assignment: " << std::boolalpha << _options.custom_starting_point << "\n"
771 << "Search resumed from a previous run: " << std::boolalpha << _options.resume_search << "\n"
772 << "Parallel search: " << std::boolalpha << _options.parallel_runs << "\n"
773 << "Number of threads (not used if no parallel search): " << _options.number_threads << "\n"
774 << "Number of variable assignments samplings at start (if custom start and resume are set to false): " << _options.number_start_samplings << "\n"
775 << "Variables of local minimum are frozen for: " << _options.tabu_time_local_min << " local moves\n"
776 << "Selected variables are frozen for: " << _options.tabu_time_selected << " local moves\n"
777 << "Percentage of chance to force exploring another variable on a plateau: " << _options.percent_chance_force_trying_on_plateau << "%\n"
778 << _options.number_variables_to_reset << " variables are reset when " << _options.reset_threshold << " variables are frozen\n";
779 if( _options.restart_threshold > 0 )
780 std::cout << "Do a restart each time " << _options.restart_threshold << " resets are performed\n";
781 else
782 std::cout << "Never perform restarts\n";
783 std::cout << "############" << "\n";
784
785 // Print solution
786 std::cout << "Solution: ";
787 for( const auto& v: _model.variables )
788 std::cout << v.get_value() << " ";
789
790 std::cout << "\n" << _options.print->print_candidate( _model.variables ).str() << "\n";
791
792 if( !is_optimization )
793 std::cout << "SATISFACTION run" << "\n";
794 else
795 {
796 std::cout << "OPTIMIZATION run with objective " << _model.objective->get_name() << "\n";
797 if( _model.objective->is_maximization() )
798 std::cout << _model.objective->get_name() << " must be maximized.\n";
799 else
800 std::cout << _model.objective->get_name() << " must be minimized.\n";
801 }
802
803 std::cout << "Permutation problem: " << std::boolalpha << _model.permutation_problem << "\n"
804 << "Time budget: " << timeout << "us (= " << timeout/1000 << "ms, " << timeout/1000000 << "s)\n"
805 << "Search time: " << chrono_search << "us (= " << chrono_search / 1000 << "ms, " << chrono_search / 1000000 << "s)\n"
806 << "Wall-clock time (full call): " << chrono_full_computation << "us (= " << chrono_full_computation/1000 << "ms, " << chrono_full_computation/1000000 << "s)\n"
807 << "Satisfaction error: " << _best_sat_error << "\n"
808 << "Number of search iterations: " << _search_iterations << "\n"
809 << "Number of local moves: " << _local_moves << " (including on plateau: " << _plateau_moves << ")\n"
810 << "Number of local minimum: " << _local_minimum << "\n"
811 << "Number of variable exploration forcing on a plateau: " << _plateau_force_trying_another_variable << "\n"
812 << "Number of resets: " << _resets << "\n"
813 << "Number of restarts: " << _restarts << "\n";
814
815 if( _options.parallel_runs )
816 std::cout << "Total number of search iterations: " << _search_iterations_total << "\n"
817 << "Total number of local moves: " << _local_moves_total << " (including on plateau: " << _plateau_moves_total << ")\n"
818 << "Total number of local minimum: " << _local_minimum_total << "\n"
819 << "Total number of variable exploration forcing on a plateau: " << _plateau_force_trying_another_variable_total << "\n"
820 << "Total number of resets: " << _resets_total << "\n"
821 << "Total number of restarts: " << _restarts_total << "\n";
822
823 if( is_optimization )
824 std::cout << "\nOptimization cost: " << _best_opt_cost << "\n";
825
826 // If post-processing takes more than 1 microsecond, print details about it on the screen
827 // This is to avoid printing something with empty post-processing, taking usually less than 0.1 microsecond (tested on a Core i9 9900)
828 if( timer_postprocess.count() > 1 )
829 std::cout << "Optimization Cost BEFORE post-processing: " << _cost_before_postprocess << "\n"
830 << "Optimization post-processing time: " << timer_postprocess.count() << "us (= " << timer_postprocess.count()/1000 << "ms, " << timer_postprocess.count()/1000000 << "s)\n";
831
832 std::cout << "\n";
833#endif
834
835 return solution_found;
836 }
837
851 bool fast_search( double& final_cost, std::vector<int>& final_solution, double timeout )
852 {
853 Options options;
854 return fast_search( final_cost, final_solution, timeout, options );
855 }
856
877 bool fast_search( double& final_cost, std::vector<int>& final_solution, std::chrono::microseconds timeout, Options& options )
878 {
879 return fast_search( final_cost, final_solution, timeout.count(), options );
880 }
881
898 bool fast_search( double& final_cost, std::vector<int>& final_solution, std::chrono::microseconds timeout )
899 {
900 Options options;
901 return fast_search( final_cost, final_solution, timeout, options );
902 }
903
904
932 bool complete_search( std::vector<double>& final_costs,
933 std::vector<std::vector<int>>& final_solutions,
934 Options& options )
935 {
936 // init data
937 bool solutions_exist = false;
938 _options = options;
939
940 _model = _model_builder.build_model();
941
942 std::vector< std::vector<int> > domains;
943 for( auto& var : _model.variables )
944 domains.emplace_back( var.get_full_domain() );
945
946 _matrix_var_ctr.resize( _model.variables.size() );
947 for( int variable_id = 0; variable_id < static_cast<int>( _model.variables.size() ); ++variable_id )
948 {
949 _matrix_var_ctr[ variable_id ] = std::vector<int>();
950 for( int constraint_id = 0; constraint_id < static_cast<int>( _model.constraints.size() ); ++constraint_id )
951 if( _model.constraints[ constraint_id ]->has_variable( variable_id ) )
952 _matrix_var_ctr[ variable_id ].push_back( constraint_id );
953 }
954
955 prefiltering( domains );
956
957 for( int value : domains[0] )
958 {
959 _model.variables[0].set_value( value );
960 auto new_domains = ac3_filtering( 0, domains );
961 auto empty_domain = std::find_if( new_domains.cbegin(), new_domains.cend(), [&]( auto& domain ){ return domain.empty(); } );
962
963 if( empty_domain == new_domains.cend() )
964 {
965 std::vector<std::vector<int>> partial_solutions = complete_search( 0, new_domains );
966
967 for( auto& solution : partial_solutions )
968 if( !solution.empty() )
969 {
970 solutions_exist = true;
971 for( int i = 1 ; i < static_cast<int>( solution.size() ) ; ++i )
972 _model.variables[i].set_value( solution[i] );
973
974 double cost = _model.objective->cost();
975 if( _model.objective->is_maximization() )
976 cost = -cost;
977
978 final_costs.push_back( cost );
979 final_solutions.emplace_back( solution );
980 }
981 }
982 }
983
984 // need to reassigned the variables value to solutions one by one
985 //std::cout << _options.print->print_candidate( _model.variables ).str();
986 return solutions_exist;
987 }
988
1001 bool complete_search( std::vector<double>& final_costs, std::vector<std::vector<int>>& final_solutions )
1002 {
1003 Options options;
1004 return complete_search( final_costs, final_solutions, options );
1005 }
1006
1013 inline std::vector<Variable> get_variables() { return _model.variables; }
1014 };
1015}
Definition solver.hpp:119
Solver(const ModelBuilderType &model_builder)
Definition solver.hpp:357
bool fast_search(double &final_cost, std::vector< int > &final_solution, double timeout, Options &options)
Definition solver.hpp:431
bool fast_search(double &final_cost, std::vector< int > &final_solution, std::chrono::microseconds timeout)
Definition solver.hpp:898
std::vector< Variable > get_variables()
Definition solver.hpp:1013
bool fast_search(double &final_cost, std::vector< int > &final_solution, double timeout)
Definition solver.hpp:851
bool fast_search(double &final_cost, std::vector< int > &final_solution, std::chrono::microseconds timeout, Options &options)
Definition solver.hpp:877
bool complete_search(std::vector< double > &final_costs, std::vector< std::vector< int > > &final_solutions)
Definition solver.hpp:1001
bool complete_search(std::vector< double > &final_costs, std::vector< std::vector< int > > &final_solutions, Options &options)
Definition solver.hpp:932
Definition auxiliary_data.hpp:38
Definition options.hpp:45
int tabu_time_selected
Number of local moves a selected variable is marked tabu.
Definition options.hpp:53
int reset_threshold
Number of variables marked as tabu required to trigger a reset.
Definition options.hpp:55
bool parallel_runs
To enable parallel runs of the solver. Using all available physical cores if number_threads is not sp...
Definition options.hpp:48
int number_threads
Number of threads the solver will use for the search.
Definition options.hpp:50
int number_start_samplings
Number of variable assignments the solver randomly draw, if custom_starting_point and resume_search a...
Definition options.hpp:58
int number_variables_to_reset
Number of variables to randomly change the value at each reset.
Definition options.hpp:57
bool custom_starting_point
To force starting the search on a custom variables assignment.
Definition options.hpp:46
std::shared_ptr< Print > print
Allowing custom solution print (by derivating a class from ghost::Print)
Definition options.hpp:51
int restart_threshold
Trigger a restart every 'restart_threshold' reset. Set to 0 to never trigger restarts.
Definition options.hpp:56
int percent_chance_force_trying_on_plateau
Percentage of chance to force trying another variable rather than doing a move on a plateau.
Definition options.hpp:54
int tabu_time_local_min
Number of local moves a variable of a local minimum is marked tabu.
Definition options.hpp:52
bool resume_search
Allowing stop-and-resume computation.
Definition options.hpp:47