/home/coin/SVN-release/OS-2.4.0/Couenne/src/branch/CouenneChooseVariable.cpp

Go to the documentation of this file.
00001 /* $Id: CouenneChooseVariable.cpp 707 2011-06-22 20:17:18Z pbelotti $
00002  *
00003  * Name:    CouenneChooseVariable.cpp
00004  * Authors: Pierre Bonami, IBM Corp.
00005  *          Pietro Belotti, Carnegie Mellon University
00006  * Purpose: Branching object for choosing branching auxiliary variable
00007  *
00008  * (C) Carnegie-Mellon University, 2006-10.
00009  * This file is licensed under the Eclipse Public License (EPL)
00010  */
00011 
00012 #include "OsiSolverInterface.hpp"
00013 
00014 #include "CouenneChooseVariable.hpp"
00015 #include "CouenneProblem.hpp"
00016 #include "CouenneProblemElem.hpp"
00017 #include "CouenneExprVar.hpp"
00018 #include "CouenneObject.hpp"
00019 
00020 using namespace Couenne;
00021 
00023 CouenneChooseVariable::CouenneChooseVariable (): 
00024   OsiChooseVariable (),
00025   problem_ (NULL) {}
00026 
00027 
00029 CouenneChooseVariable::CouenneChooseVariable (const OsiSolverInterface *si,
00030                                               CouenneProblem *p,
00031                                               JnlstPtr jnlst):
00032   OsiChooseVariable (si),
00033   problem_ (p),
00034   jnlst_   (jnlst) {}
00035 
00036 
00038 CouenneChooseVariable::CouenneChooseVariable (const CouenneChooseVariable &source):
00039   OsiChooseVariable (source),
00040   problem_ (source.problem_),
00041   jnlst_   (source.jnlst_) {}
00042 
00043 
00045 CouenneChooseVariable & CouenneChooseVariable::operator= (const CouenneChooseVariable& rhs) {
00046   problem_ = rhs.problem_; 
00047   jnlst_   = rhs.jnlst_;
00048   return *this;
00049 }
00050 
00051 
00055 int CouenneChooseVariable::setupList (OsiBranchingInformation *info, bool initialize) {
00056 
00057   problem_ -> domain () -> push 
00058     (problem_ -> nVars (),
00059      info -> solution_, 
00060      info -> lower_, 
00061      info -> upper_);
00062 
00063 #ifdef COIN_HAS_NTY
00064 
00065   if (problem_ -> orbitalBranching ()) {
00066 
00067     problem_ -> ChangeBounds (info -> lower_,
00068                               info -> upper_, 
00069                               problem_ -> nVars ());
00070     
00071     problem_ -> Compute_Symmetry();
00072   }
00073 
00074 #endif
00075 
00076   jnlst_ -> Printf (Ipopt::J_ITERSUMMARY, J_BRANCHING, "----------------- setup list\n");
00077 
00078   if (jnlst_ -> ProduceOutput (Ipopt::J_DETAILED, J_BRANCHING)) {
00079 
00080     printf ("----------------- setup list\n");
00081 
00082     for (int i=0; i<problem_ -> domain () -> current () -> Dimension (); i++) 
00083 
00084       if (problem_ -> Var (i) -> Multiplicity () > 0) {
00085         printf ("%4d %20.4g [%20.4g %20.4g]", i,
00086                 info -> solution_ [i],
00087                 info -> lower_ [i],
00088                 info -> upper_ [i]);
00089 
00090         if (problem_ -> Var (i) -> Type () == AUX) {
00091           printf (" expr. %20.4g [%+e] ", 
00092                   (*(problem_ -> Var (i) -> Image ())) (), 
00093                   (*(problem_ -> Var (i) -> Image ())) () - info -> solution_ [i]);
00094           problem_ -> Var (i) -> Image () -> print ();
00095         }
00096 
00097         printf ("\n");
00098       }
00099   }
00100 
00101   // Make it stable, in OsiChooseVariable::setupList() numberObjects must be 0.
00102   int retval = (solver_ -> numberObjects ()) ? 
00103     OsiChooseVariable::setupList (info, initialize) : 0;
00104 
00105   problem_ -> domain () -> pop ();
00106 
00107   jnlst_ -> Printf (Ipopt::J_ITERSUMMARY, J_BRANCHING, "----------------- setup list done, %d objects\n", 
00108                     retval);
00109 
00110   return retval;
00111 }
00112 
00113 
00115 // int CouenneChooseVariable::chooseVariable (OsiSolverInterface * solver, 
00116 //                                         OsiBranchingInformation *info, 
00117 //                                         bool fixVariables) {
00118 
00119 //   // !!!should go -- just choose the first element
00120 //   problem_ -> domain () -> push 
00121 //     (problem_ -> nVars (),
00122 //      info -> solution_, 
00123 //      info -> lower_, 
00124 //      info -> upper_);
00125 
00126 //   int retval = OsiChooseVariable::chooseVariable (solver, info, fixVariables);
00127 
00128 //   problem_ -> domain () -> pop ();
00129 
00130 //   return retval;
00131 // }
00132 
00133 
00134 // Returns true if solution looks feasible against given objects
00135 bool CouenneChooseVariable::feasibleSolution (const OsiBranchingInformation * info,
00136                                               const double * solution,
00137                                               int numberObjects,
00138                                               const OsiObject ** objects) {
00139 
00140   double obj = solution [problem_ -> Obj (0) -> Body () -> Index ()];
00141 
00142 #ifdef FM_CHECKNLP2
00143   bool isFeas = problem_->checkNLP2(solution,
00144                                     0, false, // do not care about obj
00145                                     true, // stopAtFirstViol
00146                                     true, // checkAll
00147                                     problem_->getFeasTol());
00148   
00149   return isFeas;
00150 #else
00151   return problem_ -> checkNLP(solution, obj);
00152 #endif
00153 }
00154 
00155 
00157 void CouenneChooseVariable::registerOptions (Ipopt::SmartPtr <Bonmin::RegisteredOptions> roptions) {
00158 
00159   roptions -> AddStringOption2 
00160     ("enable_sos",
00161      "Use Special Ordered Sets (SOS) as indicated in the MINLP model",
00162      "no",
00163      "no","",
00164      "yes","");
00165 
00166   roptions -> AddStringOption2
00167     ("branch_fbbt",
00168      "Apply bound tightening before branching",
00169      "yes",
00170      "no","",
00171      "yes","",
00172      "After applying a branching rule and before re-solving the subproblem, apply Bound Tightening.");
00173 
00174   roptions -> AddStringOption2
00175     ("branch_conv_cuts",
00176      "Apply convexification cuts before branching (for now only within strong branching)",
00177      "yes",
00178      "no","",
00179      "yes","",
00180      "After applying a branching rule and before resolving the subproblem, generate a round of linearization cuts with the new bounds enforced by the rule."
00181     );
00182 
00183   roptions -> AddStringOption6
00184     ("branch_pt_select",
00185      "Chooses branching point selection strategy",
00186      "mid-point",
00187      "lp-clamped", "LP point clamped in [k,1-k] of the bound intervals (k defined by lp_clamp)",
00188      "lp-central", "LP point if within [k,1-k] of the bound intervals, middle point otherwise" 
00189      "(k defined by branch_lp_clamp)",
00190      "balanced", "minimizes max distance from curve to convexification",
00191      "min-area", "minimizes total area of the two convexifications",
00192      "mid-point", "convex combination of current point and mid point",
00193      "no-branch", "do not branch, return null infeasibility; for testing purposes only",
00194      "");
00195 
00196   std::string br_ops [] = {"prod", "div", "exp", "log", "trig", 
00197                            "pow",  "negpow", "sqr", "cube", ""};
00198 
00199   for (int i=0; br_ops [i] != ""; i++) {
00200 
00201     char optname [40], optname2 [40], description [90];
00202     sprintf (optname,  "branch_pt_select_%s", br_ops [i].c_str ());
00203     sprintf (optname2, "branch_lp_clamp_%s",  br_ops [i].c_str ());
00204     sprintf (description, "Chooses branching point selection strategy for operator %s", 
00205              br_ops [i].c_str ());
00206 
00207     roptions -> AddStringOption7
00208       (optname,
00209        description,
00210        "common",
00211        "common",    "use strategy defined for generic operators",
00212        "lp-clamped", "LP point clamped in [k,1-k] of the bound intervals "
00213        "(k defined by lp_clamp_${this operator}$)",
00214        "lp-central", "LP point if within [k,1-k] of the bound intervals, middle point otherwise" 
00215        "(k defined by branch_lp_clamp_${this operator}$)",
00216        "balanced",  "minimizes max distance from curve to convexification",
00217        "min-area",  "minimizes total area of the two convexifications",
00218        "mid-point", "convex combination of current point and mid point",
00219        "no-branch", "do not branch, return null infeasibility; for testing purposes only",
00220        "");
00221 
00222     roptions -> AddBoundedNumberOption
00223       (optname2,
00224        "Defines safe interval percentage [0,0.5] for using LP point as a branching point",
00225        0.,false,
00226        0.5,false,
00227        0.2,
00228        "Default value is 0.2.");
00229   }
00230 
00231   roptions -> AddBoundedNumberOption
00232     ("branch_midpoint_alpha",
00233      "Defines convex combination of mid point and current LP point: "
00234      "b = alpha x_lp + (1-alpha) (lb+ub)/2.",
00235      0.,false,
00236      1.,false,
00237      default_alpha,
00238      "Default value is 0.25.");
00239 
00240   roptions -> AddBoundedNumberOption
00241     ("branch_lp_clamp",
00242      "Defines safe interval percentage for using LP point as a branching point",
00243      0.,false,
00244      1.,false,
00245      0.2,
00246      "Default value is 0.2.");
00247 
00248   roptions -> AddLowerBoundedIntegerOption
00249     ("cont_var_priority",
00250      "Priority of continuous variable branching",
00251      1, 2000,
00252      "When branching, this is compared to the priority of integer variables, whose priority is given by int_var_priority, and SOS, whose priority is 10. "
00253      "Higher values mean smaller priority."
00254     );
00255 
00256   roptions -> AddLowerBoundedIntegerOption
00257     ("int_var_priority",
00258      "Priority of integer variable branching",
00259      1, 1000,
00260      "When branching, this is compared to the priority of continuous variables, whose priority is given by cont_var_priority, and SOS, whose priority is 10. "
00261      "Higher values mean smaller priority."
00262     );
00263 
00264   roptions -> AddStringOption2
00265     ("red_cost_branching",
00266      "Apply Reduced Cost Branching (instead of the Violation Transfer) -- MUST have vt_obj enabled",
00267      "no",
00268      "no", "Use Violation Transfer with $\\sum |\\pi_i a_{ij}|$",
00269      "yes","Use Reduced cost branching with $|\\sum \\pi_i a_{ij}|$");
00270 
00271     roptions -> AddStringOption2 (
00272       "orbital_branching",
00273       "detect symmetries and apply orbital branching",
00274       "no",
00275       "yes", "",
00276       "no", "");
00277 }

Generated on Thu Sep 22 03:05:56 2011 by  doxygen 1.4.7