objective.hpp

Go to the documentation of this file.

/*
 * GHOST (General meta-Heuristic Optimization Solving Tool) is a C++ framework
 * designed to help developers to model and implement optimization problem
 * solving. It contains a meta-heuristic solver aiming to solve any kind of
 * combinatorial and optimization real-time problems represented by a CSP/COP/EF-CSP/EF-COP. 
 *
 * First developed to solve game-related optimization problems, GHOST can be used for
 * any kind of applications where solving combinatorial and optimization problems. In
 * particular, it had been designed to be able to solve not-too-complex problem instances
 * within some milliseconds, making it very suitable for highly reactive or embedded systems.
 * Please visit https://github.com/richoux/GHOST for further information.
 *
 * Copyright (C) 2014-2023 Florian Richoux
 *
 * This file is part of GHOST.
 * GHOST is free software: you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as published
 * by the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 
 * GHOST is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 
 * You should have received a copy of the GNU General Public License
 * along with GHOST. If not, see http://www.gnu.org/licenses/.
 */
 
 
#pragma once
 
#include <algorithm>
#include <limits>
#include <vector>
#include <map>
#include <cmath> // for isnan
#include <exception>
 
#include "variable.hpp"
#include "thirdparty/randutils.hpp"
 
namespace ghost
{
    namespace algorithms
    {
        class AdaptiveSearchValueHeuristic;
        class AntidoteSearchValueHeuristic;
    }
    
    class Objective
    {
        template<typename ModelBuilderType> friend class Solver;
        friend class SearchUnit;
        friend class ModelBuilder;
 
        friend class NullObjective;
        friend class Minimize;
        friend class Maximize;
 
        friend class algorithms::AdaptiveSearchValueHeuristic;
        friend class algorithms::AntidoteSearchValueHeuristic;
        
        std::vector<Variable*> _variables; // Vector of raw pointers to variables needed to compute the objective function.
        std::vector<int> _variables_index; // To know where are the constraint's variables in the global variable vector.
        std::map<int,int> _variables_position; // To know where are global variables in the constraint's variables vector. 
        bool _is_optimization;
        bool _is_maximization;
        std::string _name; // Name of the objective object.
 
        struct nanException : std::exception
        {
            std::vector<Variable*> variables;
            std::string message;
 
            nanException( const std::vector<Variable*>& variables ) : variables(variables)
            {
                message = "Objective required_cost returned a NaN value on variables (";
                for( int i = 0; i < static_cast<int>( variables.size() ) - 1; ++i )
                    message += std::to_string( variables[i]->get_value() ) + ", ";
                message += std::to_string( variables[ static_cast<int>( variables.size() ) - 1 ]->get_value() ) + ")\n";
            }
            const char* what() const noexcept { return message.c_str(); }
        };
 
        struct variableOutOfTheScope : std::exception
        {
            std::string message;
 
            variableOutOfTheScope( int var_id, std::string name )
            {
                message = "Variable ID " + std::to_string( var_id ) + " is not in the scope of the Objective function " + name + ".\n";
            }
            const char* what() const noexcept { return message.c_str(); }
        };
 
        Objective( const std::vector<int>& variables_index, bool is_maximization, const std::string& name );
        Objective( const std::vector<Variable>& variables, bool is_maximization, const std::string& name );
 
        inline void update( int index, int new_value ) { conditional_update_data_structures( _variables, _variables_position[ index ], new_value ); }
 
        // Call required_cost() on Objective::_variables after making sure the cost does not give a nan, rise an exception otherwise.
        double cost() const;
 
        // Call expert_heuristic_value on Objective::_variables.
        inline int heuristic_value( int variable_index, const std::vector<int>& possible_values, randutils::mt19937_rng& rng ) const
        { return expert_heuristic_value( _variables, _variables_position.at( variable_index ), possible_values, rng ); }
 
