decomp.h

Go to the documentation of this file.
00001 // Copyright (C) 2006 Ivo Nowak and Stefan Vigerske
00002 // All Rights Reserved.
00003 // This code is published under the Common Public License.
00004 //
00005 // Author: Stefan Vigerske
00006 
00007 #ifndef DECOMP_H
00008 #define DECOMP_H
00009 
00010 #include "standard.h"
00011 #include "usermatrix.h"
00012 #include "problem.h"
00013 
00014 class DecompGraph {
00020   friend ostream& operator<<(ostream& out, const DecompGraph& g);
00021 
00022   public:
00023                 class Edge;
00024                 class Node {
00025                         friend class DecompGraph;
00026                         private:
00027                                 int set_component(int comp);
00028                         public:
00029                                 map<int, set<Edge>::iterator> adj;
00030                                 int weight;
00031                                 int component;
00032 
00033                                 Node(int weight_=0)
00034                                 : weight(weight_), component(-1)
00035                                 { }
00036                 };
00037 
00038                 class Edge {
00039                         public:
00040                                 map<int, Node>::iterator node1, node2;
00041                                 mutable int weight;
00042 
00043                                 Edge(int weight_=0)
00044                                 : weight(weight_)
00045                                 { }
00046 
00047                                 Edge(map<int, Node>::iterator node1_, map<int, Node>::iterator node2_, int weight_=0)
00048                                 : node1(node1_), node2(node2_), weight(weight_)
00049                                 { }
00050 
00055 //                              map<int, Node>::iterator neighbour(int index) const {
00056 //                                      return (index==node1->first) ? node2 : node1;
00057 //                              }
00058 
00059                                 Node& neighbour(const Node& node) const {
00060                                         return (&node==&node1->second) ? node2->second : node1->second;
00061                                 }
00062 
00063                                 bool operator<(const Edge& e) const {
00064                                         return pair<int,int>(node1->first, node2->first)<pair<int,int>(e.node1->first, e.node2->first);
00065                                 }
00066                 };
00067 
00068                 map<int, Node> nodes;
00069                 set<Edge> edges;
00070 
00071                 int nrcomp;
00074                 int largest_size;
00075 
00079     DecompGraph()
00080                 : nrcomp(0)
00081                 { }
00082 
00083                 DecompGraph(const SparsityInfo& si);
00084 
00085                 virtual ~DecompGraph() { }
00086 
00087                 map<int, Node>::iterator add_node(int index, int weight=0);
00088 
00089                 set<Edge>::iterator add_edge(map<int, Node>::iterator node1, map<int, Node>::iterator node2, int weight=0);
00090                 set<Edge>::iterator add_edge(int node1, int node2, int weight=0);
00091 
00095         int n() const { return nodes.size(); }
00096 
00100         int m() const { return edges.size(); }
00101 
00102                 void compute_connected_components();
00103 
00104                 void get_component_members(vector<list<int> >& members);
00105 
00106                 void compute_partition(int nparts);
00107 };
00108 
00111 class SplitFunc: public Func {
00112         private:
00115                 const Pointer<Func> orig;
00116 
00119                 ivector indices;
00120 
00123     mutable dvector point;
00124 
00125                 Func::CurvatureType curv_type;
00126 
00127         public:
00130     vector<bool> ignore;
00131 
00138                 SplitFunc(const Pointer<Func>& orig_, const ivector& indices_, const dvector& point_, const vector<int>& ignore_=vector<int>(0))
00139                 : Func(indices_.dim()), orig(orig_), indices(indices_), point(point_), curv_type(orig_->get_curvature()), ignore(indices_.dim(), false)
00140                 { assert(orig!=NULL);
00141                         for (vector<int>::const_iterator it(ignore_.begin()); it!=ignore_.end(); it++) ignore[*it]=true;
00142                 }
00143 
00144                 SplitFunc(const Pointer<Func>& orig_, const ivector& indices_, const dvector& point_, const set<int>& ignore_, Pointer<SparsityInfo> si=NULL)
00145                 : Func(indices_.dim()), orig(orig_), indices(indices_), point(point_), curv_type(orig_->get_curvature()), ignore(indices_.dim(), false)
00146                 { assert(orig!=NULL);
00147                         for (set<int>::const_iterator it(ignore_.begin()); it!=ignore_.end(); ++it) ignore[*it]=true;
00148                         sparsity=si;
00149                 }
00150 
00154                 void set_point(const UserVector<double>& x) const {
00155                         for (int i=0; i<indices.size(); i++)
00156                                 if (!ignore[i]) point[indices[i]]=x(i);
00157                 }
00158 
00159                 double eval(const UserVector<double>& x) const {
00160                         set_point(x);
00161                         return orig->eval(point);
00162                 }
00163 
00164         
00165                 void grad(UserVector<double>& g, const UserVector<double>& x) const {
00166                         set_point(x);
00167                         dvector biggrad(orig->dim());
00168                         orig->grad(biggrad, point);
00169                         g=biggrad(indices);
00170                         for (int i=0; i<indices.size(); i++)
00171                                 if (ignore[i]) g[i]=0.;
00172                 }
00173 
00174                 using Func::grad;
00175 
00176                 void HessMult(UserVector<double>& y, const UserVector<double>& x, const UserVector<double>& z) const {
00177                         set_point(z);
00178                         
00179                         dvector big_x(point);
00180                         for (int i=0; i<indices.size(); i++)
00181                                 if (!ignore[i]) big_x.SetElement(indices[i], x(i));
00182                         
00183                         dvector bighess(orig->dim());
00184                         orig->HessMult(bighess, big_x, point);
00185                         y=bighess(indices);
00186                 }
00187 
00188                 using Func::HessMult;
00189 
00190 #ifdef FILIB_AVAILABLE
00191                         bool is_interval_compliant() const { return orig->is_interval_compliant(); }
00192 
00193                         void set_point(IntervalVector& bigx, const IntervalVector& x) const {
00194                                 for (int i=0; i<indices.size(); i++)
00195                                         if (!ignore[i]) bigx[indices[i]]=x(i);
00196                         }
00197 
00198                         interval<double> eval(const IntervalVector& x) const {
00199                                 IntervalVector bigx(point);
00200                                 set_point(bigx, x);
00201                                 return orig->eval(bigx);
00202                         }
00203 
00204                         void grad(IntervalVector& g, const IntervalVector& x) const {
00205                                 IntervalVector bigx(point);
00206                                 set_point(bigx, x);
00207                                 IntervalVector biggrad(bigx.dim());
00208                                 orig->grad(biggrad, bigx);
00209                                 for (int i=0; i<indices.size(); i++)
00210                                         g[i] = ignore[i] ? interval<double>(0.) : biggrad(indices[i]);
00211                         }
00212 
00213                         int valgrad(interval<double>& val, IntervalVector& y, const IntervalVector& x) const {
00214                                 IntervalVector bigx(point);
00215                                 set_point(bigx, x);
00216                                 IntervalVector biggrad(bigx.dim());
00217                                 int ret=orig->valgrad(val, biggrad, bigx);
00218                                 for (int i=0; i<indices.size(); i++)
00219                                         y[i] = ignore[i] ? interval<double>(0.) : biggrad(indices[i]);
00220                                 return ret;
00221                         }
00222 
00223                 using Func::valgrad;
00224 #endif
00225 
00226                 virtual void set_curvature(CurvatureType ct) { curv_type=ct; };
00227                 virtual CurvatureType get_curvature() const  { return curv_type; };
00228 
00229                 void print(ostream& out) const;
00230 };
00231 
00232 
00233 class SplittingScheme2 {
00234 public:
00239         vector<list<pair<int, int> > > new_pos;
00240 
00243         vector<ivector> newblock;
00244 
00245         SplittingScheme2(const DecompGraph& graph);
00246 };
00247 
00261 class Decomposition {
00262         private:
00265                 bool replace_if_quadratic;
00266 
00269                 int avg_blocksize;
00270 
00273                 Pointer<Param> param;
00274 
00275         public:
00276                 Pointer<set<int> > I_var;
00277 
00281                 Decomposition(Pointer<Param> param_=NULL)
00282                 : param(param_), replace_if_quadratic(param_ ? param_->get_i("Decomposition replace quadratic", 1) : 1),
00283                   avg_blocksize(param_ ? param_->get_i("Decomposition average blocksize", 5) : 5)
00284                 { }
00285 
00286         
00287         void set_sparsity_pattern(MinlpProblem& prob, const vector<vector<dvector> >& sample_set);
00288 
00289         
00300         Pointer<MinlpProblem> decompose(MinlpProblem& prob, vector<vector<dvector> >& sample_set);
00301 
00302         Pointer<MinlpProblem> decompose(MinlpProblem& prob, vector<Pointer<SplittingScheme2> >& ss);
00303         void decompose(SepQcFunc& f, int block_offset, const SepQcFunc& old_f, int k, const SplittingScheme2& ss, Pointer<dvector> primal);
00304 
00305         Pointer<SplittingScheme2> get_splittingscheme(MinlpProblem& prob, int blocknr);
00306 
00307         Pointer<SepQcFunc> decompose(Pointer<Func> old_f, const dvector& primal);
00308 };
00309 
00310 #endif

Generated on Tue Oct 21 03:12:09 2008 for LaGO by  doxygen 1.4.7