minlpopt.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 MINLPOPT_H
#define MINLPOPT_H

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

#include "decomp.h"
#include "relax.h"

class MinlpOpt;
#include "linrelax.h"

class SolCandidate : public pair<double, dvector> {
        friend ostream& operator<<(ostream& out, const SolCandidate& s) {
                out << s.first << ": " << s.second;
                return out;
        }

        private:
                double closeval_tol;
                Pointer<dvector> diam;

        public:

                SolCandidate(double val, const dvector& x, double closeval_tol_, Pointer<dvector> diam_)
                : pair<double, dvector>(val, x), closeval_tol(closeval_tol_), diam(diam_)
                { }

                bool operator<(const SolCandidate& y) const {
                        if (first<y.first-closeval_tol*(fabs(first)+1)) return true;
                        if (first>y.first+closeval_tol*(fabs(first)+1)) return false;
                        for (int i=0; i<second.dim(); i++)
                                if (fabs(second(i)-y.second(i))>(*diam)(i))
                                        return (second(i)<y.second(i));
                        return false;
                }

};

class Reformulation {
        private:
                MinlpOpt& opt;

                void add_var(vector<vector<Pointer<BlockMatrix> > >& A, vector<vector<Pointer<SepQcFunc> > >& s, MinlpProblem& prob, int k, int index, double lower, double upper, Pointer<char> name=NULL);
                void add_con(vector<vector<Pointer<BlockMatrix> > >& A, vector<vector<Pointer<SepQcFunc> > >& s, MinlpProblem& prob, int c, int k);

        public:
                Pointer<MinlpProblem> ext_prob;
                Pointer<MinlpProblem> ext_quad_prob;
                Pointer<MinlpProblem> ext_convex_prob;

                vector<int> related_t;

                Reformulation(MinlpOpt& opt_)
                : opt(opt_)
                { }

                void reformulate();

                dvector get_short_vector(const dvector &x);
                dvector get_long_vector(const dvector &x);

                bool set_t_block(dvector& x, int k);

};

class LevelCutHandler {
        private:
                list<pair<Pointer<MinlpProblem>, int> > problems_with_levelcut;

                list<Pointer<LinearRelax> > linrelax_with_levelcut;

                double val; // the value of the level cut

        public:

                LevelCutHandler(double init_val=INFINITY)
                : val(init_val)
                {       }
                
                ~LevelCutHandler();

                void add_problem(Pointer<MinlpProblem> prob);
                void add_problem(Pointer<LinearRelax> linear_relax);

                void update_level_cut(double newval);
};

class MinlpOpt : public Solver {
        friend class LinearRelax;
        friend class Reformulation;
        friend int main(int argc, char** argv);
        private:
                Pointer<Param> param;
                
                Pointer<Timer> timer;
                
                Pointer<MINLPData> minlpdata;

                bool is_gams_prob;

                Pointer<MinlpProblem> orig_prob; // (P)

                Pointer<MinlpProblem> split_prob; // (S)

                Pointer<MinlpProblem> quad_prob; // (Q)

                Pointer<MinlpProblem> convex_prob; // (C)

                Pointer<Reformulation> reform;

                vector<vector<double> > min_eigval, max_eigval;

                bool prob_is_convex;

                SparseVector<double> quad_obj_c_add;
                vector<SparseVector<double> > quad_con_c_add;
                SparseVector<double> conv_obj_c_add;
                vector<SparseVector<double> > conv_con_c_add;

                ivector ineq_index;

                Pointer<LinearRelax> linear_relax;

                Pointer<LevelCutHandler> levelcuts;

                IntervalReduction intervalreduction;

                void decompose(); // generates (S)

                bool check_convex(MinlpProblem& prob);

                void quad_relax();

                void convex_relax();

                bool init_called;
                void init();
                void init2();

                double sol_cand_closeval_tol;
                Pointer<dvector> sol_cand_diam;

                enum { box_off, box_C, box_Cext, box_Pext } boxreduce_type;
                int boxreduce_effort;
                double boxreduce_time;

                list<int> unbounded_var;

                Pointer<MinlpProblem> get_convex_prob(Pointer<MinlpProblem> prob);
                Pointer<MinlpProblem> get_convex_prob(Pointer<MinlpProblem> prob, Pointer<MinlpProblem> prob_curv_ref);
                double print_box_reduce_quality(dvector& oldlow, dvector& oldup, Pointer<MinlpProblem> prob, char* prefix);

        public:
                set<SolCandidate> sol_cand;

                Pointer<dvector> sol_Cext;
                bool sol_Cext_is_solution;

                double low_bound;

                MinlpOpt(Pointer<MinlpProblem> prob, Pointer<Param> param_, bool is_gams_prob_=false, Pointer<ostream> out_solver_p=out_out_p, Pointer<ostream> out_solver_log_p=out_log_p);

                void box_reduce0();

                void box_reduce1();

                double box_reduce2();

                void box_reduce3();

                int start_round_part_heu();

                int start_bb();

                void check_initial_point();

                int solve();

                using Solver::solve;
};

#endif

---