core

/* Copyright (C) 2016-2019 INRA
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#ifndef ORG_VLEPROJECT_BARYONYX_SOLVER_CORE
#define ORG_VLEPROJECT_BARYONYX_SOLVER_CORE

#include <array>
#include <forward_list>
#include <functional>
#include <limits>
#include <memory>
#include <numeric>
#include <stdexcept>
#include <string>
#include <string_view>
#include <vector>

#include <cstdint>

#include <baryonyx/export>

namespace baryonyx {

/** @c index is used as accessors for all array. */
using index = std::int32_t;

/** @c value is used as value for variable. */
using var_value = std::int_least8_t;

struct string_buffer
{
    constexpr static std::size_t string_buffer_node_length = 1024 * 1024;

    using value_type = std::array<char, string_buffer_node_length>;
    using container_type = std::forward_list<value_type>;

    string_buffer() noexcept = default;
    ~string_buffer() noexcept = default;

    string_buffer(const string_buffer&) = delete;
    string_buffer(string_buffer&&) = delete;
    string_buffer& operator=(const string_buffer&) = delete;
    string_buffer& operator=(string_buffer&&) = delete;

    std::string_view append(std::string_view str)
    {
        if (m_container.empty() ||
            str.size() + m_position > string_buffer_node_length)
            do_alloc();

        std::size_t position = m_position;
        m_position += str.size();

        char* buffer = m_container.front().data() + position;

        std::copy_n(str.data(), str.size(), buffer);

        return std::string_view(buffer, str.size());
    }

    std::size_t size() const noexcept
    {
        return std::accumulate(
          m_container.cbegin(),
          m_container.cend(),
          0,
          [](int cumul, const auto& /*elem*/) { return cumul + 1; });
    }

private:
    void do_alloc()
    {
        m_container.emplace_front();
        m_position = 0;
    }

    container_type m_container;
    std::size_t m_position = { 0 };
};

using string_buffer_ptr = std::shared_ptr<string_buffer>;

struct precondition_failure : std::logic_error
{
    precondition_failure(const char* msg)
      : std::logic_error(msg)
    {}
};

struct postcondition_failure : std::logic_error
{
    postcondition_failure(const char* msg)
      : std::logic_error(msg)
    {}
};

struct numeric_cast_failure : std::logic_error
{
    numeric_cast_failure()
      : std::logic_error("numeric_cast_failure: loss of range")
    {}
};

struct file_access_error
{
    std::string file;
    int error;
};

struct file_access_failure : std::runtime_error
{
    file_access_failure(std::string file, int error)
      : std::runtime_error("file_access_failure")
      , m_error{ std::move(file), error }
    {}

    std::string file() const
    {
        return m_error.file;
    }

    int error() const
    {
        return m_error.error;
    }

private:
    file_access_error m_error;
};

enum class file_format_error_tag
{
    success,
    file_not_found,
    bad_end_of_file,
    bad_general,
    bad_binary,
    bad_objective_function_type,
    bad_objective,
    bad_objective_quadratic,
    bad_bound,
    bad_end,
    bad_constraint,
    too_many_variables,
    too_many_constraints,
    bad_name, // Mainly use when read result file and report unknown variable.
    empty_context
};

struct file_format_error
{
    std::string element;
    int line;
    int column;
    file_format_error_tag tag;
};

struct file_format_failure : std::runtime_error
{
    file_format_failure(std::string element,
                        file_format_error_tag failure,
                        int line,
                        int column)
      : std::runtime_error("file_format_failure")
      , m_error{ std::move(element), line, column, failure }
    {}

    file_format_failure(file_format_error_tag failure, int line, int column)
      : std::runtime_error("file_format_failure")
      , m_error{ std::string(), line, column, failure }
    {}

    file_format_failure(file_format_error_tag failure)
      : std::runtime_error("file_format_failure")
      , m_error{ std::string(), -1, -1, failure }
    {}

    std::string element() const
    {
        return m_error.element;
    }

    int line() const
    {
        return m_error.line;
    }

    int column() const
    {
        return m_error.column;
    }

