bcp.h

Go to the documentation of this file.

// Copyright (C) 2006 Ivo Nowak and Stefan Vigerske
// All Rights Reserved.
// This code is published under the Common Public License.
//
// Author: Stefan Vigerske

#ifndef BCP_H
#define BCP_H

#include "standard.h"
#include "problem.h"
#include "func.h"
#include "opt.h"
#include "relaxopt.h"
#include "cuts.h"
#include "boxfind.h"

class ExtremePoint : public dvector {
        public:
        SparseVector<double> rmpcolumn;
                double rmpobjcoeff;
                const MIPSolver::ColItem* rmpcolitem;

                ExtremePoint(const dvector& point)
                : dvector(point), rmpcolitem(NULL)
                { }

                ExtremePoint(const dvector& point, Pointer<LinearRelax> linear_relax, int k)
                : dvector(point), rmpcolitem(NULL)
                { set_rmpdata(linear_relax, k);
                }

                void set_rmpdata(Pointer<LinearRelax> linear_relax, int k);
};

#include "node.h"

class ColumnGenerator;
class LagHeu;

class MinlpBCP : public RelaxationSolver {
        friend class ColumnGenerator;
        friend class MinlpNode;
        private:
                Pointer<dvector> sol_C;
                bool sol_C_is_solution;
                
                bool prob_is_convex;
                
                Pointer<MinlpProblem> quad_prob;                

                vector<Pointer<MinlpProblem> > block_prob;
                vector<Pointer<MinlpProblem> > block_convex_prob;

                vector<list<ExtremePoint> > ExtremePoints;

                vector<Pointer<MinlpProblem> > block_sub_convex_prob;

                Pointer<MinlpProblem> sub_convex_prob;

                vector<Pointer<MinlpProblem> > lag_problem;

                Pointer<ColumnGenerator> colgen;

                multimap<double, Pointer<MinlpNode> > bb_tree;

                Pointer<MinlpNode> current_node;

                double gap_tol;

                double bound_impr_tol;

                double start_bb();
                
                bool intgrad_cuts;
                IntervalGradientCutGenerator intgrad_cutgen;
                
                LinearizedConCutGenerator linconcutgen;
                
                bool mip_cuts;

                bool add_sol_candidate(const dvector& x);

                int find_sol_candidates(Pointer<MinlpNode> node);

                int preswitching(Pointer<MinlpNode> node);

                Pointer<LagHeu> lagheu;

                void init();

                void init_block_problems();

                void clean_sub_problems();

                pair<list<ExtremePoint>::iterator, bool> add_ExtremePoint(const dvector &w, int k, Pointer<MinlpNode> = NULL);

                int init_ExtremePoints(Pointer<MinlpNode> node);

                int primal_init_ExtremePoints(const dvector& x, Pointer<MinlpNode> node);

                //$\mu$ is a dual solution point of (C\ext) or (R)
                int dual_init_ExtremePoints(Pointer<MinlpNode> node);

                void prune_ExtremePoints(multimap<double, Pointer<MinlpNode> >& bb_tree);

                void project_ExtremePoints(dvector& x, Pointer<MinlpNode> node);

                // heu_type
                // bound_type
                typedef enum { RMP_bound, NLP_bound, LP_bound, LP_RMP_bound, stop_bound } t_bound_type;
                t_bound_type pre_bound_type;
                t_bound_type maj_bound_type;
                t_bound_type bound_type;
                // lagsolve_type[k]
                enum { BranchCut } lagsolve_type; //BranchCut should be BCP
                // subdiv_type
                enum { BinSubdiv, CostSubdivLag, CostSubdivNewton, BisectSubdiv, RMPSubdiv, ViolSubdiv } subdiv_type;
                
                int subdiv_discrete_emphasis;
                
                enum { BestBound, UnfixedDiscrete } nodeselect_type; 

                int upper_bound_effort_level;

                int pre_bb_max_iter;

                bool lag_cuts;

                int bound_failed;
                int bound_computed;
                double bound_time;
                double init_RMP_time;

                int lagprob_solves;

                double find_solcand_time;
                int nr_solcand_found;

                double subdiv_time;

                int update_ExtremePoints_count;

                Pointer<Timer> timer;
                double max_time;

                bool is_maxcut;

                Pointer<IntervalReduction> intervalreduction;

