source: stable/0.2/Couenne/src/problem/CouenneSOS.cpp @ 159

Last change on this file since 159 was 159, checked in by pbelotti, 11 years ago

created new stable branch 0.2 from trunk (rev. 157)

File size: 3.7 KB
Line 
1/* $Id: CouenneSOS.cpp 154 2009-06-16 18:52:53Z pbelotti $ */
2/*
3 * Name:    CouenneSOS.cpp
4 * Author:  Pietro Belotti
5 * Purpose: find SOS in problem
6 *
7 * (C) Carnegie-Mellon University, 2008.
8 * This file is licensed under the Common Public License (CPL)
9 */
10
11#include <vector>
12
13#include "CouenneProblem.hpp"
14#include "exprGroup.hpp"
15
16#include "CbcModel.hpp"
17#include "CbcBranchActual.hpp"
18#include "CbcCutGenerator.hpp"
19#include "CbcCompareActual.hpp"
20#include "CouenneSOSObject.hpp"
21
22/// find SOS objects
23int CouenneProblem::findSOS (OsiSolverInterface *solver,
24                             OsiObject **objects) {
25
26  // check auxiliaries defined as
27  // x_i binary. Disable it and add relative SOS to array "objects"
28
29  int nSOS = 0;
30
31  for (std::vector <exprVar *>::const_iterator v = variables_.begin ();
32       v != variables_.end (); ++v) 
33
34    if (((*v) -> Multiplicity () >    0) &&
35        ((*v) -> Type         () == AUX) &&
36        ((*v) -> Image () -> code () == COU_EXPRGROUP)) {
37
38      expression *img = (*v) -> Image ();
39
40      exprGroup *group = dynamic_cast <exprGroup *> (img -> isaCopy () ? 
41                                                     img -> Copy () :
42                                                     img);
43      if (!group)
44        continue;
45
46      int wind = (*v) -> Index ();
47      CouNumber cterm = group -> getc0 ();
48      bool defVar = true;
49
50      // now check if this is
51      //
52      // 1) an auxiliary fixed to one  ==> it's a SOS if its image is x1+x2+...+xk
53      // 2) an auxiliary fixed to zero ==> it's a SOS if its image is -x1-x2-...-xk+1
54
55      if      (fabs (cterm - 1.) < COUENNE_EPS) defVar = false;
56      else if (fabs (cterm)      > COUENNE_EPS) continue; // and defVar is true
57
58      if (defVar &&
59          ((fabs (Lb (wind) - 1.) > COUENNE_EPS) ||
60           (fabs (Ub (wind) - 1.) > COUENNE_EPS)))
61        continue;
62
63      if (!defVar &&
64          ((fabs (Lb (wind)) > COUENNE_EPS)))
65        continue;
66
67      int lsz = group -> lcoeff (). size ();
68
69      if (((lsz <= 2) &&  defVar) ||
70          ((lsz <= 1) && !defVar))
71        continue;
72
73      // there are two possibilities:
74      //
75      // 1) w is defined as w = 1 - \sum_{i=0}^n x_i  -- defvar = false
76      //
77      // 2) w is defined as \sum_{i=0}^n x_i and w \in [1,1] -- defvar = true
78
79      bool
80        intSOS = (*v) -> isInteger (),
81        isSOS  = true,
82        onlyOrigVars = true; // if SOS constraint only contains
83                             // original variables, it has been
84                             // spotted by Cbc already
85
86      exprGroup::lincoeff &lcoe = group -> lcoeff ();
87
88      for (exprGroup::lincoeff::iterator l = lcoe. begin (); 
89           l != lcoe. end (); ++l) {
90
91        if ((fabs (l -> second - (defVar ? 1. : -1.)) > COUENNE_EPS) || // wrong coefficient?
92            (fabs (Lb (l -> first -> Index ()))       > COUENNE_EPS)) { // positive lower bound?
93
94          isSOS = false;
95          break;
96        } else 
97          if (!(l -> first -> isInteger ()))
98            intSOS = false;
99
100        if (l -> first -> Index () > nOrigVars_) //
101          onlyOrigVars = false;
102      }
103
104      if (!isSOS || !intSOS)// || onlyOrigVars)
105        continue;
106
107      printf ("----- found SOS: ");
108      (*v) -> print (); printf (" := ");
109      (*v) -> Image () -> print (); printf ("\n");
110
111      // it is a SOS -- if intSOS==true, it's also integer
112
113      int
114        indStart = defVar ? 0 : 1,
115        nelem    = indStart + lcoe. size (), 
116        *indices = new int [nelem];
117
118      if (!defVar)
119        indices [0] = (*v) -> Index ();
120
121      for (int i=indStart, j=0; i<nelem; i++)
122        indices [i] = lcoe [j++]. first -> Index ();
123
124      // TODO: if use Cbc, add CbcSOSBranchingObject
125
126      /*CouenneSOSObject *newsos = new CouenneSOSObject (solver, nelem, indices, NULL, 1,
127        jnlst_, true, true);*/
128
129      OsiSOS *newsos = new OsiSOS (solver, nelem, indices, NULL, 1);
130
131      objects [nSOS] = newsos;
132      // as in BonBabSetupBase.cpp:675
133      newsos -> setPriority (10);
134      newsos -> setIntegerValued (intSOS);
135
136      nSOS++;
137    }
138
139  return nSOS;
140}
Note: See TracBrowser for help on using the repository browser.