    file_format_error_tag failure() const
    {
        return m_error.tag;
    }

private:
    file_format_error m_error;
};

enum class problem_definition_error_tag
{
    empty_variables = 1,
    empty_objective_function,
    variable_not_used,
    bad_bound,
    multiple_constraint,
};

struct problem_definition_error
{
    std::string element;
    problem_definition_error_tag tag;
};

struct problem_definition_failure : std::runtime_error
{
    problem_definition_failure(std::string element,
                               problem_definition_error_tag failure)
      : std::runtime_error("problem_definition_failure")
      , m_error{ std::move(element), failure }
    {}

    std::string element() const
    {
        return m_error.element;
    }

    problem_definition_error_tag failure() const
    {
        return m_error.tag;
    }

private:
    problem_definition_error m_error;
};

enum class solver_error_tag
{
    no_solver_available = 1,
    unrealisable_constraint,
    not_enough_memory
};

struct solver_error
{
    solver_error_tag tag;
};

struct solver_failure : std::runtime_error
{
    solver_failure(solver_error_tag failure)
      : std::runtime_error("solver_failure")
      , m_error{ failure }
    {}

    solver_error_tag failure() const
    {
        return m_error.tag;
    }

private:
    solver_error m_error;
};

/**
 * @brief Stores the solver parameters options.
 *
 * @details @c baryonyx::solver_parameters manage behaviour of baryonyx
 *     solvers. If bad value are provided, for instance negative value for the
 *     @c delta or @c kappa-step variables, the default is used.
 *
 */
struct BX_EXPORT solver_parameters
{
    enum class pre_constraint_order
    {
        none = 0, ///< Use the raw_problem (or lp file) order for constraints
                  ///< and variables.
        memory,   ///< Default, use the raw_problem (or lp file) order for
                  ///< constraints but sort the variables to improve the memory
                  ///< cache efficiency.
        less_greater_equal, ///< sort constraints according to their type
                            ///< (first less and finally greater then equal)
                            ///< and sort variable to improve the memory cache
                            ///< efficiency.
        less_equal_greater, ///< sort constraints according to their type
                            ///< (first less and finally equal then greater)
                            ///< and sort variable to improve the memory cache
                            ///< efficiency.
        greater_less_equal, ///< sort constraints according to their type
                            ///< (first greater then less and finally equal)
                            ///< and sort variable to improve the memory cache
                            ///< efficiency.
        greater_equal_less, ///< sort constraints according to their type
                            ///< (first greater then equal and finally less)
                            ///< and sort variable to improve the memory cache
                            ///< efficiency.
        equal_less_greater, ///< sort constraints according to their type
                            ///< (first equal then less and finally greater)
                            ///< and sort variable to improve the memory cache
                            ///< efficiency.
        equal_greater_less, ///< sort constraints according to their type
                            ///< (first equal then greater and finally less)
                            ///< and sort variable to improve the memory cache
                            ///< efficiency.
        p1,                 ///< reserved
        p2,                 ///< reserved
        p3,                 ///< reserved
        p4,                 ///< reserved

    };

    enum class init_policy_type
    {
        bastert,
        pessimistic_solve,
        optimistic_solve,
    };

    enum class floating_point_type
    {
        float_type = 0,
        double_type,
        longdouble_type
    };

    enum class constraint_order
    {
        none = 0,
        reversing,
        random_sorting,
        infeasibility_decr,
        infeasibility_incr,
        lagrangian_decr,
        lagrangian_incr,
        pi_sign_change,
        cycle
    };

    enum class cost_norm_type
    {
        none = 0,
        random,
        l1,
        l2,
        loo
    };

    enum class mode_type : unsigned
    {
        none = 0,
        manual = 1,
        nlopt = 2,
        branch = 4
    };

    /**
     * Preprocessor options available for @c solve or @c optimize function.
     */
    enum class preprocessor_options
    {
        none = 0,
        all
    };

    enum class observer_type
    {
        none,
        pnm,
        file
    };

    enum class solver_type
    {
        bastert,
        random
    };

