432 std::vector<int>& final_solution,
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 );
446 _model_builder.declare_variables();
447 _number_variables = _model_builder.get_number_variables();
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;
475#if defined GHOST_RANDOM_WALK || defined GHOST_HILL_CLIMBING
482 double chrono_search;
483 double chrono_full_computation;
487 final_solution.resize( _number_variables );
488 bool solution_found =
false;
490 bool is_optimization;
492#if defined GHOST_DEBUG || defined GHOST_TRACE || defined GHOST_BENCH
502#if defined GHOST_RANDOM_WALK
503 SearchUnit search_unit( _model_builder.build_model(),
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(),
512 std::make_unique<algorithms::UniformVariableHeuristic>(),
513 std::make_unique<algorithms::AllFreeVariableCandidatesHeuristic>(),
514 std::make_unique<algorithms::AdaptiveSearchValueHeuristic>(),
515 std::make_unique<algorithms::NullErrorProjection>() );
517 SearchUnit search_unit( _model_builder.build_model(),
520 is_optimization = search_unit.data.is_optimization;
521 std::future<bool> unit_future = search_unit.solution_found.get_future();
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();
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;
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();
544 _model = std::move( search_unit.transfer_model() );
548 std::vector<SearchUnit> units;
550 std::vector<std::thread> unit_threads;
555#if defined GHOST_RANDOM_WALK
556 units.emplace_back( _model_builder.build_model(),
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(),
565 std::make_unique<algorithms::UniformVariableHeuristic>(),
566 std::make_unique<algorithms::AllFreeVariableCandidatesHeuristic>(),
567 std::make_unique<algorithms::AdaptiveSearchValueHeuristic>(),
568 std::make_unique<algorithms::NullErrorProjection>() );
570 units.emplace_back( _model_builder.build_model(),
575 is_optimization = units[0].data.is_optimization;
577 std::vector<std::future<bool>> units_future;
578 std::vector<bool> units_terminated( _options.
number_threads,
false );
580 start_search = std::chrono::steady_clock::now();
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() );
589 int thread_number = 0;
590 int winning_thread = 0;
591 bool end_of_computation =
false;
592 int number_timeouts = 0;
594 while( !end_of_computation )
596 for( thread_number = 0 ; thread_number < _options.
number_threads ; ++thread_number )
598 if( !units_terminated[ thread_number ] && units_future.at( thread_number ).wait_for( std::chrono::microseconds( 0 ) ) == std::future_status::ready )
600 if( is_optimization )
603 units_terminated[ thread_number ] =
true;
605 if( units_future.at( thread_number ).get() )
607 solution_found =
true;
608 if( _best_opt_cost > units.at( thread_number ).data.best_opt_cost )
610 _best_opt_cost = units.at( thread_number ).data.best_opt_cost;
611 winning_thread = thread_number;
617 end_of_computation =
true;
623 if( units_future.at( thread_number ).get() )
625 solution_found =
true;
626 units_terminated[ thread_number ] =
true;
627 winning_thread = thread_number;
628 end_of_computation =
true;
634 units_terminated[ thread_number ] =
true;
637 end_of_computation =
true;
646 elapsed_time = std::chrono::steady_clock::now() - start_search;
647 chrono_search = elapsed_time.count();
653 units.at(i).stop_search();
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;
667#if defined GHOST_TRACE
668 std::cout <<
"Parallel run, thread number " << winning_thread <<
" has found a solution.\n";
670 _best_sat_error = units.at( winning_thread ).data.best_sat_error;
671 _best_opt_cost = units.at( winning_thread ).data.best_opt_cost;
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;
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();
686 _model = std::move( units.at( winning_thread ).transfer_model() );
690#if defined GHOST_TRACE
691 std::cout <<
"Parallel run, no solutions found.\n";
693 int best_non_solution = 0;
696 if( _best_sat_error > units.at( i ).data.best_sat_error )
698 best_non_solution = i;
699 _best_sat_error = units.at( i ).data.best_sat_error;
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 )
704 best_non_solution = i;
705 _best_opt_cost = units.at( i ).data.best_opt_cost;
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;
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();
722 _model = std::move( units.at( best_non_solution ).transfer_model() );
725 for(
auto& thread: unit_threads )
727#if defined GHOST_TRACE
728 std::cout <<
"Joining and terminating thread number " << thread.get_id() <<
"\n";
734 if( solution_found && is_optimization )
736 _cost_before_postprocess = _best_opt_cost;
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;
743 if( is_optimization )
745 if( _model.objective->is_maximization() )
747 _best_opt_cost = -_best_opt_cost;
748 _cost_before_postprocess = -_cost_before_postprocess;
751 final_cost = _best_opt_cost;
754 final_cost = _best_sat_error;
756 std::transform( _model.variables.begin(),
757 _model.variables.end(),
758 final_solution.begin(),
759 [&](
auto& var){ return var.get_value(); } );
761 elapsed_time = std::chrono::steady_clock::now() - start_wall_clock;
762 chrono_full_computation = elapsed_time.count();
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"
780 std::cout <<
"Do a restart each time " << _options.
restart_threshold <<
" resets are performed\n";
782 std::cout <<
"Never perform restarts\n";
783 std::cout <<
"############" <<
"\n";
786 std::cout <<
"Solution: ";
787 for(
const auto& v: _model.variables )
788 std::cout << v.get_value() <<
" ";
790 std::cout <<
"\n" << _options.
print->print_candidate( _model.variables ).str() <<
"\n";
792 if( !is_optimization )
793 std::cout <<
"SATISFACTION run" <<
"\n";
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";
800 std::cout << _model.objective->get_name() <<
" must be minimized.\n";
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";
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";
823 if( is_optimization )
824 std::cout <<
"\nOptimization cost: " << _best_opt_cost <<
"\n";
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";
835 return solution_found;