boxfind.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 BOXFIND_H
#define BOXFIND_H

#include "standard.h"
#include "param.h"
#include "problem.h"
#include "opt.h"
#include "relax.h"
#include "graph.h"

class BoundsFinder {
        private:
                Pointer<Param> param;

                int method;

                double compute_bound(MinlpProblem& conv_prob, int& ret, int index, int block, bool low);

        public:
                bool low, up, known;

                BoundsFinder(Pointer<Param> param_=NULL);
                
                pair<int,int> compute_bounds(MinlpProblem& prob, vector<bool>& discr);

                pair<int,int> compute_bounds_guess(MinlpProblem& prob);

                pair<int,int> compute_bounds_expensive(MinlpProblem& conv_prob, dvector& lower, dvector& upper, vector<bool>& discr);

                pair<int,int> compute_bounds_expensive2(MinlpProblem& conv_prob, dvector& lower, dvector& upper, vector<bool>& discr);

                void compute_linbounds(MinlpProblem& prob);
};

class DualBounds {
        private:
                Pointer<Param> param;

                Pointer<MinlpProblem> S, C, R;
                vector<Pointer<MinlpProblem> > lag_prob;

                vector<list<int> > lin_con;
                vector<bool> lin_con2;

                int type;

                double dual_bound(UserVector<double>& a);

        public:
                DualBounds(Pointer<MinlpProblem> S_, Pointer<MinlpProblem> C_, Pointer<Param> param_, int type_=1);
        
                int update_box(int n);
                int update_box() { return update_box(S->dim()); }
        
                double obj_bound();
};


class IntervalReduction {
        public:
                typedef enum {LOWER, UPPER, WHATEVER} which_bound_type;
        private:
                class NodeData {
                        friend ostream& operator<<(ostream& out, const NodeData& nd) {
                                if (nd.block_nr>=0) out << nd.block_nr << ',' << nd.block_index;
                                return out;
                        }
                        public:
                                int block_nr, block_index;

                                NodeData(int block_nr_=-1, int block_index_=-1)
                                : block_nr(block_nr_), block_index(block_index_)
                                { }

                                NodeData& operator+=(const NodeData& nd) { return *this; }
                };

                class EdgeData {
                        friend ostream& operator<<(ostream& out, const EdgeData& ed);
                        public:
                                which_bound_type which_bound;
                                int con_nr;
                                double coeff; // the coefficient before the linear variable, this edge is directed to

                                EdgeData(int con_nr_, which_bound_type which_bound_, double coeff_)
                                : con_nr(con_nr_), which_bound(which_bound_), coeff(coeff_)
                                { }

                                bool operator<(const EdgeData& ed) const { return con_nr<ed.con_nr; }

                                const EdgeData& operator+=(const EdgeData& ed) const;
                };
                friend ostream& operator<<(ostream& out, const EdgeData& ed);

                Pointer<MinlpProblem> prob;

                typedef Graph<NodeData,EdgeData,true,true> DependencyGraph;
                DependencyGraph dependency_graph;

                void run(dvector& newlow, dvector& newup, const dvector& oldlow, const dvector& oldup, set<pair<const DependencyGraph::NodeType*, which_bound_type> >& nodeset);

        public:
                bool do_print;
                bool empty_boxes;
                double min_impr;
                set<pair<int, int> > reduced_integer;

                dvector reduction_by_block;
                double reduction;

                IntervalReduction(Pointer<MinlpProblem> prob_=NULL)
                : do_print(false), empty_boxes(false), min_impr(.01)
                { if (prob_) set_problem(prob_);
                }

                void set_problem(Pointer<MinlpProblem> prob_);

                void compute(dvector& newlow, dvector& newup, const dvector& oldlow, const dvector& oldup);
                void compute(dvector& newlow, dvector& newup, const dvector& oldlow, const dvector& oldup, set<pair<int, which_bound_type> >& startset);

                void print_small_boxes(dvector& low, dvector& up);
};


class BoundsFinderLinear {
        private:
                Pointer<Param> param;

                Pointer<MinlpProblem> prob;

                Pointer<MIPSolver> solver;

                MIPSolver::SolutionStatus compute_bound(double& bound, int index, bool low);

        public:
                bool low, up, known;

                BoundsFinderLinear(Pointer<MinlpProblem> prob_, Pointer<Param> param_);

                int compute(dvector& newlow, dvector& newup, set<pair<int, IntervalReduction::which_bound_type> >* changed_var=NULL, double min_impr=0.01);

};

#endif

---