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