    /**
     * @brief Solution storage policy for the optimizer mode.
     */
    enum class storage_type
    {
        one,   ///< stores only the best solution found.
        bound, ///< stores the best and the bad solution found.
        five   ///< stores the best five solution found.
    };

    double time_limit{ -1 }; ///< value <= 0 means infinity time.
    double theta{ 0.5 };
    double delta{ -1 }; ///< value == -1 means automatic.
    double kappa_min{ 0 };
    double kappa_step{ 1.e-3 };
    double kappa_max{ 0.6 };
    double alpha{ 1 };
    double pushing_k_factor{ 0.9 };
    double pushing_objective_amplifier{ 5 };
    double init_policy_random{ 0.5 };

    // Probability to insert a bastert solution during the crossover
    // operation.
    double init_crossover_bastert_insertion{ 0.01 };

    double init_crossover_solution_selection_mean{ 0.0 };
    double init_crossover_solution_selection_stddev{ 0.3 };

    // Probability to mutate the solution after the crossover operation.
    // @c init_mutation_variable defines the number of variables to
    // changes, @c init_mutation_value defines the value of the variables.
    // If @c init_mutation_variable_mean and init_mutation_variable_stddev
    // equal zeros, no mutation are done after the crossover.

    double init_mutation_variable_mean{ 0.0001 };
    double init_mutation_variable_stddev{ 0.001 };
    double init_mutation_value_mean{ 0.5 };
    double init_mutation_value_stddev{ 0.2 };

    double init_kappa_improve_start{ 0 };
    double init_kappa_improve_increase{ 0.02 };
    double init_kappa_improve_stop{ 0.2 };

    double w{ 0.05 };       ///< 5% of limit
    unsigned int seed{ 0 }; ///< value == 0 means automatic seed.
    int thread{ 0 };        ///< value <= 0 means automatic detection.
    long int limit{ 1000 }; ///< value <= 0 means infinity loop.
    int print_level{ 0 };
    int pushes_limit{ 100 };
    int pushing_iteration_limit{ 50 };
    int init_population_size{ 100 };
    pre_constraint_order pre_order{ pre_constraint_order::none };
    constraint_order order{ constraint_order::none };
    floating_point_type float_type{ floating_point_type::double_type };
    init_policy_type init_policy{ init_policy_type::bastert };
    cost_norm_type cost_norm{ cost_norm_type::loo };
    mode_type mode{ mode_type::none };
    preprocessor_options preprocessor{ preprocessor_options::all };
    observer_type observer{ observer_type::none };
    storage_type storage{ storage_type::one };
    solver_type solver{ solver_type::bastert };
    bool debug{ false };
};

/**
 * @brief Stores logging system and parameters.
 *
 * @details @c baryonyx::context manages the logging system and stores a set of
 *     parameters for solvers. Default, the logging system is active and use
 *     @c stdout C file structure as output stream. To disable logging system,
 *         use the CMake WITH_LOG=OFF or undefined the @c BARYONYX_ENABLE_LOG
 *         preprocessor value to hide all messages. To disable debug message
 *         only, use the CMake WITH_DEBUG=OFF or undefined the @c
 *         BARYONYX_ENABLE_DEBUG preprocessor value.
 *
 *     The implementation of this class is hidden into private include to
 *     ensure a stable ABI of the Baryonyx library.
 */
struct context;

/**
 * @brief Stores the @c context into smart pointer.
 *
 * @details This type is use in many place of the Baryonyx library and
 *     application to simplify source code. We use a no copyable smart pointer
 *     to ensure thread safe library. Each thread must use its own @c context.
 *     Use the @c copy_context function to simplify the copy. We provide a free
 *     function to delete context pointer to avoid context publication.
 */
using context_ptr = std::unique_ptr<context, void (*)(context*)>;

BX_EXPORT context_ptr
make_context(int verbose_level = 6);

/**
 * @brief Assign baryonyx internal parameters.
 *
 * @details This function is used to provide internal parameters to Baryonyx
 *     library and to ensures a stable API and ABI (for example extends the
 *     solver without change in @c solver_parameters). Normally, this function
 *     is not used.
 *
 * @param ctx Baryonyx's internal state.
 * @param name The name of the parameters.
 * @param value A string representation of the parameters.
 */
