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 return -1; 40 } 41 return i + 1; 42 } 43 44 45 /** 46 * Gets the left side of the constraint. 47 * 48 * @return pointer to a BList containing the summands on the left side of the constraint 49 */ 50 SummandList* 51 Constraint::LeftSide() 52 { 53 return fLeftSide; 54 } 55 56 57 /** 58 * Sets the summands on the left side of the constraint. 59 * The old summands are NOT deleted. 60 * 61 * @param summands a BList containing the Summand objects that make up the new left side 62 */ 63 void 64 Constraint::SetLeftSide(SummandList* summands) 65 { 66 if (!fIsValid) 67 return; 68 69 fLeftSide = summands; 70 fLS->UpdateLeftSide(this); 71 } 72 73 74 void 75 Constraint::SetLeftSide(double coeff1, Variable* var1) 76 { 77 if (!fIsValid) 78 return; 79 80 for (int i=0; i<fLeftSide->CountItems(); i++) 81 delete fLeftSide->ItemAt(i); 82 fLeftSide->MakeEmpty(); 83 fLeftSide->AddItem(new(std::nothrow) Summand(coeff1, var1)); 84 fLS->UpdateLeftSide(this); 85 } 86 87 88 void 89 Constraint::SetLeftSide(double coeff1, Variable* var1, 90 double coeff2, Variable* var2) 91 { 92 if (!fIsValid) 93 return; 94 95 for (int i=0; i<fLeftSide->CountItems(); i++) 96 delete fLeftSide->ItemAt(i); 97 fLeftSide->MakeEmpty(); 98 fLeftSide->AddItem(new(std::nothrow) Summand(coeff1, var1)); 99 fLeftSide->AddItem(new(std::nothrow) Summand(coeff2, var2)); 100 fLS->UpdateLeftSide(this); 101 } 102 103 104 void 105 Constraint::SetLeftSide(double coeff1, Variable* var1, 106 double coeff2, Variable* var2, 107 double coeff3, Variable* var3) 108 { 109 if (!fIsValid) 110 return; 111 112 for (int i=0; i<fLeftSide->CountItems(); i++) 113 delete fLeftSide->ItemAt(i); 114 fLeftSide->MakeEmpty(); 115 fLeftSide->AddItem(new(std::nothrow) Summand(coeff1, var1)); 116 fLeftSide->AddItem(new(std::nothrow) Summand(coeff2, var2)); 117 fLeftSide->AddItem(new(std::nothrow) Summand(coeff3, var3)); 118 fLS->UpdateLeftSide(this); 119 } 120 121 122 void 123 Constraint::SetLeftSide(double coeff1, Variable* var1, 124 double coeff2, Variable* var2, 125 double coeff3, Variable* var3, 126 double coeff4, Variable* var4) 127 { 128 if (!fIsValid) 129 return; 130 131 for (int i=0; i<fLeftSide->CountItems(); i++) 132 delete fLeftSide->ItemAt(i); 133 fLeftSide->MakeEmpty(); 134 fLeftSide->AddItem(new(std::nothrow) Summand(coeff1, var1)); 135 fLeftSide->AddItem(new(std::nothrow) Summand(coeff2, var2)); 136 fLeftSide->AddItem(new(std::nothrow) Summand(coeff3, var3)); 137 fLeftSide->AddItem(new(std::nothrow) Summand(coeff4, var4)); 138 fLS->UpdateLeftSide(this); 139 } 140 141 142 /** 143 * Gets the operator used for this constraint. 144 * 145 * @return the operator used for this constraint 146 */ 147 OperatorType 148 Constraint::Op() 149 { 150 return fOp; 151 } 152 153 154 /** 155 * Sets the operator used for this constraint. 156 * 157 * @param value operator 158 */ 159 void 160 Constraint::SetOp(OperatorType value) 161 { 162 if (!fIsValid) 163 return; 164 165 fOp = value; 166 fLS->UpdateOperator(this); 167 } 168 169 170 /** 171 * Gets the constant value that is on the right side of the operator. 172 * 173 * @return the constant value that is on the right side of the operator 174 */ 175 double 176 Constraint::RightSide() const 177 { 178 return fRightSide; 179 } 180 181 182 /** 183 * Sets the constant value that is on the right side of the operator. 184 * 185 * @param value constant value that is on the right side of the operator 186 */ 187 void 188 Constraint::SetRightSide(double value) 189 { 190 if (!fIsValid) 191 return; 192 193 if (fRightSide == value) 194 return; 195 196 fRightSide = value; 197 198 fLS->UpdateRightSide(this); 199 } 200 201 202 /** 203 * Gets the penalty coefficient for negative deviations. 204 * 205 * @return the penalty coefficient 206 */ 207 double 208 Constraint::PenaltyNeg() const 209 { 210 return fPenaltyNeg; 211 } 212 213 214 /** 215 * The penalty coefficient for negative deviations from the soft constraint's exact solution, 216 * i.e. if the left side is too large. 217 * 218 * @param value coefficient of negative penalty <code>double</code> 219 */ 220 void 221 Constraint::SetPenaltyNeg(double value) 222 { 223 fPenaltyNeg = value; 224 225 if (!fIsValid) 226 return; 227 228 if (fDNegObjSummand == NULL) { 229 fDNegObjSummand = new(std::nothrow) Summand(value, fLS->AddVariable()); 230 fLS->ObjectiveFunction()->AddItem(fDNegObjSummand); 231 fLS->UpdateLeftSide(this); 232 fLS->UpdateObjectiveFunction(); 233 return; 234 } 235 236 if (value == fDNegObjSummand->Coeff()) 237 return; 238 239 fDNegObjSummand->SetCoeff(value); 240 fLS->UpdateObjectiveFunction(); 241 } 242 243 244 /** 245 * Gets the penalty coefficient for positive deviations. 246 * 247 * @return the penalty coefficient 248 */ 249 double 250 Constraint::PenaltyPos() const 251 { 252 return fPenaltyPos; 253 } 254 255 256 /** 257 * The penalty coefficient for negative deviations from the soft constraint's 258 * exact solution, i.e. if the left side is too small. 259 * @param value coefficient of positive penalty <code>double</code> 260 */ 261 void 262 Constraint::SetPenaltyPos(double value) 263 { 264 fPenaltyPos = value; 265 266 if (!fIsValid) 267 return; 268 269 if (fDPosObjSummand == NULL) { 270 fDPosObjSummand = new(std::nothrow) Summand(value, fLS->AddVariable()); 271 fLS->ObjectiveFunction()->AddItem(fDPosObjSummand); 272 fLS->UpdateLeftSide(this); 273 fLS->UpdateObjectiveFunction(); 274 return; 275 } 276 277 if (value == fDPosObjSummand->Coeff()) 278 return; 279 280 fDPosObjSummand->SetCoeff(value); 281 fLS->UpdateObjectiveFunction(); 282 } 283 284 285 const char* 286 Constraint::Label() 287 { 288 return fLabel.String(); 289 } 290 291 292 void 293 Constraint::SetLabel(const char* label) 294 { 295 fLabel = label; 296 } 297 298 299 void 300 Constraint::WriteXML(BFile* file) 301 { 302 if (!file->IsWritable()) 303 return; 304 305 char buffer[200]; 306 307 file->Write(buffer, sprintf(buffer, "\t<constraint>\n")); 308 file->Write(buffer, sprintf(buffer, "\t\t<leftside>\n")); 309 310 Summand* summand; 311 for (int32 i = 0; i < fLeftSide->CountItems(); i++) { 312 summand = (Summand*)fLeftSide->ItemAt(i); 313 file->Write(buffer, sprintf(buffer, "\t\t\t<summand>\n")); 314 file->Write(buffer, sprintf(buffer, "\t\t\t\t<coeff>%f</coeff>\n", 315 summand->Coeff())); 316 BString varStr = *(summand->Var()); 317 file->Write(buffer, sprintf(buffer, "\t\t\t\t<var>%s</var>\n", 318 varStr.String())); 319 file->Write(buffer, sprintf(buffer, "\t\t\t</summand>\n")); 320 } 321 322 file->Write(buffer, sprintf(buffer, "\t\t</leftside>\n")); 323 324 const char* op = "??"; 325 if (fOp == kEQ) 326 op = "EQ"; 327 else if (fOp == kLE) 328 op = "LE"; 329 else if (fOp == kGE) 330 op = "GE"; 331 332 file->Write(buffer, sprintf(buffer, "\t\t<op>%s</op>\n", op)); 333 file->Write(buffer, sprintf(buffer, "\t\t<rightside>%f</rightside>\n", fRightSide)); 334 //~ file->Write(buffer, sprintf(buffer, "\t\t<penaltyneg>%s</penaltyneg>\n", PenaltyNeg())); 335 //~ file->Write(buffer, sprintf(buffer, "\t\t<penaltypos>%s</penaltypos>\n", PenaltyPos())); 336 file->Write(buffer, sprintf(buffer, "\t</constraint>\n")); 337 } 338 339 340 /** 341 * Gets the slack variable for the negative variations. 342 * 343 * @return the slack variable for the negative variations 344 */ 345 Variable* 346 Constraint::DNeg() const 347 { 348 if (fDNegObjSummand == NULL) 349 return NULL; 350 return fDNegObjSummand->Var(); 351 } 352 353 354 /** 355 * Gets the slack variable for the positive variations. 356 * 357 * @return the slack variable for the positive variations 358 */ 359 Variable* 360 Constraint::DPos() const 361 { 362 if (fDPosObjSummand == NULL) 363 return NULL; 364 return fDPosObjSummand->Var(); 365 } 366 367 368 bool 369 Constraint::IsValid() 370 { 371 return fIsValid; 372 } 373 374 375 void 376 Constraint::Invalidate() 377 { 378 STRACE(("Constraint::Invalidate() on %d\n", this)); 379 380 if (!fIsValid) 381 return; 382 383 fIsValid = false; 384 fLS->RemoveConstraint(this, false); 385 } 386 387 388 Constraint::operator BString() const 389 { 390 BString string; 391 GetString(string); 392 return string; 393 } 394 395 396 void 397 Constraint::GetString(BString& string) const 398 { 399 string << "Constraint "; 400 string << fLabel; 401 string << "(" << (int32)this << "): "; 402 403 if (fIsValid) { 404 for (int i = 0; i < fLeftSide->CountItems(); i++) { 405 Summand* s = static_cast<Summand*>(fLeftSide->ItemAt(i)); 406 string << (float)s->Coeff() << "*"; 407 s->Var()->GetString(string); 408 string << " "; 409 } 410 string << ((fOp == kEQ) ? "== " 411 : (fOp == kGE) ? ">= " 412 : (fOp == kLE) ? "<= " 413 : "?? "); 414 string << (float)fRightSide; 415 string << " PenaltyPos=" << (float)PenaltyPos(); 416 string << " PenaltyNeg=" << (float)PenaltyNeg(); 417 } else 418 string << "invalid"; 419 } 420 421 422 /** 423 * Constructor. 424 */ 425 Constraint::Constraint(LinearSpec* ls, SummandList* summands, OperatorType op, 426 double rightSide, double penaltyNeg, double penaltyPos) 427 : 428 fLS(ls), 429 fLeftSide(summands), 430 fOp(op), 431 fRightSide(rightSide), 432 fPenaltyNeg(penaltyNeg), 433 fPenaltyPos(penaltyPos), 434 fDNegObjSummand(NULL), 435 fDPosObjSummand(NULL), 436 fIsValid(true) 437 { 438 439 } 440 441 442 /** 443 * Destructor. 444 * Removes the constraint from its specification and deletes all the summands. 445 */ 446 Constraint::~Constraint() 447 { 448 Invalidate(); 449 450 for (int32 i = 0; i < fLeftSide->CountItems(); i++) 451 delete (Summand*)fLeftSide->ItemAt(i); 452 delete fLeftSide; 453 fLeftSide = NULL; 454 } 455 456