cuts.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 CUTS_H
#define CUTS_H

#include "standard.h"
#include "opt.h"
#include "MINLPData.h"

class IntervalGradientCut {
        public:
                class ConstraintInfo {
                        public:
                                double c;
                                Pointer<UserVector<double> > b_x;
                                Pointer<UserVector<double> > b_w;
                                Pointer<UserVector<double> > b_z;

                                ConstraintInfo(const Pointer<UserVector<double> >& b_x_, const Pointer<UserVector<double> >& b_w_, const Pointer<UserVector<double> >& b_z_, double c_)
                                : b_x(b_x_), b_w(b_w_), b_z(b_z_), c(c_)
                                { }
                };

                list<ConstraintInfo> coninfos;
                int coninfos_size;

                dvector ref_x;
                dvector w_z_up;
                ivector indices;

                IntervalGradientCut(const dvector& ref_x_, const dvector& w_z_up_, const ivector& indices_)
                : ref_x(ref_x_), w_z_up(w_z_up_), indices(indices_), coninfos_size(0)
                { }
};


class SimpleCut {
        friend ostream& operator<<(ostream& out, const SimpleCut& cut);
        public:
                Pointer<UserVector<double> > coeff;
                double constant;
                
                SimpleCut()
                : constant(0.)
                { }
        
                SimpleCut(const Pointer<UserVector<double> >& coeff_, double constant_)
                : coeff(coeff_), constant(constant_)
                { }
                
                bool feasible(const dvector& x, double tol) const {
                        return 2*(*coeff*x)+constant<tol;
                }
                
                void scale(double max_coeff=100.);
};

class LinearizationCut : public SimpleCut {
        public:
                LinearizationCut()
                : objcon_nr(-2), derived_from_lower_part(true)
                { }

                LinearizationCut(const Pointer<UserVector<double> >& coeff_, double constant_)
                : SimpleCut(coeff_, constant_), objcon_nr(-2), derived_from_lower_part(true)
                { }

                LinearizationCut(const Pointer<UserVector<double> >& coeff_, double constant_, int objcon_nr_, bool derived_from_lower_part_, const dvector& x_, double t_)
                : SimpleCut(coeff_, constant_), objcon_nr(objcon_nr_), derived_from_lower_part(derived_from_lower_part_), x(x_), t_value(t_)
                { }
                
                int objcon_nr;
                bool derived_from_lower_part;
                dvector x;
                double t_value;
                
};


class IntervalGradientCutGenerator {
        private:
                Pointer<MinlpProblem> prob;

                vector<Pointer<SparsityInfo> > sparsity;

        public:
                IntervalGradientCutGenerator(Pointer<MinlpProblem> prob_=NULL)
                : prob(prob_)
                { prob->get_sparsity(sparsity); }

                void set_problem(Pointer<MinlpProblem> prob_) { prob=prob_; prob->get_sparsity(sparsity); }

                Pointer<IntervalGradientCut> get_cuts(const dvector& x, int k, const dvector& low, const dvector& up);

                Pointer<IntervalGradientCut> update_cuts(Pointer<IntervalGradientCut> cut, int k, const dvector& low, const dvector& up) {
                        return get_cuts(cut->ref_x, k, low, up);
                }
};

class CutPool;
class MinlpNode;

template <class CutType> class Cut {
        friend class CutPool;
//      friend ostream& operator<<(ostream& out, Cut<CutType>& cut);

        class NodeInfo {
                public:
                        int inactive_time;

                        NodeInfo()
                        : inactive_time(0)
                        { }

                        NodeInfo(const NodeInfo& cni)
                        : inactive_time(cni.inactive_time)
                        { }
        };

        private:
                Pointer<CutType> cut;

                map<Pointer<MinlpNode>, NodeInfo> nodes;

                bool global;
                int inactive_time_global;

                bool tagged;

        public:
                Cut(Pointer<CutType> cut_, Pointer<MinlpNode> node=NULL)
                : cut(cut_), global(false), tagged(false), inactive_time_global(0)
                { if (node) add_node(node);
                        else global=true;
                }

                Cut(const Cut<CutType>& cut_)
                : cut(cut_.cut), nodes(cut_.nodes), global(cut_.global), tagged(cut_.tagged), inactive_time_global(cut_.inactive_time_global)
                { }

                virtual ~Cut();

                bool valid(const Pointer<MinlpNode>& node=NULL) const {
                        return global || (node && nodes.count(node));
                }

                void add_node(Pointer<MinlpNode> node) {
                        nodes.insert(pair<Pointer<MinlpNode>, NodeInfo>(node, NodeInfo()));
                }

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

                bool remove_node(Pointer<MinlpNode> node);

                pair<bool, bool> set_inactivetime(Pointer<MinlpNode> node, bool increase, int limit);

                const CutType& get_cut() const { return *cut; }
};