BX_EXPORT void
context_set_parameters(const context_ptr& ctx,
                       const std::string& name,
                       std::string value);

/**
 * @brief Affects parameters to the solver.
 *
 * @details For each variables of @c params, value is check and assign to the
 *     solver's internal variables.
 *
 * @param ctx Baryonyx's internal state.
 * @param params Parameters to be copied.
 */
BX_EXPORT void
context_set_solver_parameters(const context_ptr& ctx,
                              const solver_parameters& params);

/**
 * @brief Get solver's internal state.
 *
 * @param ctx Baryonyx's internal state.
 *
 * @return A copy of the internal state.
 */
BX_EXPORT
solver_parameters
context_get_solver_parameters(const context_ptr& ctx);

enum class variable_type
{
    real,
    binary,
    general
};

enum class problem_solver_type
{
    equalities_01,
    equalities_101,
    equalities_Z,
    inequalities_01,
    inequalities_101,
    inequalities_Z
};

enum class objective_function_type
{
    maximize,
    minimize
};

enum class operator_type
{
    equal,
    greater,
    less,
};

struct variable_value
{
    variable_value() = default;

    variable_value(int min_, int max_, variable_type type_)
      : min(min_)
      , max(max_)
      , type(type_)
    {}

    int min{ 0 };
    int max{ std::numeric_limits<int>::infinity() };
    variable_type type{ variable_type::real };
};

struct variables
{
    std::vector<std::string_view> names;
    std::vector<variable_value> values;
};

struct function_element
{
    function_element() = default;

    function_element(int factor_, index variable_index_) noexcept
      : factor(factor_)
      , variable_index(variable_index_)
    {}

    int factor = { 0 };
    index variable_index{ -1 };
};

struct objective_function_element
{
    objective_function_element(double factor_, index variable_index_) noexcept
      : factor(factor_)
      , variable_index(variable_index_)
    {}

    double factor = { 0 };
    index variable_index{ -1 };
};

struct objective_quadratic_element
{
    objective_quadratic_element() noexcept = default;

    constexpr objective_quadratic_element(double factor_,
                                          index variable_index_a_,
                                          index variable_index_b_) noexcept
      : factor(factor_)
      , variable_index_a(variable_index_a_)
      , variable_index_b(variable_index_b_)
    {}

    double factor = 0;
    index variable_index_a = -1;
    index variable_index_b = -1;
};

struct constraint
{
    constraint() = default;

    constraint(std::string_view label_,
               std::vector<function_element>&& elements_,
               int value_,
               int id_)
      : label(label_)
      , elements(elements_)
      , value(value_)
      , id(id_)
    {}

    std::string_view label;
    std::vector<function_element> elements;
    int value = { 0 };
    int id;
};

struct objective_function
{
    std::vector<objective_function_element> elements;
    std::vector<objective_quadratic_element> qelements;
    double value = { 0 };
};

struct affected_variables
{
    void push_back(std::string_view name, bool value)
    {
        names.emplace_back(name);
        values.emplace_back(value);
    }

    std::vector<std::string_view> names;
    std::vector<var_value> values;
};

struct raw_problem
{
    raw_problem() = default;
    raw_problem(file_format_error_tag status_)
      : status(status_)
    {}

    string_buffer_ptr strings;

    objective_function objective;

    std::vector<constraint> equal_constraints;
    std::vector<constraint> greater_constraints;
    std::vector<constraint> less_constraints;

    constexpr operator bool() const noexcept
    {
        return status == file_format_error_tag::success;
    }

    variables vars;

    objective_function_type type = { objective_function_type::maximize };
    file_format_error_tag status = { file_format_error_tag::success };
};

enum class result_status
{
    success,
    internal_error,
    uninitialized,
    time_limit_reached,
    kappa_max_reached,
    limit_reached,
    empty_context
};

struct solution
{
    solution() = default;