        // Call expert_heuristic_value_permutation on Objective::_variables.
        inline int heuristic_value_permutation( int variable_index, const std::vector<int>& bad_variables, randutils::mt19937_rng& rng ) const
        { return expert_heuristic_value_permutation( _variables, _variables_position.at( variable_index ), bad_variables, rng ); }
 
        // Call expert_postprocess on Objective::_variables.
        inline double postprocess( double best_cost ) const
        { return expert_postprocess( _variables, best_cost ); }
 
    protected:
        virtual double required_cost( const std::vector<Variable*>& variables ) const = 0;
 
        virtual void conditional_update_data_structures( const std::vector<Variable*>& variables, int index, int new_value );
 
        virtual int expert_heuristic_value( const std::vector<Variable*>& variables,
                                            int variable_index,
                                            const std::vector<int>& possible_values,
                                            randutils::mt19937_rng& rng ) const;
 
        virtual int expert_heuristic_value_permutation( const std::vector<Variable*>& variables,
                                                        int variable_index,
                                                        const std::vector<int>& bad_variables,
                                                        randutils::mt19937_rng& rng ) const;
 
        virtual double expert_postprocess( const std::vector<Variable*>& variables,
                                           double best_cost ) const;
 
 
        // No documentation on purpose.
        inline void is_not_optimization() { _is_optimization = false; }
 
    public:
        Objective( const Objective& other ) = default;
        Objective( Objective&& other ) = default;
 
        Objective& operator=( const Objective& other ) = delete;
        Objective& operator=( Objective&& other ) = delete;
 
        virtual ~Objective() = default;
 
        inline std::string get_name() const { return _name; }
 
        inline bool is_optimization() const { return _is_optimization; }
 
        inline bool is_maximization() const { return _is_maximization; }
 
        friend std::ostream& operator<<( std::ostream& os, const Objective& o )
        {
            return os << "Objective name: " <<  o._name
                      << "\n********";
        }
    };
 
    /*******************/
    /*******************/
    // NullObjective is used when no objective functions have been given to the solver (ie, for pure satisfaction runs). 
    class NullObjective : public Objective
    {
    public:
        NullObjective() : Objective( std::vector<int>{0}, false, "nullObjective" )
        {
            this->is_not_optimization();
        }
 
    private:
        double required_cost( const std::vector<Variable*>& variables ) const override { return 0.0; }
    };
 
    /**************/
    /**************/
    class Minimize : public Objective
    {
    public:
        Minimize( const std::vector<int>& variables_index )
            : Objective( variables_index, false, std::string( "Minimize" ) )
        {   }
 
        Minimize( const std::vector<Variable>& variables )
            : Objective( variables, false, std::string( "Minimize" ) )
        {   }
 
        Minimize( const std::vector<int>& variables_index, const std::string& name )
            : Objective( variables_index, false, name )
        {   }
 
        Minimize( const std::vector<Variable>& variables, const std::string& name )
            : Objective( variables, false, name )
        {   }
 
        Minimize( const std::vector<int>& variables_index, const char* name )
            : Objective( variables_index, false, std::string( name ) )
        {   }
 
        Minimize( const std::vector<Variable>& variables, const char* name )
            : Objective( variables, false, std::string( name ) )
        {   }
    };
 
    /**************/
    /**************/
    class Maximize : public Objective
    {
    public:
        Maximize( const std::vector<int>& variables_index )
            : Objective( variables_index, true, std::string( "Maximize" ) )
        {   }
 
        Maximize( const std::vector<Variable>& variables )
            : Objective( variables, true, std::string( "Maximize" ) )
        {   }
 
        Maximize( const std::vector<int>& variables_index, const std::string& name )
            : Objective( variables_index, true, name )
        {   }
 
        Maximize( const std::vector<Variable>& variables, const std::string& name )
            : Objective( variables, true, name )
        {   }
 
        Maximize( const std::vector<int>& variables_index, const char* name )
            : Objective( variables_index, true, std::string( name ) )
        {   }
 
        Maximize( const std::vector<Variable>& variables, const char* name )
            : Objective( variables, true, std::string( name ) )
        {   }
    };
}