                bool boxreduce(Pointer<MinlpNode> node, int index, IntervalReduction::which_bound_type which_bound);
                
                bool feasibility_check(Pointer<MinlpNode> node);
                
                multimap<double, Pointer<MinlpNode> >::iterator select_node();

                // --------------------- bounding

                int set_low_bound(Pointer<MinlpNode> node);

                pair<bool, double> improve_bound(Pointer<MinlpNode> node);

                int set_NLP_bound(Pointer<MinlpNode> node, bool improve=false);
                int set_RMP_bound(Pointer<MinlpNode> node);
                int set_LP_bound(Pointer<MinlpNode> node);
                int set_LP_RMP_bound(Pointer<MinlpNode> node);
                int improve_LP_bound(Pointer<MinlpNode> node);

                int update_subdiv_bound(int k, int i, Pointer<MinlpNode> node);

                // --------------- branching

                int subdivide(list<Pointer<MinlpNode> >& nodes, Pointer<MinlpNode> node);

                int bin_subdiv(list<Pointer<MinlpNode> >& nodes, int& subdiv_var, Pointer<MinlpNode> node);

                void cost_subdiv(list<Pointer<MinlpNode> >& nodes, int& subdiv_var, Pointer<MinlpNode> node);

//              void cost_subdiv2(list<Pointer<MinlpNode> >& nodes, Pointer<MinlpNode> node);

                void bisect_subdiv(list<Pointer<MinlpNode> >& nodes, int& subdiv_var, Pointer<MinlpNode> node);

                void viol_subdiv(list<Pointer<MinlpNode> >& nodes, int& subdiv_var, Pointer<MinlpNode> node);

                void rect_subdiv(list<Pointer<MinlpNode> >& nodes, Pointer<MinlpNode> node, int k, int i, double cut);

                int nr_subdiv_contvar;
                int nr_subdiv_bisect;

          // -----------  lagrangian subproblems

                void init_lag_problems(Pointer<MinlpNode> node);

                void update_lag_problems(const dvector& dual_point);
                void update_lag_problem(int k, const dvector& a);

                typedef struct LagSolveStatus_s {
                        set<SolCandidate> solset;
                        int ret;
                        int iter;
                        double lowbound;
                        double value;
                        int new_points;
                } LagSolveStatus;

                void solve_lag_problem(LagSolveStatus& status, int k, Pointer<MinlpNode> node, Pointer<SepQcFunc> temp_cut=NULL);

                // --------------------------- Convergence check

    double conv_rate_cntrl_stopping_rho;
    int conv_rate_cntrl_minor_iter;
    double conv_rate_cntrl_last_major_val;
    double conv_rate_cntrl_last_val;
    double conv_rate_cntrl_first_major_val;
    double conv_rate_cntrl_max_rel_improvement;
    int conv_rate_cntrl_improve_iter;

    int conv_rate_check(double val);

                // ---------------------- Memory control

                int mem_limit;
                void mem_check();

        public:
                MinlpBCP(Pointer<MinlpProblem> orig_prob_, Pointer<MinlpProblem> split_prob_, Pointer<LinearRelax> linear_relax_,
                        bool is_gams_prob=false, double closeval_tol_=0., Pointer<dvector> diam_=NULL, Pointer<Param> param_=NULL,
                        Pointer<ostream> out_solver_p_=out_out_p, Pointer<ostream> out_solver_log_p_=out_log_p);

                virtual ~MinlpBCP();
                
                void set_quad_relax(Pointer<MinlpProblem> quad_prob_);

                void set_convex_prob(Pointer<MinlpProblem> convex_prob_, const Pointer<dvector>& sol_C_=NULL, bool sol_C_is_solution_=false);

                void set_reform(Pointer<Reformulation> reform_, Pointer<dvector> sol_C_, bool sol_C_is_solution_);

                void set_reform(Pointer<Reformulation> reform_);

                void set_linear_relax(Pointer<LinearRelax> linrelax_);
                
                void set_problem_is_convex(bool prob_is_convex_) { prob_is_convex=prob_is_convex_; }

                void set_MINLPData(Pointer<MINLPData> minlpdata_);
                
                void set_timer(Pointer<Timer> timer_);

                int solve();

                int solve(dvector& start);

};

#endif

---