    solution(std::vector<var_value> variables_, double value_)
      : variables(std::move(variables_))
      , value(value_)
    {}

    std::vector<var_value> variables;
    double value;
};

struct result
{
    string_buffer_ptr strings;

    result() = default;

    result(result_status status_)
      : status(status_)
    {}

    std::string_view method;
    affected_variables affected_vars;

    std::vector<std::string_view> variable_name;
    std::vector<solution> solutions;

    double duration = 0.0;
    long int loop = 0;
    index variables = 0;
    index constraints = 0;
    index remaining_constraints = std::numeric_limits<index>::max();

    // The variable id with the heaviest load factor i.e. the variable which
    // changes too many times during the @c update_row in-the-middle process.
    int annoying_variable = 0;

    result_status status{ result_status::uninitialized };

    operator bool() const
    {
        return status == result_status::success;
    }
};

/// Function called after the preprocessor.
using solver_started_cb = std::function<void(const solver_parameters& params)>;

/// Function called for each solution improvement.
using solver_updated_cb = std::function<void(int remaining_constraints,
                                             double value,
                                             long int loop,
                                             double duration,
                                             long int reinit_number)>;

/// finish Function called at the end of the computation.
using solver_finished_cb = std::function<void(const result& r)>;

/**
 * @brief Register callback functions.
 * @details These functions are called during computation of the @c solver or
 *     @c optimize functions. They allow to retrieve data during computation.
 *
 * @param ctx Baryonyx's internal state.
 * @param start Function called after the preprocessor.
 * @param update Function called for each solution improvement.
 * @param finish Function called at the end of the computation.
 */
BX_EXPORT void
context_register(const context_ptr& ctx,
                 solver_started_cb start = solver_started_cb(),
                 solver_updated_cb update = solver_updated_cb(),
                 solver_finished_cb finish = solver_finished_cb());

/**
 * Read a @e lp file from the @e file.
 *
 * @exception baryonyx::file_format_error, baryonyx::file_access_error,
 *     std::system_error.
 *
 * @param ctx Baryonyx's internal state.
 * @param filename The file to read.
 */
BX_EXPORT
raw_problem
make_problem(const baryonyx::context_ptr& ctx, const std::string& filename);

/**
 * @brief Read a @c baryonyx::result from a file.
 * @details A @c baryonyx::result file store all meta data into comments and
 *     variable value.
 *
 * @param ctx Baryonyx's internal state.
 * @param filename The file to read.
 */
BX_EXPORT
result
make_result(const baryonyx::context_ptr& ctx, const std::string& filename);

/**
 * @details Try to solve or find a feasible solution for the @c
 *     baryonyx::problem.
 *
 * @param ctx Baryonyx's internal state.
 * @param pb Problem definition.
 *
 * @exception baryonyx::solver_error
 * @exception baryonyx::problem_definition
 */
BX_EXPORT
result
solve(const baryonyx::context_ptr& ctx, const raw_problem& pb);

/**
 * @details Try to optimize the @c baryonyx::problem with a set of
 *     parameters.
 *
 * @param ctx Baryonyx's internal state.
 * @param pb Problem definition.
 *
 * @return A representation of the result.
 *
 * @throw @c baryonyx::solver_error.
 */
BX_EXPORT
result
optimize(const baryonyx::context_ptr& ctx, const raw_problem& pb);

/**
 * @details Try to valid the @c baryonyx::result according to the
 *    @c baryonyx::raw_problem.
 *
 * @param pb Problem definition.
 * @param r A representation of the result of the problem @c pb.
 *
 * @return true if @c r is a solution of the problem @c pb, false otherwise.
 */
BX_EXPORT
bool
is_valid_solution(const raw_problem& pb, const result& r);

/**
 * @details Computes the value of the solution of the @c baryonyx::result
 *    according to the @c baryonyx::raw_problem.
 *
 * @param pb Problem definition.
 * @param r A representation of the result of the problem @c pb.
 *
 * @return the value of the solution if @c r is a solution of the problem
 *    @c pb.
 */
BX_EXPORT
double
compute_solution(const raw_problem& pb, const result& r);
}

#endif