class CutPool {
        private:
                list<Cut<SimpleCut> > simplecuts;

                list<Cut<LinearizationCut> > linearizationcuts;

                list<Cut<IntervalGradientCut> > intgradcuts;

                int cuts_size;

                int inactivetime_limit_global;
                int inactivetime_limit_local;

        public:
                typedef enum { SIMPLE, LINEARIZATION, INTERVALGRADIENT } CutType;

                class CutInfo {
                        friend class CutPool;
                        public:
                                list<Cut<SimpleCut> >::iterator it_simplecuts;

                                list<Cut<IntervalGradientCut> >::iterator it_intgradcuts;
                                
                                list<Cut<LinearizationCut> >::iterator it_linearizationcuts;

                                CutType type;

                                int block_nr;
                                bool inactive;
                                bool removed;

                                list<const MIPSolver::RowItem*> rowitems;

                                list<const MIPSolver::ColItem*> colitems;

                                CutInfo(list<Cut<SimpleCut> >::iterator& it, int bnr)
                                : it_simplecuts(it), type(SIMPLE), block_nr(bnr), inactive(false), removed(false)
                                { }

                                CutInfo(list<Cut<LinearizationCut> >::iterator& it, int bnr)
                                : it_linearizationcuts(it), type(LINEARIZATION), block_nr(bnr), inactive(false), removed(false)
                                { }

                                CutInfo(list<Cut<IntervalGradientCut> >::iterator& it_intgradcuts_, int bnr)
                                : it_intgradcuts(it_intgradcuts_), type(INTERVALGRADIENT), block_nr(bnr), inactive(false), removed(false)
                                { }

                                pair<bool, bool> set_inactivetime(Pointer<MinlpNode> node, int limit);
                };

                CutPool(int inactivetime_limit_global_=10, int inactivetime_limit_local_=3)
                : inactivetime_limit_global(inactivetime_limit_global_), inactivetime_limit_local(inactivetime_limit_local_), cuts_size(0)
                { }

                CutPool(const CutPool& cutpool, Pointer<MinlpNode> node=NULL);
                
                CutInfo add_cut(Pointer<SimpleCut>, Pointer<MinlpNode> node, int blocknr=-1);

                CutInfo add_cut(Pointer<IntervalGradientCut> intgradcut, Pointer<MinlpNode> node, int blocknr);

                CutInfo add_cut(Pointer<LinearizationCut> linearizationcut, Pointer<MinlpNode> node, int blocknr);

                void integrate(const CutPool& cutpool, Pointer<MinlpNode> node=NULL);

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

                void remove_node(Pointer<MinlpNode> node);

                void update_nodeinfo(list<CutInfo>& cutinfos, int block_nr, Pointer<MinlpNode> node);

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

                void update_cuts(Pointer<MinlpNode> node, int blocknr, const dvector& low, const dvector& up, IntervalGradientCutGenerator& generator, LinearizedConCutGenerator& linconcutgen);

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

                int nr_local_cuts(Pointer<MinlpNode> node) const;
                int nr_global_cuts() const;
                int nr_all_cuts() const { return cuts_size; }
};

class LinearizedConCutGenerator {
        private:
                Pointer<MinlpProblem> prob;
                
                Pointer<MINLPData> minlpdata;
                
                Pointer<Reformulation> reform;
                
                static const double tol;

        public:
                double max_violation;   
        
                LinearizedConCutGenerator(Pointer<MinlpProblem> prob_, Pointer<MINLPData> minlpdata_=NULL, Pointer<Reformulation> reform_=NULL);

                LinearizationCut get_cut(const dvector& x, int c, int block_nr, double val=INFINITY);

                int get_cuts(list<pair<LinearizationCut, pair<int, bool> > >& cuts, const MINLPData::ObjCon& objcon, int objcon_nr, const dvector& x, const dvector& lower, const dvector& upper, bool violated_polyest_only=false);
                int get_cuts(list<pair<LinearizationCut, pair<int, bool> > >& cuts, const MINLPData::Constraint& objcon, int objcon_nr, const dvector& x, const dvector& lower, const dvector& upper, bool violated_polyest_only=false);
                int get_cuts(list<pair<LinearizationCut, pair<int, bool> > >& cuts, const dvector& x, const dvector& lower, const dvector& upper, bool violated_polyest_only=false);
                
                Pointer<LinearizationCut> update_cut(LinearizationCut& cut, unsigned int block_nr, const dvector& lower, const dvector& upper);
                
                void set_problem(Pointer<MinlpProblem> prob_) { prob=prob_; }
                void set_reform(Pointer<Reformulation> reform_);
                void set_MINLPData(Pointer<MINLPData> minlpdata_) { minlpdata=minlpdata_; }
                
};

class LinearRelax;

#endif

---