linrelax.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 LINRELAX_H
#define LINRELAX_H

#include "standard.h"
#include "problem.h"
#include "cuts.h"
#include "boxfind.h"

class MinlpNode;
class LinearRelaxSolver;
class LinearRelaxSolverGeneral;
class LinearRelaxSolverMIP;

class LinearRelax {
        friend class LinearRelaxSolverGeneral;
        friend class LinearRelaxSolverMIP;
        friend ostream& operator<<(ostream& out, LinearRelax& linrelax);
        public:
        class LinConstraint {
                friend ostream& operator<<(ostream& out, const LinConstraint& lincon);
                public:
                        vector<Pointer<UserVector<double> > > b;
                        double c;
                        bool eq;
                        Pointer<char> name;

                        LinConstraint(vector<Pointer<UserVector<double> > >& b_, double c_, bool eq_, Pointer<char> name_=NULL)
                        : b(b_), c(c_), eq(eq_), name(name_)
                        { }

                        LinConstraint(Pointer<UserVector<double> > b_, double c_, bool eq_, Pointer<char> name_=NULL)
                        : b(1, b_), c(c_), eq(eq_), name(name_)
                        { }

                        LinConstraint(const LinConstraint& lincon)
                        : b(lincon.b), c(lincon.c), eq(lincon.eq), name(lincon.name)
                        { }
        };

        private:
                Pointer<Param> param;

                int max_cutsnr;

                int inactivetime_limit_global;
                int inactivetime_limit_local;

                vector<Pointer<CutPool> > cutpool;
                
                Pointer<CutPool> cutpoolcoupling;

                dvector lower, upper;
                
                vector<int> i_discr;

                Pointer<LinearRelaxSolver> solver;

                MinlpNode* solver_node;

                list<LinConstraint>::iterator levelcut_pos;

                bool box_reduce(pair<double,double>& newbox, const pair<double,double>& oldbox, int k, int i, bool discrete=false, bool unknown_only=false);

        public:
                Pointer<SepQcFunc> obj;
                vector<list<LinConstraint> > block_con;
                list<LinConstraint> couple_con;
                int core_size() const;

                set<pair<int, int> > boxreduce_reduced_integer;

                LinearRelax(Pointer<Param> param_);

                LinearRelax(const LinearRelax& linrelax, int k, Pointer<MinlpNode> node=NULL, Pointer<SepQcFunc> alt_obj=NULL);

                void init(Pointer<MinlpProblem> convex_prob, const vector<int>& i_discr, Pointer<dvector> feas_point=NULL, bool is_feas=true);

                void add_level_cut(double level);
                void update_level_cut(double newlevel);

                void add_cut(const Pointer<SimpleCut>& cut, int k, const Pointer<MinlpNode>& node=NULL);
                
                void add_cut(const Pointer<SimpleCut>& cut, const Pointer<MinlpNode>& node=NULL) {
                        add_cut(cut, -1, node);
                }

                void add_cut(const Pointer<LinearizationCut>& cut, int k, const Pointer<MinlpNode>& node=NULL);

                void add_cut(Pointer<IntervalGradientCut> intgradcut, int k, Pointer<MinlpNode> node=NULL);

                void integrate(LinearRelax& linrelax, int k, Pointer<MinlpNode> node=NULL);

                void get_cuts(list<CutPool::CutInfo>& cutinfos, Pointer<MinlpNode> node=NULL);

                void update_cuts(Pointer<MinlpNode> node, int k, IntervalGradientCutGenerator& generator, LinearizedConCutGenerator& linconcutgen);

                double get_upper_bound();

                bool cutlimit_reached() const { return nr_all_cuts()>=max_cutsnr; }

                int nr_local_cuts(Pointer<MinlpNode> node) const;
                int nr_global_cuts() const;
                int nr_all_cuts() const;

                void remove_node(Pointer<MinlpNode> node);

                void duplicate_nodeinfo(Pointer<MinlpNode> oldnode, Pointer<MinlpNode> newnode);

