Heuristics.hpp

Go to the documentation of this file.
00001 /* $Id: Heuristics.hpp 508 2011-02-15 21:52:44Z pbelotti $
00002  *
00003  * Name:    Heuristics.hpp
00004  * Author:  Andrea Qualizza
00005  * Purpose: 
00006  *
00007  * This file is licensed under the Eclipse Public License (EPL)
00008  */
00009 
00010 #ifndef HEURISTICS_HPP
00011 #define HEURISTICS_HPP
00012 
00013 #include "CoinPackedVector.hpp"
00014 #include "OsiSolverInterface.hpp"
00015 #include "OsiXxxSolverInterface.hpp"
00016 #include "tracer.hpp"
00017 #include "misc_util.hpp"
00018 
00019 
00020 class Heuristics {
00021 private:
00022         const int n_;           // number of variables x_i (involved in quadratic terms)
00023         const int t_;           // number of variables y_i (NOT involved in quadratic terms)
00024         int N_;                 // number of variables x_i + X_ij  (= n*(n+3)/2)
00025         const int cons_;        // number of constraints in the original problem
00026         const double objConst_; // constant to be added to the objective function value
00027         const double *b_;       // objective function coefficients of the variables x_i
00028         const double *c_;       // objective function coefficients of the variables y_i
00029         const double **Q_;      // objective function coefficients of the variables X_ij
00030         const double **origMat_;// original problem constraints (linearized)
00031         const double *origRhs_; // original problem RHS
00032         const char *origSense_; // original problem sense
00033         const double *xlb_;     // original problem lower bounds for x_i
00034         const double *xub_;     // original problem upper bounds for x_i
00035         const double *ylb_;     // original problem lower bounds for y_i
00036         const double *yub_;     // original problem upper bounds for y_i
00037         const OsiSolverInterface *si_;// pointer to the main problem
00038 
00039         double currObj_;        // current quadratic objective 
00040         double bestObj_;        // quadratic objective of bestSol_
00041         double *bestSol_;       // best solution of original problem; dim. N_ + t_
00042 
00043         bool *heurLbRowAdded_;  // used in heurSi to determine which original 
00044                                 // constraints are considered (those with nz at some y_i entries)
00045                                 // the other constraints can be discarded
00046 
00047         double *xxTSol_;        // (x,xxT,y) heuristic solution
00048 
00049         // min norm heuristic variables
00050         double *MNSol_;         // approximate min norm heuristic solution
00051         double *temp_row_;
00052         OsiXxxSolverInterface MNLPSi_; 
00053 
00054         OsiXxxSolverInterface heurLPimproveSi_; // heuristic solution improvement LP solver interface
00055         Tracer *tracer_;        //global tracer
00056 
00057 private:
00058         // Evaluates the current heuristic solution and updates currObj and bestSol if necessary
00059         int update(double*, double);
00060 
00061         // Tries to improve the current solution by fixing the values for x_i and X_ij 
00062         // and optimizing over the y_i variables only.
00063         // Would not produce any improvement if the original problem has no variable y_i (i.e. t=0)
00064         int heurLP_improveSolution(double*);
00065 
00066         // uses the functions heurLP_improveSolution and feasibility check, and updates current & best solutions
00067         int processSol(double*, bool, double*, double*);
00068 
00069         double* xxTHeur();
00070         double* MNHeur();
00071 
00072 public:
00073         // constructor
00074         Heuristics(const int,const int,const int,const double,const double*,const double*,const double**,const double**,const double*,const char*,const double*,const double*,const double*,const double*,const OsiSolverInterface *si,Tracer *tracer);
00075         
00076         // destructor
00077         ~Heuristics();
00078 
00079         // getters
00080         double bestObj() {return bestObj_;}
00081         double* bestSol() {return bestSol_;}
00082         double currObj() {return currObj_;}
00083 
00084         // run heuristics on the current outer approximation solution
00085         int run();
00086 };
00087 
00088 
00089 #endif
00090 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

Generated on 10 Feb 2012 for Couenne by  doxygen 1.6.1