1 /* 2 * Copyright 2007-2008, Christof Lutteroth, lutteroth@cs.auckland.ac.nz 3 * Copyright 2007-2008, James Kim, jkim202@ec.auckland.ac.nz 4 * Copyright 2010, Clemens Zeidler <haiku@clemens-zeidler.de> 5 * Distributed under the terms of the MIT License. 6 */ 7 8 9 #include "Constraint.h" 10 11 #include <new> 12 #include <stdio.h> 13 14 #include "LinearSpec.h" 15 #include "Variable.h" 16 17 18 // Toggle debug output 19 //#define DEBUG_CONSTRAINT 20 21 #ifdef DEBUG_CONSTRAINT 22 # define STRACE(x) debug_printf x 23 #else 24 # define STRACE(x) ; 25 #endif 26 27 28 /** 29 * Gets the index of the constraint. 30 * 31 * @return the index of the constraint 32 */ 33 int32 34 Constraint::Index() const 35 { 36 int32 i = fLS->Constraints().IndexOf(this); 37 if (i == -1) 38 STRACE(("Constraint not part of fLS->Constraints().")); 39 40 return i; 41 } 42 43 44 /** 45 * Gets the left side of the constraint. 46 * 47 * @return pointer to a BList containing the summands on the left side of the constraint 48 */ 49 SummandList* 50 Constraint::LeftSide() 51 { 52 return fLeftSide; 53 } 54 55 56 /** 57 * Sets the summands on the left side of the constraint. 58 * The old summands are NOT deleted. 59 * 60 * @param summands a BList containing the Summand objects that make up the new left side 61 */ 62 void 63 Constraint::SetLeftSide(SummandList* summands) 64 { 65 if (!fIsValid) 66 return; 67 68 // check left side 69 for (int32 i = 0; i < summands->CountItems(); i++) { 70 Summand* summand = summands->ItemAt(i); 71 for (int32 a = i + 1; a < summands->CountItems(); a++) { 72 Summand* nextSummand = summands->ItemAt(a); 73 if (summand->Var() == nextSummand->Var()) { 74 summand->SetCoeff(summand->Coeff() + nextSummand->Coeff()); 75 summands->RemoveItem(nextSummand); 76 delete nextSummand; 77 a--; 78 } 79 } 80 } 81 82 fLeftSide = summands; 83 fLS->UpdateLeftSide(this); 84 } 85 86 87 void 88 Constraint::SetLeftSide(double coeff1, Variable* var1) 89 { 90 if (!fIsValid) 91 return; 92 93 for (int i=0; i<fLeftSide->CountItems(); i++) 94 delete fLeftSide->ItemAt(i); 95 fLeftSide->MakeEmpty(); 96 fLeftSide->AddItem(new(std::nothrow) Summand(coeff1, var1)); 97 SetLeftSide(fLeftSide); 98 } 99 100 101 void 102 Constraint::SetLeftSide(double coeff1, Variable* var1, 103 double coeff2, Variable* var2) 104 { 105 if (!fIsValid) 106 return; 107 108 for (int i=0; i<fLeftSide->CountItems(); i++) 109 delete fLeftSide->ItemAt(i); 110 fLeftSide->MakeEmpty(); 111 fLeftSide->AddItem(new(std::nothrow) Summand(coeff1, var1)); 112 fLeftSide->AddItem(new(std::nothrow) Summand(coeff2, var2)); 113 SetLeftSide(fLeftSide); 114 } 115 116 117 void 118 Constraint::SetLeftSide(double coeff1, Variable* var1, 119 double coeff2, Variable* var2, 120 double coeff3, Variable* var3) 121 { 122 if (!fIsValid) 123 return; 124 125 for (int i=0; i<fLeftSide->CountItems(); i++) 126 delete fLeftSide->ItemAt(i); 127 fLeftSide->MakeEmpty(); 128 fLeftSide->AddItem(new(std::nothrow) Summand(coeff1, var1)); 129 fLeftSide->AddItem(new(std::nothrow) Summand(coeff2, var2)); 130 fLeftSide->AddItem(new(std::nothrow) Summand(coeff3, var3)); 131 SetLeftSide(fLeftSide); 132 } 133 134 135 void 136 Constraint::SetLeftSide(double coeff1, Variable* var1, 137 double coeff2, Variable* var2, 138 double coeff3, Variable* var3, 139 double coeff4, Variable* var4) 140 { 141 if (!fIsValid) 142 return; 143 144 for (int i=0; i<fLeftSide->CountItems(); i++) 145 delete fLeftSide->ItemAt(i); 146 fLeftSide->MakeEmpty(); 147 fLeftSide->AddItem(new(std::nothrow) Summand(coeff1, var1)); 148 fLeftSide->AddItem(new(std::nothrow) Summand(coeff2, var2)); 149 fLeftSide->AddItem(new(std::nothrow) Summand(coeff3, var3)); 150 fLeftSide->AddItem(new(std::nothrow) Summand(coeff4, var4)); 151 SetLeftSide(fLeftSide); 152 } 153 154 155 /** 156 * Gets the operator used for this constraint. 157 * 158 * @return the operator used for this constraint 159 */ 160 OperatorType 161 Constraint::Op() 162 { 163 return fOp; 164 } 165 166 167 /** 168 * Sets the operator used for this constraint. 169 * 170 * @param value operator 171 */ 172 void 173 Constraint::SetOp(OperatorType value) 174 { 175 if (!fIsValid) 176 return; 177 178 fOp = value; 179 fLS->UpdateOperator(this); 180 } 181 182 183 /** 184 * Gets the constant value that is on the right side of the operator. 185 * 186 * @return the constant value that is on the right side of the operator 187 */ 188 double 189 Constraint::RightSide() const 190 { 191 return fRightSide; 192 } 193 194 195 /** 196 * Sets the constant value that is on the right side of the operator. 197 * 198 * @param value constant value that is on the right side of the operator 199 */ 200 void 201 Constraint::SetRightSide(double value) 202 { 203 if (!fIsValid) 204 return; 205 206 if (fRightSide == value) 207 return; 208 209 fRightSide = value; 210 211 fLS->UpdateRightSide(this); 212 } 213 214 215 /** 216 * Gets the penalty coefficient for negative deviations. 217 * 218 * @return the penalty coefficient 219 */ 220 double 221 Constraint::PenaltyNeg() const 222 { 223 return fPenaltyNeg; 224 } 225 226 227 /** 228 * The penalty coefficient for negative deviations from the soft constraint's exact solution, 229 * i.e. if the left side is too large. 230 * 231 * @param value coefficient of negative penalty <code>double</code> 232 */ 233 void 234 Constraint::SetPenaltyNeg(double value) 235 { 236 fPenaltyNeg = value; 237 238 fLS->UpdateLeftSide(this); 239 } 240 241 242 /** 243 * Gets the penalty coefficient for positive deviations. 244 * 245 * @return the penalty coefficient 246 */ 247 double 248 Constraint::PenaltyPos() const 249 { 250 return fPenaltyPos; 251 } 252 253 254 /** 255 * The penalty coefficient for negative deviations from the soft constraint's 256 * exact solution, i.e. if the left side is too small. 257 * @param value coefficient of positive penalty <code>double</code> 258 */ 259 void 260 Constraint::SetPenaltyPos(double value) 261 { 262 fPenaltyPos = value; 263 264 fLS->UpdateLeftSide(this); 265 } 266 267 268 const char* 269 Constraint::Label() 270 { 271 return fLabel.String(); 272 } 273 274 275 void 276 Constraint::SetLabel(const char* label) 277 { 278 fLabel = label; 279 } 280 281 282 /** 283 * Gets the slack variable for the negative variations. 284 * 285 * @return the slack variable for the negative variations 286 */ 287 Variable* 288 Constraint::DNeg() const 289 { 290 if (fDNegObjSummand == NULL) 291 return NULL; 292 return fDNegObjSummand->Var(); 293 } 294 295 296 /** 297 * Gets the slack variable for the positive variations. 298 * 299 * @return the slack variable for the positive variations 300 */ 301 Variable* 302 Constraint::DPos() const 303 { 304 if (fDPosObjSummand == NULL) 305 return NULL; 306 return fDPosObjSummand->Var(); 307 } 308 309 310 bool 311 Constraint::IsSoft() const 312 { 313 if (fPenaltyNeg > 0. && fOp != kLE) 314 return true; 315 316 if (fPenaltyPos > 0. && fOp != kGE) 317 return true; 318 return false; 319 } 320 321 322 bool 323 Constraint::IsValid() 324 { 325 return fIsValid; 326 } 327 328 329 void 330 Constraint::Invalidate() 331 { 332 STRACE(("Constraint::Invalidate() on %d\n", this)); 333 334 if (!fIsValid) 335 return; 336 337 fIsValid = false; 338 fLS->RemoveConstraint(this, false); 339 } 340 341 342 BString 343 Constraint::ToString() const 344 { 345 BString string; 346 string << "Constraint "; 347 string << fLabel; 348 string << "(" << (int32)this << "): "; 349 350 if (fIsValid) { 351 for (int i = 0; i < fLeftSide->CountItems(); i++) { 352 Summand* s = static_cast<Summand*>(fLeftSide->ItemAt(i)); 353 if (i != 0 && s->Coeff() >= 0) 354 string << " + "; 355 string << (float)s->Coeff() << "*"; 356 string << "x"; 357 string << s->Var()->Index(); 358 string << " "; 359 } 360 string << ((fOp == kEQ) ? "== " 361 : (fOp == kGE) ? ">= " 362 : (fOp == kLE) ? "<= " 363 : "?? "); 364 string << (float)fRightSide; 365 string << " PenaltyPos=" << (float)PenaltyPos(); 366 string << " PenaltyNeg=" << (float)PenaltyNeg(); 367 } else 368 string << "invalid"; 369 return string; 370 } 371 372 373 void 374 Constraint::PrintToStream() 375 { 376 BString string = ToString(); 377 printf("%s\n", string.String()); 378 } 379 380 381 /** 382 * Constructor. 383 */ 384 Constraint::Constraint(LinearSpec* ls, SummandList* summands, OperatorType op, 385 double rightSide, double penaltyNeg, double penaltyPos) 386 : 387 fLS(ls), 388 fOp(op), 389 fRightSide(rightSide), 390 fPenaltyNeg(penaltyNeg), 391 fPenaltyPos(penaltyPos), 392 fDNegObjSummand(NULL), 393 fDPosObjSummand(NULL), 394 fIsValid(true) 395 { 396 SetLeftSide(summands); 397 } 398 399 400 /** 401 * Destructor. 402 * Removes the constraint from its specification and deletes all the summands. 403 */ 404 Constraint::~Constraint() 405 { 406 Invalidate(); 407 408 for (int32 i = 0; i < fLeftSide->CountItems(); i++) 409 delete (Summand*)fLeftSide->ItemAt(i); 410 delete fLeftSide; 411 fLeftSide = NULL; 412 } 413 414