                void clear_solver();
                bool feasible(Pointer<MinlpNode> node, double tol=1E-4);

                bool point_feasible(Pointer<MinlpNode> node, const dvector& x, double tol=1E-4) const;

                int solve(dvector& sol_point, double& value, Pointer<MinlpNode> node, dvector* dual_point=NULL, double tol=1E-4);

                double box_reduce(Pointer<MinlpNode> node, int k, const vector<bool>& discr, bool unknown_only=false, set<pair<int, IntervalReduction::which_bound_type> >* changed_var=NULL, double min_impr=0.01);
                double box_reduce(Pointer<MinlpNode> node, const vector<bool>& discr, bool unknown_only=false, set<pair<int, IntervalReduction::which_bound_type> >* changed_var=NULL, double min_impr=0.01);
                double box_reduce(dvector& newlow, dvector& newup, const vector<bool>& discr, bool unknown_only=false, set<pair<int, IntervalReduction::which_bound_type> >* changed_var=NULL, double min_impr=0.01);

                void set_box(const dvector& lower_, const dvector& upper_) {
                        lower=lower_;
                        upper=upper_;
                }
                
                int generate_cuts(Pointer<MinlpNode> node);
};

class LinearRelaxSolver : public Solver {
        protected:
                LinearRelax& linrelax;

        public:
                list<CutPool::CutInfo> cutinfos;
                
                dvector duals;

                LinearRelaxSolver(LinearRelax& linrelax_);

                virtual ~LinearRelaxSolver();

                virtual void init()=0;

                virtual void reset()=0;

                virtual void construct(Pointer<MinlpNode> node=NULL)=0;

//              virtual void update(Pointer<MinlpNode> node=NULL)=0;

                virtual void add_cut(const CutPool::CutInfo& cutinfo)=0;

                virtual void set_objective(Pointer<SepQcFunc> obj)=0;

                virtual void update_levelcut(double newlevel)=0;

                virtual bool feasible()=0;

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

                virtual void remove_cuts()=0;

                int solve();

                using Solver::solve;

                virtual int generate_cuts(list<Pointer<SimpleCut> >& cuts)=0;
};

class LinearRelaxSolverGeneral : public LinearRelaxSolver {
        private:
                Pointer<MinlpProblem> prob;

                int cutstart;
                int levelcut_pos;

        public:
                LinearRelaxSolverGeneral(LinearRelax& linrelax_)
                : LinearRelaxSolver(linrelax_), cutstart(0), levelcut_pos(-1)
                { tol=1E-4;
                        init();
                }

                void init();

                void reset();

                void construct(Pointer<MinlpNode> node=NULL);

                void add_cut(const CutPool::CutInfo& cutinfo);

                void set_objective(Pointer<SepQcFunc> obj);

                void update_levelcut(double newlevel);

                bool feasible();

                int solve(Pointer<MinlpNode> node=NULL);

                using LinearRelaxSolver::solve;
                
                void remove_cuts();

                int generate_cuts(list<Pointer<SimpleCut> >& cuts) { return 0; }
};

class LinearRelaxSolverMIP : public LinearRelaxSolver {
        private:
                MipProblem mip;

                Pointer<MIPSolver> solver;

                int levelcut_pos;
                
                int intervalgradcutvars_start;

                void add_intervalgradientcut(CutPool::CutInfo& cutinfo);

        public:
                LinearRelaxSolverMIP(LinearRelax& linrelax_);
                void init();

                void reset();

                void construct(Pointer<MinlpNode> node=NULL);

                void add_cut(const CutPool::CutInfo& cutinfo);

                void set_objective(Pointer<SepQcFunc> obj);

                void update_levelcut(double newlevel);

                bool feasible();

                int solve(Pointer<MinlpNode> node=NULL);

                using LinearRelaxSolver::solve;
                
                void remove_cuts();
                
                int generate_cuts(list<Pointer<SimpleCut> >& cuts);
};

#endif

---