MI_Solver.hpp

Go to the documentation of this file.

#ifndef ZONOOPT_MI_SOLVER_
#define ZONOOPT_MI_SOLVER_
 
#include <thread>
#include <atomic>
#include <mutex>
#include <condition_variable>
#include <sstream>
#include <iomanip>
#include <variant>
#include <memory_resource>
#include <cmath>
 
#include "MI_DataStructures.hpp"
#include "SolverDataStructures.hpp"
#include "ADMM.hpp"
 
namespace ZonoOpt::detail {
 
    class MI_Solver
    {
    public:
        explicit MI_Solver(const MI_data& data);
 
        // solve
        OptSolution solve();
 
        // branch and bound where all possible solutions are returned
        std::pair<std::vector<OptSolution>, OptSolution> multi_solve(int max_sols = std::numeric_limits<int>::max());
 
 
    private:
 
        struct NodeDeleter
        {
            std::pmr::synchronized_pool_resource* pool_ptr;
 
            explicit NodeDeleter(std::pmr::synchronized_pool_resource* pool_ptr) : pool_ptr(pool_ptr) {}
 
            void operator()(Node* node) const
            {
                if (node)
                {
                    node->~Node();
                    pool_ptr->deallocate(node, sizeof(Node), alignof(Node));
                }
            }
        };
 
        struct NodeCompare
        {
            bool operator()(const std::unique_ptr<Node, NodeDeleter>& n1, const std::unique_ptr<Node, NodeDeleter>& n2) const
            {
                return n1->solution.J > n2->solution.J;
            }
        };
 
        const MI_data data;
        std::pmr::synchronized_pool_resource pool;
        NodeCompare comp;
 
        PriorityQueuePrunable<std::unique_ptr<Node, NodeDeleter>, NodeCompare> node_queue; // priority queue for nodes
        mutable std::mutex pq_mtx;
        std::condition_variable pq_cv_bnb; // condition variables for branch-and-bound threads
 
        bool multi_sol = false;
        std::shared_ptr<ADMM_data> bnb_data; // data for branch-and-bound threads
 
        std::atomic<bool> converged = false;
        std::atomic<bool> done = false;
        std::atomic<bool> feasible = false; // feasible solution found
        std::atomic<long int> qp_iter = 0; // number of QP iterations
        std::atomic<int> iter = 0; // number of iterations
        std::atomic<zono_float> J_max = std::numeric_limits<zono_float>::infinity(); // upper bound
        ThreadSafeAccess<Eigen::Vector<zono_float, -1>> z, x, u; // solution vector
        std::atomic<zono_float> primal_residual = std::numeric_limits<zono_float>::infinity();
        std::atomic<zono_float> dual_residual = std::numeric_limits<zono_float>::infinity();
        ThreadSafeIncrementable<double> total_startup_time{0.0};
        ThreadSafeIncrementable<double> total_run_time{0.0};
        ThreadSafeMultiset J_threads; // threads for J values
        ThreadSafeVector<OptSolution> solutions; // solutions found
 
        // allocate nodes
        std::unique_ptr<Node, NodeDeleter> make_node(const std::shared_ptr<ADMM_data>& data);
 
        std::unique_ptr<Node, NodeDeleter> clone_node(const std::unique_ptr<Node, NodeDeleter>& other);
 
        // solver core
        std::variant<OptSolution, std::pair<std::vector<OptSolution>, OptSolution>> solver_core(
                int max_sols = std::numeric_limits<int>::max());
 
        // solve node and branch
        void solve_and_branch(const std::unique_ptr<Node, NodeDeleter>& node);
 
        // check if integer feasible, xb is vector of relaxed binary variables
        bool is_integer_feasible(Eigen::Ref<const Eigen::Vector<zono_float,-1>> xb) const;
 
        // most fractional branching
        void branch_most_frac(const std::unique_ptr<Node, NodeDeleter>& node);
 
        // loop for multithreading
        void worker_loop();
 
        // push node to queue
        void push_node(std::unique_ptr<Node, NodeDeleter>&& node);
 
        // prune
        void prune(zono_float J_max);
 
        // check if 2 solutions correspond to the same binaries
        bool check_bin_equal(const OptSolution& sol1, const OptSolution& sol2) const;
 
    };
 
} // namespace ZonoOpt::detail
     
 
 
 
#endif