00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012 #include <map>
00013 #include <set>
00014
00015 #include "CouenneTypes.hpp"
00016 #include "CouenneProblem.hpp"
00017 #include "exprQuad.hpp"
00018 #include "exprMul.hpp"
00019 #include "exprPow.hpp"
00020 #include "lqelems.hpp"
00021
00022 #define MIN_DENSITY 0.5
00023
00024
00025
00029 void CouenneProblem::analyzeSparsity (CouNumber c0,
00030 LinMap &lmap,
00031 QuadMap &qmap) {
00032
00033 if (qmap.Map().size () == 0) return;
00034
00035
00036
00037
00038
00039 std::set <int> occur;
00040 unsigned int nsquares = 0;
00041
00042 for (std::map <std::pair <int,int>, CouNumber>::iterator i = qmap.Map().begin ();
00043 i != qmap.Map().end (); ++i) {
00044
00045 int
00046 first = i -> first.first,
00047 second = i -> first.second;
00048
00049 if (occur.find (first) == occur.end ())
00050 occur.insert (first);
00051
00052 if (first != second) {
00053 if (occur.find (second) == occur.end ())
00054 occur.insert (second);
00055 } else nsquares++;
00056 }
00057
00058 #ifdef DEBUG
00059 printf ("qmap has %d element, occur has %d, md*s*(s+1)/2 = %g\n",
00060 qmap.Map().size (),
00061 occur.size (),
00062 MIN_DENSITY * occur.size () * (occur.size () + 1) / 2);
00063 #endif
00064
00065 int nterms = occur.size ();
00066
00067 if (useQuadratic_ &&
00068 ((qmap.Map().size () >= MIN_DENSITY * nterms * (nterms+1) / 2) &&
00069 (nterms >= 2)
00070
00071 || (nsquares >= occur.size ()))
00072 )
00073 return;
00074
00075
00076
00077
00078 for (std::map <std::pair <int,int>, CouNumber>::iterator i = qmap.Map().begin ();
00079 i != qmap.Map().end (); ++i) {
00080
00081 int indI = i -> first.first,
00082 indJ = i -> first.second;
00083
00084 exprAux *aux = (indI != indJ) ?
00085 addAuxiliary
00086 (new exprMul (new exprClone (Var (indI)),
00087 new exprClone (Var (indJ)))) :
00088 addAuxiliary
00089 (new exprPow (new exprClone (Var (indI)),
00090 new exprConst (2.)));
00091
00092
00093
00094 lmap.insert (aux -> Index (), i -> second);
00095 }
00096
00097 if (qmap.Map().size () == 1) {
00098
00099
00100
00101 }
00102
00103 qmap.Map().erase (qmap.Map().begin (), qmap.Map().end ());
00104
00105
00106
00107
00108
00109
00110 }