1 /* 2 * Copyright 2007-2008, Christof Lutteroth, lutteroth@cs.auckland.ac.nz 3 * Copyright 2007-2008, James Kim, jkim202@ec.auckland.ac.nz 4 * Distributed under the terms of the MIT License. 5 */ 6 7 #include "Constraint.h" 8 #include "LinearSpec.h" 9 #include "Variable.h" 10 11 #include "lp_lib.h" 12 13 14 // Toggle debug output 15 //#define DEBUG_CONSTRAINT 16 17 #ifdef DEBUG_CONSTRAINT 18 # define STRACE(x) debug_printf x 19 #else 20 # define STRACE(x) ; 21 #endif 22 23 24 /** 25 * Gets the index of the constraint. 26 * 27 * @return the index of the constraint 28 */ 29 int32 30 Constraint::Index() const 31 { 32 int32 i = fLS->Constraints()->IndexOf(this); 33 if (i == -1) { 34 STRACE(("Constraint not part of fLS->Constraints().")); 35 return -1; 36 } 37 return i + 1; 38 } 39 40 41 /** 42 * Gets the left side of the constraint. 43 * 44 * @return pointer to a BList containing the summands on the left side of the constraint 45 */ 46 BList* 47 Constraint::LeftSide() 48 { 49 return fLeftSide; 50 } 51 52 53 /** 54 * Sets the summands on the left side of the constraint. 55 * The old summands are NOT deleted. 56 * 57 * @param summands a BList containing the Summand objects that make up the new left side 58 */ 59 void 60 Constraint::SetLeftSide(BList* summands) 61 { 62 if (!fIsValid) 63 return; 64 65 fLeftSide = summands; 66 UpdateLeftSide(); 67 } 68 69 70 void 71 Constraint::UpdateLeftSide() 72 { 73 if (!fIsValid) 74 return; 75 76 double coeffs[fLeftSide->CountItems() + 2]; 77 int varIndexes[fLeftSide->CountItems() + 2]; 78 int32 i; 79 for (i = 0; i < fLeftSide->CountItems(); i++) { 80 Summand* s = (Summand*)fLeftSide->ItemAt(i); 81 coeffs[i] = s->Coeff(); 82 varIndexes[i] = s->Var()->Index(); 83 } 84 85 if (fDNegObjSummand != NULL && fOp != OperatorType(LE)) { 86 varIndexes[i] = fDNegObjSummand->Var()->Index(); 87 coeffs[i] = 1.0; 88 i++; 89 } 90 91 if (fDPosObjSummand != NULL && fOp != OperatorType(GE)) { 92 varIndexes[i] = fDPosObjSummand->Var()->Index(); 93 coeffs[i] = -1.0; 94 i++; 95 } 96 97 if (!set_rowex(fLS->fLP, this->Index(), i, &coeffs[0], &varIndexes[0])) 98 STRACE(("Error in set_rowex.")); 99 100 fLS->UpdateObjFunction(); 101 fLS->RemovePresolved(); 102 } 103 104 105 void 106 Constraint::SetLeftSide(double coeff1, Variable* var1) 107 { 108 if (!fIsValid) 109 return; 110 111 for (int i=0; i<fLeftSide->CountItems(); i++) 112 delete (Summand*)fLeftSide->ItemAt(i); 113 fLeftSide->MakeEmpty(); 114 fLeftSide->AddItem(new Summand(coeff1, var1)); 115 UpdateLeftSide(); 116 } 117 118 119 void 120 Constraint::SetLeftSide(double coeff1, Variable* var1, 121 double coeff2, Variable* var2) 122 { 123 if (!fIsValid) 124 return; 125 126 for (int i=0; i<fLeftSide->CountItems(); i++) 127 delete (Summand*)fLeftSide->ItemAt(i); 128 fLeftSide->MakeEmpty(); 129 fLeftSide->AddItem(new Summand(coeff1, var1)); 130 fLeftSide->AddItem(new Summand(coeff2, var2)); 131 UpdateLeftSide(); 132 } 133 134 135 void 136 Constraint::SetLeftSide(double coeff1, Variable* var1, 137 double coeff2, Variable* var2, 138 double coeff3, Variable* var3) 139 { 140 if (!fIsValid) 141 return; 142 143 for (int i=0; i<fLeftSide->CountItems(); i++) 144 delete (Summand*)fLeftSide->ItemAt(i); 145 fLeftSide->MakeEmpty(); 146 fLeftSide->AddItem(new Summand(coeff1, var1)); 147 fLeftSide->AddItem(new Summand(coeff2, var2)); 148 fLeftSide->AddItem(new Summand(coeff3, var3)); 149 UpdateLeftSide(); 150 } 151 152 153 void 154 Constraint::SetLeftSide(double coeff1, Variable* var1, 155 double coeff2, Variable* var2, 156 double coeff3, Variable* var3, 157 double coeff4, Variable* var4) 158 { 159 if (!fIsValid) 160 return; 161 162 for (int i=0; i<fLeftSide->CountItems(); i++) 163 delete (Summand*)fLeftSide->ItemAt(i); 164 fLeftSide->MakeEmpty(); 165 fLeftSide->AddItem(new Summand(coeff1, var1)); 166 fLeftSide->AddItem(new Summand(coeff2, var2)); 167 fLeftSide->AddItem(new Summand(coeff3, var3)); 168 fLeftSide->AddItem(new Summand(coeff4, var4)); 169 UpdateLeftSide(); 170 } 171 172 173 /** 174 * Gets the operator used for this constraint. 175 * 176 * @return the operator used for this constraint 177 */ 178 OperatorType 179 Constraint::Op() 180 { 181 return fOp; 182 } 183 184 185 /** 186 * Sets the operator used for this constraint. 187 * 188 * @param value operator 189 */ 190 void 191 Constraint::SetOp(OperatorType value) 192 { 193 if (!fIsValid) 194 return; 195 196 fOp = value; 197 if (!set_constr_type(fLS->fLP, this->Index(), 198 ((fOp == OperatorType(EQ)) ? EQ 199 : (fOp == OperatorType(GE)) ? GE 200 : LE))) 201 STRACE(("Error in set_constr_type.")); 202 203 fLS->RemovePresolved(); 204 } 205 206 207 /** 208 * Gets the constant value that is on the right side of the operator. 209 * 210 * @return the constant value that is on the right side of the operator 211 */ 212 double 213 Constraint::RightSide() const 214 { 215 return fRightSide; 216 } 217 218 219 /** 220 * Sets the constant value that is on the right side of the operator. 221 * 222 * @param value constant value that is on the right side of the operator 223 */ 224 void 225 Constraint::SetRightSide(double value) 226 { 227 if (!fIsValid) 228 return; 229 230 if (fRightSide == value) 231 return; 232 233 fRightSide = value; 234 if (!set_rh(fLS->fLP, Index(), fRightSide)) 235 STRACE(("Error in set_rh.")); 236 237 fLS->RemovePresolved(); 238 } 239 240 241 /** 242 * Gets the penalty coefficient for negative deviations. 243 * 244 * @return the penalty coefficient 245 */ 246 double 247 Constraint::PenaltyNeg() const 248 { 249 if (fDNegObjSummand == NULL) 250 return INFINITY; 251 return fDNegObjSummand->Coeff(); 252 } 253 254 255 /** 256 * The penalty coefficient for negative deviations from the soft constraint's exact solution, 257 * i.e. if the left side is too large. 258 * 259 * @param value coefficient of negative penalty <code>double</code> 260 */ 261 void 262 Constraint::SetPenaltyNeg(double value) 263 { 264 if (!fIsValid) 265 return; 266 267 if (fDNegObjSummand == NULL) { 268 fDNegObjSummand = new Summand(value, new Variable(fLS)); 269 fLS->ObjFunction()->AddItem(fDNegObjSummand); 270 UpdateLeftSide(); 271 fLS->UpdateObjFunction(); 272 return; 273 } 274 275 if (value == fDNegObjSummand->Coeff()) 276 return; 277 278 fDNegObjSummand->SetCoeff(value); 279 fLS->UpdateObjFunction(); 280 } 281 282 283 /** 284 * Gets the penalty coefficient for positive deviations. 285 * 286 * @return the penalty coefficient 287 */ 288 double 289 Constraint::PenaltyPos() const 290 { 291 if (fDPosObjSummand == NULL) 292 return INFINITY; 293 return fDPosObjSummand->Coeff(); 294 } 295 296 297 /** 298 * The penalty coefficient for negative deviations from the soft constraint's exact solution, 299 * i.e. if the left side is too small. 300 * 301 * @param value coefficient of positive penalty <code>double</code> 302 */ 303 void 304 Constraint::SetPenaltyPos(double value) 305 { 306 if (!fIsValid) 307 return; 308 309 if (fDPosObjSummand == NULL) { 310 fDPosObjSummand = new Summand(value, new Variable(fLS)); 311 fLS->ObjFunction()->AddItem(fDPosObjSummand); 312 UpdateLeftSide(); 313 fLS->UpdateObjFunction(); 314 return; 315 } 316 317 if (value == fDPosObjSummand->Coeff()) 318 return; 319 320 fDPosObjSummand->SetCoeff(value); 321 fLS->UpdateObjFunction(); 322 } 323 324 325 const char* 326 Constraint::Label() 327 { 328 return fLabel.String(); 329 } 330 331 332 void 333 Constraint::SetLabel(const char* label) 334 { 335 fLabel = label; 336 } 337 338 339 void 340 Constraint::WriteXML(BFile* file) 341 { 342 if (file->IsWritable() && fOwner == NULL) { 343 char buffer[200]; 344 345 file->Write(buffer, sprintf(buffer, "\t<constraint>\n")); 346 file->Write(buffer, sprintf(buffer, "\t\t<leftside>\n")); 347 348 Summand* summand; 349 for (int32 i = 0; i < fLeftSide->CountItems(); i++) { 350 summand = (Summand*)fLeftSide->ItemAt(i); 351 file->Write(buffer, sprintf(buffer, "\t\t\t<summand>\n")); 352 file->Write(buffer, sprintf(buffer, "\t\t\t\t<coeff>%f</coeff>\n", 353 summand->Coeff())); 354 BString varStr = *(summand->Var()); 355 file->Write(buffer, sprintf(buffer, "\t\t\t\t<var>%s</var>\n", 356 varStr.String())); 357 file->Write(buffer, sprintf(buffer, "\t\t\t</summand>\n")); 358 } 359 360 file->Write(buffer, sprintf(buffer, "\t\t</leftside>\n")); 361 362 const char* op = "??"; 363 if (fOp == OperatorType(EQ)) 364 op = "EQ"; 365 else if (fOp == OperatorType(LE)) 366 op = "LE"; 367 else if (fOp == OperatorType(GE)) 368 op = "GE"; 369 370 file->Write(buffer, sprintf(buffer, "\t\t<op>%s</op>\n", op)); 371 file->Write(buffer, sprintf(buffer, "\t\t<rightside>%f</rightside>\n", fRightSide)); 372 //~ file->Write(buffer, sprintf(buffer, "\t\t<penaltyneg>%s</penaltyneg>\n", PenaltyNeg())); 373 //~ file->Write(buffer, sprintf(buffer, "\t\t<penaltypos>%s</penaltypos>\n", PenaltyPos())); 374 file->Write(buffer, sprintf(buffer, "\t</constraint>\n")); 375 } 376 } 377 378 379 /** 380 * Gets the slack variable for the negative variations. 381 * 382 * @return the slack variable for the negative variations 383 */ 384 Variable* 385 Constraint::DNeg() const 386 { 387 if (fDNegObjSummand == NULL) 388 return NULL; 389 return fDNegObjSummand->Var(); 390 } 391 392 393 /** 394 * Gets the slack variable for the positive variations. 395 * 396 * @return the slack variable for the positive variations 397 */ 398 Variable* 399 Constraint::DPos() const 400 { 401 if (fDPosObjSummand == NULL) 402 return NULL; 403 return fDPosObjSummand->Var(); 404 } 405 406 407 void 408 Constraint::SetOwner(void* owner) 409 { 410 fOwner = owner; 411 } 412 413 414 void* 415 Constraint::Owner() const 416 { 417 return fOwner; 418 } 419 420 421 bool 422 Constraint::IsValid() 423 { 424 return fIsValid; 425 } 426 427 428 void 429 Constraint::Invalidate() 430 { 431 STRACE(("Constraint::Invalidate() on %d\n", this)); 432 433 if (!fIsValid) 434 return; 435 436 fIsValid = false; 437 438 for (int32 i = 0; i < fLeftSide->CountItems(); i++) 439 delete (Summand*)fLeftSide->ItemAt(i); 440 delete fLeftSide; 441 fLeftSide = NULL; 442 443 if (fDNegObjSummand) { 444 fLS->ObjFunction()->RemoveItem(fDNegObjSummand); 445 delete fDNegObjSummand->Var(); 446 delete fDNegObjSummand; 447 fDNegObjSummand = NULL; 448 } 449 if (fDPosObjSummand) { 450 fLS->ObjFunction()->RemoveItem(fDPosObjSummand); 451 delete fDPosObjSummand->Var(); 452 delete fDPosObjSummand; 453 fDPosObjSummand = NULL; 454 } 455 456 del_constraint(fLS->fLP, this->Index()); 457 fLS->Constraints()->RemoveItem(this); 458 } 459 460 461 Constraint::operator BString() const 462 { 463 BString string; 464 GetString(string); 465 return string; 466 } 467 468 469 void 470 Constraint::GetString(BString& string) const 471 { 472 string << "Constraint "; 473 string << fLabel; 474 string << "(" << (int32)this << "): "; 475 476 if (fIsValid) { 477 for (int i = 0; i < fLeftSide->CountItems(); i++) { 478 Summand* s = static_cast<Summand*>(fLeftSide->ItemAt(i)); 479 string << (float)s->Coeff() << "*"; 480 s->Var()->GetString(string); 481 string << " "; 482 } 483 string << ((fOp == OperatorType(EQ)) ? "== " 484 : (fOp == OperatorType(GE)) ? ">= " 485 : (fOp == OperatorType(LE)) ? "<= " 486 : "?? "); 487 string << (float)fRightSide; 488 string << " PenaltyPos=" << (float)PenaltyPos(); 489 string << " PenaltyNeg=" << (float)PenaltyNeg(); 490 } else 491 string << "invalid"; 492 } 493 494 495 /** 496 * Constructor. 497 */ 498 Constraint::Constraint(LinearSpec* ls, BList* summands, OperatorType op, 499 double rightSide, double penaltyNeg, double penaltyPos) 500 : fLS(ls), 501 fLeftSide(summands), 502 fOp(op), 503 fRightSide(rightSide), 504 fOwner(NULL), 505 fIsValid(true) 506 { 507 double coeffs[summands->CountItems() + 2]; 508 int varIndexes[summands->CountItems() + 2]; 509 int32 i; 510 for (i = 0; i < summands->CountItems(); i++) { 511 Summand* s = (Summand*)summands->ItemAt(i); 512 coeffs[i] = s->Coeff(); 513 varIndexes[i] = s->Var()->Index(); 514 } 515 516 if (penaltyNeg != INFINITY 517 && fOp != OperatorType(LE)) { 518 fDNegObjSummand = new Summand(penaltyNeg, new Variable(fLS)); 519 fLS->fObjFunction->AddItem(fDNegObjSummand); 520 varIndexes[i] = fDNegObjSummand->Var()->Index(); 521 coeffs[i] = 1.0; 522 i++; 523 } 524 else 525 fDNegObjSummand = NULL; 526 527 if (penaltyPos != INFINITY 528 && fOp != OperatorType(GE)) { 529 fDPosObjSummand = new Summand(penaltyPos, new Variable(fLS)); 530 fLS->fObjFunction->AddItem(fDPosObjSummand); 531 varIndexes[i] = fDPosObjSummand->Var()->Index(); 532 coeffs[i] = -1.0; 533 i++; 534 } 535 else 536 fDPosObjSummand = NULL; 537 538 if (!add_constraintex(fLS->fLP, i, &coeffs[0], &varIndexes[0], 539 ((fOp == OperatorType(EQ)) ? EQ 540 : (fOp == OperatorType(GE)) ? GE 541 : LE), rightSide)) 542 STRACE(("Error in add_constraintex.")); 543 544 fLS->UpdateObjFunction(); 545 fLS->Constraints()->AddItem(this); 546 } 547 548 549 /** 550 * Destructor. 551 * Removes the constraint from its specification and deletes all the summands. 552 */ 553 Constraint::~Constraint() 554 { 555 Invalidate(); 556 } 557 558