/home/coin/SVN-release/OS-2.1.0/Couenne/src/branch/infeasibility.cpp

Go to the documentation of this file.
00001 /* $Id: infeasibility.cpp 259 2009-10-04 14:20:13Z pbelotti $
00002  *
00003  * Name:    infeasibility.cpp
00004  * Authors: Pietro Belotti, Carnegie Mellon University
00005  * Purpose: Compute infeasibility of a variable, looking at all expressions it appears in
00006  *
00007  * (C) Carnegie-Mellon University, 2008-09.
00008  * This file is licensed under the Common Public License (CPL)
00009  */
00010 
00011 #include "CoinHelperFunctions.hpp"
00012 
00013 #include "CouenneProblem.hpp"
00014 #include "CouenneVarObject.hpp"
00015 
00017 const CouNumber weiMin = 0.8; // for minimum of infeasibilities of nonlinear objects
00018 const CouNumber weiMax = 1.3; //     maximum
00019 const CouNumber weiSum = 0.1; //     sum
00020 const CouNumber weiAvg = 0.0; //     average
00021 
00022 
00026 double CouenneVarObject::infeasibility (const OsiBranchingInformation *info, int &way) const {
00027 
00028   assert (reference_);
00029   int index = reference_ -> Index ();
00030 
00031   /*printf ("===INFEAS %d = %g [%g,%g]\n", 
00032           index, 
00033           info -> solution_ [index], 
00034           info -> lower_ [index],
00035           info -> upper_ [index]);*/
00036 
00037   /*if (info -> lower_ [index] >= 
00038       info -> upper_ [index] - CoinMin (COUENNE_EPS, feas_tolerance_))
00039     return (reference_ -> isInteger ()) ? 
00040     intInfeasibility (info -> solution_ [index]) : 0.;*/
00041 
00042   problem_ -> domain () -> push 
00043     (problem_ -> nVars (),
00044      info -> solution_, 
00045      info -> lower_, 
00046      info -> upper_);
00047 
00048   const std::set <int> &dependence = problem_ -> Dependence () [index];
00049 
00051   CouNumber retval = checkInfeasibility (info);
00053 
00054   if (//(retval > CoinMin (COUENNE_EPS, feas_tolerance_)) &&
00055       (jnlst_ -> ProduceOutput (J_DETAILED, J_BRANCHING))) {
00056     printf ("infeasVar x%d %-10g [", reference_ -> Index (), retval);
00057     reference_             -> print (); 
00058     if ((dependence.size () == 0) && (reference_ -> Image ())) { // if no list, print image
00059       printf (" := ");
00060       reference_ -> Image () -> print ();
00061     }
00062     printf ("]\n");
00063   }
00064 
00065   // add term to stop branching on very tiny intervals
00066 
00067   // Compute the up and down estimates here
00068   // TODO: We probably only have to do that if pseudo costs option has
00069   // been chosen
00070 
00071   const CouenneObject *obj_ignored = NULL; // only care about it in CouenneVarObject.cpp
00072 
00073   CouNumber brkPt = computeBranchingPoint (info, way, obj_ignored);
00074 
00075   if (pseudoMultType_ != PROJECTDIST)
00076     setEstimates (info, &retval, &brkPt);
00077 
00078   if (jnlst_ -> ProduceOutput (J_DETAILED, J_BRANCHING)) {
00079     printf("index = %d up = %e down = %e bounds [%e,%e] brpt = %e\n", 
00080            index, upEstimate_, downEstimate_, 
00081            info -> lower_ [index],
00082            info -> upper_ [index], brkPt);
00083   }
00084 
00085   problem_ -> domain () -> pop (); // domain not used below
00086 
00087   retval = ((retval < CoinMin (COUENNE_EPS, feas_tolerance_)) ? 0. : retval);
00088 
00089   //printf ("infVar x%d ==> returning %g\n", reference_ -> Index (), (reference_ -> isInteger ()) ? 
00090   //CoinMax (retval, intInfeasibility (info -> solution_ [reference_ -> Index ()])) :
00091   //retval);
00092 
00093   return (reference_ -> isInteger ()) ? 
00094     CoinMax (retval, intInfeasibility (info -> solution_ [reference_ -> Index ()])) :
00095     retval;
00096 }
00097 
00098 
00101 double CouenneVarObject::checkInfeasibility (const OsiBranchingInformation * info) const {
00102 
00103   int index = reference_ -> Index ();
00104 
00105   const std::set <int> &dependence = problem_ -> Dependence () [index];
00106 
00107   if (dependence.size () == 0) { // this is a top level auxiliary,
00108                                  // nowhere an independent
00109 
00110     // check first if this variable is fixed. If so, it's useless to branch on it
00111     if (fabs (info -> upper_ [index] - 
00112               info -> lower_ [index]) / 
00113         (1. + fabs (info -> solution_ [index])) < COUENNE_EPS)
00114       return 0.;
00115 
00116     // otherwise, return a nonzero infeasibility, if necessary. It
00117     // might make sense to branch on it
00118     const CouenneObject *obj = problem_ -> Objects () [reference_ -> Index ()];
00119 
00120     double retval = (obj -> Reference ()) ? 
00121       (1. - 1. / (1. + info -> upper_ [index] - info -> lower_ [index])) *
00122       weiSum * obj -> checkInfeasibility (info) : 0.;
00123 
00124     return retval;
00125 
00126     /*return (reference_ -> isInteger ()) ? 
00127       CoinMax (retval, intInfeasibility (info -> solution_ [reference_ -> Index ()])) :
00128       retval;*/
00129 
00130   } else {
00131 
00132     CouNumber 
00133       infsum = 0.,
00134       infmax = 0.,
00135       infmin = COIN_DBL_MAX;
00136 
00137     for (std::set <int>::const_iterator i = dependence.begin ();
00138          i != dependence.end (); ++i) {
00139 
00140       // *i is the index of an auxiliary that depends on reference_
00141 
00142       const CouenneObject *obj = problem_ -> Objects () [*i];
00143       CouNumber infeas = (obj -> Reference ()) ? obj -> checkInfeasibility (info) : 0.;
00144 
00145       if (infeas > infmax) infmax = infeas;
00146       if (infeas < infmin) infmin = infeas;
00147       infsum += infeas;
00148     }
00149 
00150     double retval = 
00151       // neglect it if variable has small bound interval (check
00152       // x84=x83/x5 in csched1.nl)
00153       (1. - 1. / (1. + info -> upper_ [index] - info -> lower_ [index])) *
00154       // to consider maximum, minimum, and sum/avg of the infeasibilities
00155       (weiSum * infsum + 
00156        weiAvg * (infsum / CoinMax (1., (CouNumber) dependence.size ())) + 
00157        weiMin * infmin + 
00158        weiMax * infmax);
00159 
00160     return retval;
00161 
00162     /*return (reference_ -> isInteger ()) ? 
00163       CoinMax (retval, intInfeasibility (info -> solution_ [reference_ -> Index ()])) :
00164       retval;*/
00165   }
00166 }

Generated on Tue Mar 30 03:04:36 2010 by  doxygen 1.4.7