/home/coin/SVN-release/OS-2.2.0/Couenne/src/problem/CouenneSOS.cpp

Go to the documentation of this file.
00001 /* $Id: CouenneSOS.cpp 215 2009-07-08 15:43:38Z pbelotti $
00002  *
00003  * Name:    CouenneSOS.cpp
00004  * Author:  Pietro Belotti
00005  * Purpose: find SOS in problem 
00006  *
00007  * (C) Carnegie-Mellon University, 2008.
00008  * This file is licensed under the Common Public License (CPL)
00009  */
00010 
00011 #include <vector>
00012 
00013 #include "CouenneProblem.hpp"
00014 #include "exprGroup.hpp"
00015 
00016 #include "CbcModel.hpp"
00017 #include "CbcBranchActual.hpp"
00018 #include "CbcCutGenerator.hpp"
00019 #include "CbcCompareActual.hpp"
00020 //#include "CouenneSOSObject.hpp"
00021 
00023 int CouenneProblem::findSOS (OsiSolverInterface *solver,
00024                              OsiObject **objects) {
00025 
00026   // check auxiliaries defined as 
00027   // x_i binary. Disable it and add relative SOS to array "objects"
00028 
00029   int nSOS = 0;
00030 
00031   for (std::vector <exprVar *>::const_iterator v = variables_.begin ();
00032        v != variables_.end (); ++v) 
00033 
00034     if (((*v) -> Multiplicity () >    0) &&
00035         ((*v) -> Type         () == AUX) &&
00036         ((*v) -> Image () -> code () == COU_EXPRGROUP)) {
00037 
00038       expression *img = (*v) -> Image ();
00039 
00040       exprGroup *group = dynamic_cast <exprGroup *> (img -> isaCopy () ? 
00041                                                      img -> Copy () :
00042                                                      img);
00043       if (!group)
00044         continue;
00045 
00046       int wind = (*v) -> Index ();
00047       CouNumber cterm = group -> getc0 ();
00048       bool defVar = true;
00049 
00050       // now check if this is 
00051       //
00052       // 1) an auxiliary fixed to one  ==> it's a SOS if its image is x1+x2+...+xk
00053       // 2) an auxiliary fixed to zero ==> it's a SOS if its image is -x1-x2-...-xk+1
00054 
00055       if      (fabs (cterm - 1.) < COUENNE_EPS) defVar = false;
00056       else if (fabs (cterm)      > COUENNE_EPS) continue; // and defVar is true
00057 
00058       if (defVar &&
00059           ((fabs (Lb (wind) - 1.) > COUENNE_EPS) ||
00060            (fabs (Ub (wind) - 1.) > COUENNE_EPS)))
00061         continue;
00062 
00063       if (!defVar &&
00064           ((fabs (Lb (wind)) > COUENNE_EPS)))
00065         continue;
00066 
00067       int lsz = group -> lcoeff (). size ();
00068 
00069       if (((lsz <= 2) &&  defVar) ||
00070           ((lsz <= 1) && !defVar))
00071         continue;
00072 
00073       // there are two possibilities:
00074       //
00075       // 1) w is defined as w = 1 - \sum_{i=0}^n x_i  -- defvar = false
00076       //
00077       // 2) w is defined as \sum_{i=0}^n x_i and w \in [1,1] -- defvar = true
00078 
00079       bool
00080         intSOS = (*v) -> isInteger (),
00081         isSOS  = true,
00082         onlyOrigVars = true; // if SOS constraint only contains
00083                              // original variables, it has been
00084                              // spotted by Cbc already
00085 
00086       exprGroup::lincoeff &lcoe = group -> lcoeff ();
00087 
00088       for (exprGroup::lincoeff::iterator l = lcoe. begin (); 
00089            l != lcoe. end (); ++l) {
00090 
00091         if ((fabs (l -> second - (defVar ? 1. : -1.)) > COUENNE_EPS) || // wrong coefficient?
00092             (fabs (Lb (l -> first -> Index ()))       > COUENNE_EPS)) { // positive lower bound?
00093 
00094           isSOS = false;
00095           break;
00096         } else 
00097           if (!(l -> first -> isInteger ()))
00098             intSOS = false;
00099 
00100         if (l -> first -> Index () > nOrigVars_) // 
00101           onlyOrigVars = false;
00102       }
00103 
00104       if (!isSOS || !intSOS)// || onlyOrigVars) 
00105         continue;
00106 
00107       printf ("----- found SOS: ");
00108       (*v) -> print (); printf (" := ");
00109       (*v) -> Image () -> print (); printf ("\n");
00110 
00111       // it is a SOS -- if intSOS==true, it's also integer
00112 
00113       int
00114         indStart = defVar ? 0 : 1,
00115         nelem    = indStart + lcoe. size (), 
00116         *indices = new int [nelem];
00117 
00118       if (!defVar)
00119         indices [0] = (*v) -> Index ();
00120 
00121       for (int i=indStart, j=0; i<nelem; i++)
00122         indices [i] = lcoe [j++]. first -> Index ();
00123 
00124       // TODO: if use Cbc, add CbcSOSBranchingObject
00125 
00126       /*CouenneSOSObject *newsos = new CouenneSOSObject (solver, nelem, indices, NULL, 1,
00127         jnlst_, true, true);*/
00128 
00129       OsiSOS *newsos = new OsiSOS (solver, nelem, indices, NULL, 1);
00130 
00131       objects [nSOS] = newsos;
00132       // as in BonBabSetupBase.cpp:675
00133       newsos -> setPriority (10);
00134       newsos -> setIntegerValued (intSOS);
00135 
00136       nSOS++;
00137     }
00138 
00139   return nSOS;
00140 }

Generated on Thu Aug 5 03:02:57 2010 by  doxygen 1.4.7