1 /* $Id$
2 *
3 * Name: CouenneSOSObject.cpp
4 * Authors: Pietro Belotti, Lehigh University
5 * Purpose: Branching SOS object
6 *
7 * (C) Carnegie-Mellon University, 2008-09.
8 * This file is licensed under the Eclipse Public License (EPL)
9 */
10
11 #include "OsiRowCut.hpp"
12
13 //#include "CouenneSolverInterface.hpp"
14 #include "CouenneSOSObject.hpp"
15 #include "CouenneProblem.hpp"
16 #include "CouenneProblemElem.hpp"
17
18 #include "CoinHelperFunctions.hpp"
19 #include "CoinFinite.hpp"
20
21 using namespace Couenne;
22
23 // translate changed bound sparse array into a dense one
24 void sparse2dense (int ncols, t_chg_bounds *chg_bds, int *&changed, int &nchanged);
25
26
27 /** \brief Execute the actions required to branch, as specified by the
28 * current state of the branching object, and advance the
29 * object's state.
30 *
31 * Returns change in guessed objective on next branch
32 */
33
branch(OsiSolverInterface * solver)34 double CouenneSOSBranchingObject::branch (OsiSolverInterface * solver) {
35
36 // Apply SOS branching first
37 double retval = OsiSOSBranchingObject::branch (solver);
38
39 //CouenneSolverInterface *couenneSolver = dynamic_cast <CouenneSolverInterface *> (solver);
40 //CouenneProblem *p = couenneSolver -> CutGen () -> Problem ();
41
42 int
43 nvars = problem_ -> nVars (),
44 objind = problem_ -> Obj (0) -> Body () -> Index ();
45
46 bool infeasible = false;
47
48 problem_ -> domain () -> push (solver); // have to alloc+copy
49
50 int nMembers = dynamic_cast <const OsiSOS *> (originalObject ()) -> numberMembers ();
51 const int *Members = dynamic_cast <const OsiSOS *> (originalObject ()) -> members ();
52
53 //CouNumber &estimate = way ? upEstimate_ : downEstimate_;
54 CouNumber estimate = 0.;//way ? upEstimate_ : downEstimate_;
55
56 t_chg_bounds *chg_bds = new t_chg_bounds [nvars];
57
58 while (nMembers--) {
59 chg_bds [*Members] .setUpper (t_chg_bounds::CHANGED);
60 chg_bds [*Members++].setLower (t_chg_bounds::CHANGED);
61 }
62
63 if ( doFBBT_ && // this branching object should do FBBT, and
64 problem_ -> doFBBT ()) { // problem allowed to do FBBT
65
66 problem_ -> installCutOff ();
67
68 if (!problem_ -> btCore (chg_bds)) // done FBBT and this branch is infeasible
69 infeasible = true; // ==> report it
70 else {
71
72 const double
73 *lb = solver -> getColLower (),
74 *ub = solver -> getColUpper ();
75
76 //CouNumber newEst = problem_ -> Lb (objind) - lb [objind];
77 estimate = CoinMax (0., objind >= 0 ? problem_ -> Lb (objind) - lb [objind] : 0.);
78
79 //if (newEst > estimate)
80 //estimate = newEst;
81
82 for (int i=0; i<nvars; i++) {
83 if (problem_ -> Lb (i) > lb [i]) solver -> setColLower (i, problem_ -> Lb (i));
84 if (problem_ -> Ub (i) < ub [i]) solver -> setColUpper (i, problem_ -> Ub (i));
85 }
86 }
87 }
88
89 /*if (!infeasible && doConvCuts_ && simulate_) {
90 // generate convexification cuts before solving new node's LP
91
92 int nchanged, *changed = NULL;
93 OsiCuts cs;
94
95 // sparsify structure with info on changed bounds and get convexification cuts
96 sparse2dense (nvars, chg_bds, changed, nchanged);
97 couenneSolver -> CutGen () -> genRowCuts (*solver, cs, nchanged, changed, chg_bds);
98 free (changed);
99
100 solver -> applyCuts (cs);
101 }*/
102
103 delete [] chg_bds;
104
105 problem_ -> domain () -> pop ();
106
107 // next time do other branching
108 branchIndex_++;
109
110 // estimated change in objective function
111 return (infeasible ? COIN_DBL_MAX : CoinMax (retval, estimate));
112 }
113
114
115 /// create CouenneBranchingObject or CouenneThreeWayBranchObj based
116 /// on this object
createBranch(OsiSolverInterface * si,const OsiBranchingInformation * info,int way) const117 OsiBranchingObject *CouenneSOSObject::createBranch (OsiSolverInterface* si,
118 const OsiBranchingInformation* info, int way) const
119 {
120
121 // COPIED FROM OsiBranchingObject.cpp (see code for OsiSOSObject::createBranch)
122 int j;
123 const double * solution = info->solution_;
124 double tolerance = info->primalTolerance_;
125 const double * upper = info->upper_;
126 int firstNonFixed=-1;
127 int lastNonFixed=-1;
128 int firstNonZero=-1;
129 int lastNonZero = -1;
130 double weight = 0.0;
131 double sum =0.0;
132 for (j=0;j<numberMembers_;j++) {
133 int iColumn = members_[j];
134 if (upper[iColumn]) {
135 double value = CoinMax(0.0,solution[iColumn]);
136 sum += value;
137 if (firstNonFixed<0)
138 firstNonFixed=j;
139 lastNonFixed=j;
140 if (value>tolerance) {
141 weight += weights_[j]*value;
142 if (firstNonZero<0)
143 firstNonZero=j;
144 lastNonZero=j;
145 }
146 }
147 }
148 assert (lastNonZero-firstNonZero>=sosType_) ;
149 // find where to branch
150 assert (sum>0.0);
151 weight /= sum;
152 int iWhere;
153 double separator=0.0;
154 for (iWhere=firstNonZero;iWhere<lastNonZero;iWhere++)
155 if (weight<weights_[iWhere+1])
156 break;
157 if (sosType_==1) {
158 // SOS 1
159 separator = 0.5 *(weights_[iWhere]+weights_[iWhere+1]);
160 } else {
161 // SOS 2
162 if (iWhere==lastNonFixed-1)
163 iWhere = lastNonFixed-2;
164 separator = weights_[iWhere+1];
165 }
166 // create object
167
168 return new CouenneSOSBranchingObject (problem_, reference_,
169 si, this, way, separator, jnlst_, doFBBT_, doConvCuts_);
170 }
171