1 /* $Id$
2 *
3 * Name: CouenneProblem.cpp
4 * Author: Pietro Belotti
5 * Purpose: methods of the class CouenneProblem
6 *
7 * (C) Carnegie-Mellon University, 2006-10.
8 * This file is licensed under the Eclipse Public License (EPL)
9 */
10
11 #include <vector>
12
13 #include "CoinHelperFunctions.hpp"
14 #include "CoinTime.hpp"
15
16 #include "CbcBranchActual.hpp"
17
18 #include "CouenneTypes.hpp"
19
20 #include "CouenneExpression.hpp"
21 #include "CouenneExprConst.hpp"
22 #include "CouenneExprQuad.hpp"
23 #include "CouenneExprClone.hpp"
24 #include "CouenneExprIVar.hpp"
25 #include "CouenneExprAux.hpp"
26 #include "CouenneExprOpp.hpp"
27
28 #include "CouenneProblem.hpp"
29 #include "CouenneGlobalCutOff.hpp"
30 #include "CouenneProblemElem.hpp"
31 #include "CouenneDepGraph.hpp"
32 #include "CouenneLQelems.hpp"
33
34 #include "CouenneJournalist.hpp"
35 #include "CouenneObject.hpp"
36
37 using namespace Couenne;
38
39 /// methods to add objective function.
40
addObjective(expression * newobj,const std::string & sense)41 void CouenneProblem::addObjective (expression *newobj, const std::string &sense) {
42 objectives_ . push_back
43 (new CouenneObjective ((sense == "min") ?
44 newobj : new exprOpp (new exprClone (newobj))));
45 }
46
47
48 /// methods to add nonlinear constraints:
49
50 /// equality constraint
addEQConstraint(expression * body,expression * rhs)51 void CouenneProblem::addEQConstraint (expression *body, expression *rhs) {
52
53 if (!rhs) rhs = new exprConst (0.);
54 constraints_ . push_back (new CouenneConstraint (body, rhs, new exprClone (rhs)));
55 }
56
57 /// "greater than" constraint
addGEConstraint(expression * body,expression * rhs)58 void CouenneProblem::addGEConstraint (expression *body, expression *rhs) {
59 if (!rhs) rhs = new exprConst (0.);
60 constraints_ . push_back (new CouenneConstraint
61 (body, rhs, new exprConst (COUENNE_INFINITY)));
62 }
63
64 /// "smaller than" constraint
addLEConstraint(expression * body,expression * rhs)65 void CouenneProblem::addLEConstraint (expression *body, expression *rhs) {
66 if (!rhs) rhs = new exprConst (0.);
67 constraints_ . push_back (new CouenneConstraint
68 (body, new exprConst (-COUENNE_INFINITY), rhs));
69 }
70
71 /// Add (non linear) objective function
setObjective(int indObj,expression * newObj,const std::string & sense)72 void CouenneProblem::setObjective (int indObj, expression * newObj, const std::string &sense) {
73 objectives_ [indObj] = (new CouenneObjective ((sense == "min") ?
74 newObj : new exprOpp (new exprClone (newObj))));
75 }
76
77
78 /// range constraint
addRNGConstraint(expression * body,expression * lb,expression * ub)79 void CouenneProblem::addRNGConstraint (expression *body, expression *lb, expression *ub) {
80 if (!lb) lb = new exprConst (0.);
81 if (!ub) ub = new exprConst (0.);
82 constraints_ . push_back (new CouenneConstraint (body, lb, ub));
83 }
84
85
86
87 /// add variable to the problem -- check whether it is integer (isDiscrete)
88
addVariable(bool isDiscrete,Domain * d)89 expression *CouenneProblem::addVariable (bool isDiscrete, Domain *d) {
90
91 exprVar *var = (isDiscrete) ?
92 (new exprIVar (variables_ . size (), d)) :
93 (new exprVar (variables_ . size (), d));
94
95 variables_ . push_back (var);
96
97 if (isDiscrete)
98 nIntVars_++;
99
100 nOrigVars_++;
101
102 return var;
103 }
104
105
106 /// add auxiliary variable and associate it with pointer to expression
107 /// given as argument
addAuxiliary(expression * symbolic)108 exprAux *CouenneProblem::addAuxiliary (expression *symbolic) {
109
110 // check if image is already in the expression database auxSet_
111 std::set <exprAux *, compExpr>::iterator i;
112
113 int var_ind = variables_ . size ();
114 domain_. current () -> resize (var_ind + 1);
115
116 symbolic -> getBounds (domain_. lb (var_ind),
117 domain_. ub (var_ind));
118
119 // create new aux associated with that expression
120 exprAux *w = new exprAux (symbolic,
121 var_ind,
122 1 + symbolic -> rank (),
123 exprAux::Unset,
124 &domain_);
125 //symbolic -> isInteger () ? exprAux::Integer : exprAux::Continuous);
126
127 // w -> linkDomain (&domain_);
128
129 // seek expression in the set
130 if ((i = auxSet_ -> find (w)) == auxSet_ -> end ()) {
131
132 // no such expression found in the set, create entry therein
133 variables_ . push_back (w);
134 auxSet_ -> insert (w); // insert into repetition checking structure
135 graph_ -> insert (w); // insert into acyclic structure
136
137 } else { // otherwise, just return the entry's pointer
138
139 w -> Image (NULL); // otherwise "delete w" will also delete user given expression "symbolic"
140 delete w;
141 w = *i;
142 (*i) -> increaseMult ();
143 }
144
145 return w;
146 }
147
148
149 /// translates pair (indices, coefficients) into vector with pointers to variables
indcoe2vector(int * indexL,CouNumber * coeff,std::vector<std::pair<exprVar *,CouNumber>> & lcoeff)150 void CouenneProblem::indcoe2vector (int *indexL,
151 CouNumber *coeff,
152 std::vector <std::pair <exprVar *, CouNumber> > &lcoeff) {
153 // TODO: sort
154
155 for (int i=0; indexL [i] >= 0; i++)
156 lcoeff.push_back (std::pair <exprVar *, CouNumber> (Var (indexL [i]), coeff [i]));
157 }
158
159
160 /// translates triplet (indicesI, indicesJ, coefficients) into vector with pointers to variables
indcoe2vector(int * indexI,int * indexJ,CouNumber * coeff,std::vector<quadElem> & qcoeff)161 void CouenneProblem::indcoe2vector (int *indexI,
162 int *indexJ,
163 CouNumber *coeff,
164 std::vector <quadElem> &qcoeff) {
165 // TODO: sort
166
167 for (int i=0; indexI [i] >= 0; i++)
168 qcoeff.push_back (quadElem (Var (indexI [i]), Var (indexJ [i]), coeff [i]));
169 }
170
171
172 /// fill in the integerRank_ array
fillIntegerRank() const173 void CouenneProblem::fillIntegerRank () const {
174
175 if (integerRank_)
176 return;
177
178 int nvars = nVars ();
179
180 integerRank_ = new int [nvars];
181
182 CoinZeroN (integerRank_, nvars);
183
184 // 0: fractional
185 // 1: integer
186 // k: integer, depending on at least one integer with associated value k-1, or
187 // k: fractional, depending on at least one integer with associated value k
188
189 for (int ii = 0; ii < nvars; ii++) {
190
191 int index = numbering_ [ii];
192
193 if (Var (index) -> Multiplicity () <= 0) {
194 integerRank_ [index] = 0;
195 continue;
196 }
197
198 bool isInt = Var (index) -> isDefinedInteger ();
199
200 // sets all originals to either 0 (fractional) or 1 (integer)
201 integerRank_ [index] = (isInt) ? 1 : 0;
202
203 if (Var (index) -> Type () == AUX) {
204
205 std::set <int> deplist;
206
207 if (Var (index) -> Image () -> DepList (deplist, STOP_AT_AUX) != 0) // depends on something
208 for (std::set <int>::iterator i = deplist.begin (); i != deplist.end (); ++i) {
209
210 int token = integerRank_ [*i];
211 if (isInt) token++;
212
213 if (token > integerRank_ [index]) // there's a free integer below us
214 integerRank_ [index] = token;
215 }
216 }
217 }
218
219 jnlst_->Printf (Ipopt::J_VECTOR, J_PROBLEM, "Free (original) integers\n");
220 for (int i=0; i<nOrigVars_; i++)
221 jnlst_->Printf (Ipopt::J_VECTOR, J_PROBLEM, "%d: %d\n", i, integerRank_ [i]);
222
223 // fill in numberInRank_
224 for (int i=0; i<nOrigVars_ - ndefined_; i++)
225 if ((variables_ [i] -> isDefinedInteger ()) &&
226 (variables_ [i] -> Multiplicity () > 0)) {
227
228 int rank = integerRank_ [i];
229
230 if (numberInRank_.size () <= (unsigned int) rank)
231 for (int j=numberInRank_.size (); j <= rank; j++)
232 numberInRank_ .push_back (0);
233
234 numberInRank_ [rank] ++;
235 }
236
237 jnlst_->Printf (Ipopt::J_VECTOR, J_PROBLEM, "numInteger [neglect non-originals]\n");
238 for (unsigned int i=0; i<numberInRank_.size(); i++)
239 jnlst_->Printf (Ipopt::J_VECTOR, J_PROBLEM, "%d: %d\n", i, numberInRank_ [i]);
240 }
241
242 // /// rescans problem after adding new auxiliaries
243 // void CouenneProblem::resizeAuxs (int nOld, int nNew) {
244
245 // #define resizeOld(typeD,oldV,oldN,newN) { \
246 // if (oldV) { \
247 // typeD *newV = new typeD [newN]; \
248 // CoinCopyN (oldV, oldN, newV); \
249 // delete [] oldV; \
250 // oldV = newV; \
251 // } \
252 // }
253
254 // resizeOld (int, numbering_, nOld, nNew);
255 // resizeOld (bool, commuted_, nOld, nNew);
256 // resizeOld (int, integerRank_, nOld, nNew);
257 // //resizeOld (double, optimum_, nOld, nNew);
258
259 // optimum_ = (double *) realloc (optimum_, nNew * sizeof (double));
260
261 // if (numbering_) for (int i=nOld; i<nNew; ++i) numbering_ [i] = i;
262 // if (commuted_) for (int i=nOld; i<nNew; ++i) commuted_ [i] = false;
263 // if (integerRank_) for (int i=nOld; i<nNew; ++i) integerRank_ [i] = nNew;
264 // if (optimum_) for (int i=nOld; i<nNew; ++i) optimum_ [i] = 0.;
265
266 // domain_ . current () -> resize (nNew);
267
268 // // post-rescan: update
269 // //
270 // // numbering_
271 // // domain_
272 // // commuted_
273 // // optimum_
274 // // integerRank_
275 // //
276 // // since there are new variables
277 // }
278
279 /// Get cutoff
getCutOff() const280 CouNumber CouenneProblem::getCutOff () const
281 {return pcutoff_ -> getCutOff ();}
282
283 /// Get cutoff solution
getCutOffSol() const284 CouNumber *CouenneProblem::getCutOffSol () const
285 {return pcutoff_ -> getCutOffSol ();}
286
287 /// Provide Journalist
Jnlst() const288 ConstJnlstPtr CouenneProblem::Jnlst () const
289 {return ConstPtr (jnlst_);}
290
291 // set lastPrioSort_
setLastPrioSort(int givenLastPS)292 void CouenneProblem::setLastPrioSort(int givenLastPS) {
293 lastPrioSort_ = givenLastPS;
294 }
295