lagheu.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 LAGHEU_H
#define LAGHEU_H

#include "standard.h"
#include "problem.h"
#include "relaxopt.h"
#include "linrelax.h"
#include "bcp.h"

class LagHeu : public RelaxationSolver {
        private:
                Pointer<MIPSolver> project_LP;
                Pointer<SparseVector<double> > project_LP_obj;

                list<const MIPSolver::RowItem*> project_LP_cuts;

                int x_con_start;

                Pointer<MIPSolver> lagheu_LP;
                int z_start;

                bool project_and_round_rek(dvector& x, map<int, double>& unfixed, int& switch_count);

                int switch_count_limit;

        protected:
                Pointer<MinlpNode> node;

                vector<list<const MIPSolver::ColItem*> > lagheu_LP_columns;

                void make_project_LP();
                void update_project_LP();

                void update_project_LP_x(const dvector& x);

                MIPSolver::SolutionStatus solve_project_LP(dvector& sol);
                MIPSolver::SolutionStatus solve_project_LP(double& val);

                void project_LP_fix_variable(int i, double val);
                void project_LP_unfix_variable(int i);

                void make_lagheu_LP(double delta);

                MIPSolver::SolutionStatus solve_lagheu_LP();
                MIPSolver::SolutionStatus solve_lagheu_LP(dvector &z, dvector& x);
                MIPSolver::SolutionStatus solve_lagheu_LP(vector<dvector> &z, dvector& x);

                void lagheu_LP_fixblock(int k, const MIPSolver::ColItem* colitem);
                void lagheu_LP_unfixblock(int k);

                double couple_con_violation(const dvector& x);

                double delta;

                bool project_and_round(dvector& x);

        public:
                LagHeu(Pointer<MinlpProblem> orig_prob_, Pointer<LinearRelax> linrelax_, 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)
                : RelaxationSolver(orig_prob_, is_gams_prob, closeval_tol_, diam_, param_, out_solver_p_, out_solver_log_p_),
                  delta(param_->get_d("LagHeu penalty parameter", 10.)), switch_count_limit(2*orig_prob_->i_discr.size())
                {       set_linear_relax(linrelax_);
                }

                void set_linear_relax(Pointer<LinearRelax> linrelax_) {
                        RelaxationSolver::set_linear_relax(linrelax_);
                        make_project_LP();
                }

                virtual int solve(Pointer<MinlpNode> node_)=0;

                int solve() {
                        assert(node);
                        return solve(node);
                }

                using Solver::solve;
};

class LagHeu1 : public LagHeu {

        public:
                LagHeu1(Pointer<MinlpProblem> orig_prob_, Pointer<LinearRelax> linrelax_, 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)
                : LagHeu(orig_prob_, linrelax_, is_gams_prob, closeval_tol_, diam_, param_, out_solver_p_, out_solver_log_p_)
                { }

                int solve(Pointer<MinlpNode> node_);

                using LagHeu::solve;
};

class LagHeu_SimAnnealing : public LagHeu {
        private:
                vector<vector<list<ExtremePoint>::iterator> > Z;

                vector<int> nonsingles;

                int minor_iter_max;

                enum { VIOLATION, DISTANCE } weight_type;

                void get_Wz(dvector& Wz, const ivector& z);

                double weight(const ivector& z, const dvector& Wz);

                void walk(ivector& z, dvector& Wz, double& weight_z, double T, int max_iter);

        public:
                LagHeu_SimAnnealing(Pointer<MinlpProblem> orig_prob_, Pointer<LinearRelax> linrelax_, 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);

                int solve(Pointer<MinlpNode> node_);

                using LagHeu::solve;
};

class LagHeu2 : public LagHeu {
        private:
                dvector x;

                map<pair<double, int>, multimap<double, list<ExtremePoint>::iterator> > W;

                Pointer<MinlpPenaltyFunc> penalty;

                map<double, dvector> candidates;
                int max_candidates;

                int max_ns;

                double ns_done;
                double ns_all;
                int lastprint;

                void search(map<pair<double, int>, multimap<double, list<ExtremePoint>::iterator> >::reverse_iterator it_k, double ns);

                bool project(dvector& res);

                double key(const dvector& x);

        public:
                LagHeu2(Pointer<MinlpProblem> orig_prob_, Pointer<LinearRelax> linrelax_, 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);

                int solve(Pointer<MinlpNode> node_);

                void set_reform(Pointer<Reformulation> reform_);

                using LagHeu::solve;
};

class LagHeu2b : public LagHeu {
        private:
                dvector x;
                vector<dvector> z;

                map<pair<double, int>, multimap<double, list<ExtremePoint>::iterator> > W;

                dvector W_val;
                list<int> unfixed_blocks;

                Pointer<MinlpPenaltyFunc> penalty;

                multimap<double, dvector> candidates;
                int max_candidates;

                int max_ns;

                double ns_done;
                double ns_all;
                int lastprint;

                int block_value(double& val, int k);

                void search(double ns);

                double key();

                bool project();

                bool switch_binaries(double val, bool eq, map<int,double>& coeff);
                void make_binaries_feasible();

                void switch_binaries2(double val, bool eq, map<int,double>& coeff);
                void switch_binaries2_rek(double val, bool eq, double& bestval, dvector& pt, map<int,double>::iterator coeff_it, map<int,double>& coeff);
                void move_continuous(double& val, bool eq, map<int,double>& cont_coeff);                
        public:
                LagHeu2b(Pointer<MinlpProblem> orig_prob_, Pointer<LinearRelax> linrelax_, 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);

                int solve(Pointer<MinlpNode> node_);

                void set_reform(Pointer<Reformulation> reform_);

                using LagHeu::solve;
};

#endif

---