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() 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 fRightSide = value; 231 if (!set_rh(fLS->fLP, Index(), fRightSide)) 232 STRACE(("Error in set_rh.")); 233 234 fLS->RemovePresolved(); 235 } 236 237 238 /** 239 * Gets the penalty coefficient for negative deviations. 240 * 241 * @return the penalty coefficient 242 */ 243 double 244 Constraint::PenaltyNeg() const 245 { 246 if (fDNegObjSummand == NULL) 247 return INFINITY; 248 return fDNegObjSummand->Coeff(); 249 } 250 251 252 /** 253 * The penalty coefficient for negative deviations from the soft constraint's exact solution, 254 * i.e. if the left side is too large. 255 * 256 * @param value coefficient of negative penalty <code>double</code> 257 */ 258 void 259 Constraint::SetPenaltyNeg(double value) 260 { 261 if (!fIsValid) 262 return; 263 264 if (fDNegObjSummand == NULL) { 265 fDNegObjSummand = new Summand(value, new Variable(fLS)); 266 fLS->ObjFunction()->AddItem(fDNegObjSummand); 267 UpdateLeftSide(); 268 fLS->UpdateObjFunction(); 269 return; 270 } 271 272 if (value == fDNegObjSummand->Coeff()) 273 return; 274 275 fDNegObjSummand->SetCoeff(value); 276 fLS->UpdateObjFunction(); 277 } 278 279 280 /** 281 * Gets the penalty coefficient for positive deviations. 282 * 283 * @return the penalty coefficient 284 */ 285 double 286 Constraint::PenaltyPos() const 287 { 288 if (fDPosObjSummand == NULL) 289 return INFINITY; 290 return fDPosObjSummand->Coeff(); 291 } 292 293 294 /** 295 * The penalty coefficient for negative deviations from the soft constraint's exact solution, 296 * i.e. if the left side is too small. 297 * 298 * @param value coefficient of positive penalty <code>double</code> 299 */ 300 void 301 Constraint::SetPenaltyPos(double value) 302 { 303 if (!fIsValid) 304 return; 305 306 if (fDPosObjSummand == NULL) { 307 fDPosObjSummand = new Summand(value, new Variable(fLS)); 308 fLS->ObjFunction()->AddItem(fDPosObjSummand); 309 UpdateLeftSide(); 310 fLS->UpdateObjFunction(); 311 return; 312 } 313 314 if (value == fDPosObjSummand->Coeff()) 315 return; 316 317 fDPosObjSummand->SetCoeff(value); 318 fLS->UpdateObjFunction(); 319 } 320 321 322 const char* 323 Constraint::Label() 324 { 325 return fLabel; 326 } 327 328 329 void 330 Constraint::SetLabel(const char* label) 331 { 332 fLabel = (char*) malloc(strlen(label) + 1); 333 strcpy(fLabel, label); 334 } 335 336 337 void 338 Constraint::WriteXML(BFile* file) 339 { 340 if (file->IsWritable() && fOwner == NULL) { 341 char buffer[200]; 342 343 file->Write(buffer, sprintf(buffer, "\t<constraint>\n")); 344 file->Write(buffer, sprintf(buffer, "\t\t<leftside>\n")); 345 346 Summand* summand; 347 for (int32 i = 0; i < fLeftSide->CountItems(); i++) { 348 summand = (Summand*)fLeftSide->ItemAt(i); 349 file->Write(buffer, sprintf(buffer, "\t\t\t<summand>\n")); 350 file->Write(buffer, sprintf(buffer, "\t\t\t\t<coeff>%f</coeff>\n", 351 summand->Coeff())); 352 BString* varStr = summand->Var()->ToBString(); 353 file->Write(buffer, sprintf(buffer, "\t\t\t\t<var>%s</var>\n", 354 varStr->String())); 355 delete varStr; 356 file->Write(buffer, sprintf(buffer, "\t\t\t</summand>\n")); 357 } 358 359 file->Write(buffer, sprintf(buffer, "\t\t</leftside>\n")); 360 361 char* op; 362 if (fOp == OperatorType(EQ)) 363 op = "EQ"; 364 else if (fOp == OperatorType(LE)) 365 op = "LE"; 366 else if (fOp == OperatorType(GE)) 367 op = "GE"; 368 369 file->Write(buffer, sprintf(buffer, "\t\t<op>%s</op>\n", op)); 370 file->Write(buffer, sprintf(buffer, "\t\t<rightside>%f</rightside>\n", fRightSide)); 371 //~ file->Write(buffer, sprintf(buffer, "\t\t<penaltyneg>%s</penaltyneg>\n", PenaltyNeg())); 372 //~ file->Write(buffer, sprintf(buffer, "\t\t<penaltypos>%s</penaltypos>\n", PenaltyPos())); 373 file->Write(buffer, sprintf(buffer, "\t</constraint>\n")); 374 } 375 } 376 377 378 /** 379 * Gets the slack variable for the negative variations. 380 * 381 * @return the slack variable for the negative variations 382 */ 383 Variable* 384 Constraint::DNeg() const 385 { 386 if (fDNegObjSummand == NULL) 387 return NULL; 388 return fDNegObjSummand->Var(); 389 } 390 391 392 /** 393 * Gets the slack variable for the positive variations. 394 * 395 * @return the slack variable for the positive variations 396 */ 397 Variable* 398 Constraint::DPos() const 399 { 400 if (fDPosObjSummand == NULL) 401 return NULL; 402 return fDPosObjSummand->Var(); 403 } 404 405 406 void 407 Constraint::SetOwner(void* owner) 408 { 409 fOwner = owner; 410 } 411 412 413 void* 414 Constraint::Owner() const 415 { 416 return fOwner; 417 } 418 419 420 bool 421 Constraint::IsValid() 422 { 423 return fIsValid; 424 } 425 426 427 void 428 Constraint::Invalidate() 429 { 430 STRACE(("Constraint::Invalidate() on %d\n", this)); 431 432 if (!fIsValid) 433 return; 434 435 fIsValid = false; 436 437 for (int32 i = 0; i < fLeftSide->CountItems(); i++) 438 delete (Summand*)fLeftSide->ItemAt(i); 439 delete fLeftSide; 440 fLeftSide = NULL; 441 442 if (fDNegObjSummand) { 443 fLS->ObjFunction()->RemoveItem(fDNegObjSummand); 444 delete fDNegObjSummand->Var(); 445 delete fDNegObjSummand; 446 fDNegObjSummand = NULL; 447 } 448 if (fDPosObjSummand) { 449 fLS->ObjFunction()->RemoveItem(fDPosObjSummand); 450 delete fDPosObjSummand->Var(); 451 delete fDPosObjSummand; 452 fDPosObjSummand = NULL; 453 } 454 455 del_constraint(fLS->fLP, this->Index()); 456 fLS->Constraints()->RemoveItem(this); 457 } 458 459 460 BString* 461 Constraint::ToBString() 462 { 463 BString* str = new BString(); 464 *str << "Constraint "; 465 if (fLabel) 466 *str << fLabel; 467 *str << "(" << (int32)this << "): "; 468 469 if (fIsValid) { 470 for (int i = 0; i < fLeftSide->CountItems(); i++) { 471 Summand* s = static_cast<Summand*>(fLeftSide->ItemAt(i)); 472 *str << (float)s->Coeff() << "*"; 473 BString* varString = s->Var()->ToBString(); 474 *str << *varString << " "; 475 delete varString; 476 } 477 *str << ((fOp == OperatorType(EQ)) ? "== " 478 : (fOp == OperatorType(GE)) ? ">= " 479 : (fOp == OperatorType(LE)) ? "<= " 480 : "?? "); 481 *str << (float)fRightSide; 482 *str << " PenaltyPos=" << (float)PenaltyPos(); 483 *str << " PenaltyNeg=" << (float)PenaltyNeg(); 484 } else 485 *str << "invalid"; 486 return str; 487 } 488 489 490 const char* 491 Constraint::ToString() 492 { 493 BString* str = ToBString(); 494 char* result = (char*) malloc(str->Length() + 1); 495 str->CopyInto(result, 0, str->Length()); 496 delete str; 497 return result; 498 } 499 500 501 /** 502 * Constructor. 503 */ 504 Constraint::Constraint(LinearSpec* ls, BList* summands, OperatorType op, 505 double rightSide, double penaltyNeg, double penaltyPos) 506 : fLS(ls), 507 fLeftSide(summands), 508 fOp(op), 509 fRightSide(rightSide), 510 fOwner(NULL), 511 fLabel(NULL), 512 fIsValid(true) 513 { 514 double coeffs[summands->CountItems() + 2]; 515 int varIndexes[summands->CountItems() + 2]; 516 int32 i; 517 for (i = 0; i < summands->CountItems(); i++) { 518 Summand* s = (Summand*)summands->ItemAt(i); 519 coeffs[i] = s->Coeff(); 520 varIndexes[i] = s->Var()->Index(); 521 } 522 523 if (penaltyNeg != INFINITY 524 && fOp != OperatorType(LE)) { 525 fDNegObjSummand = new Summand(penaltyNeg, new Variable(fLS)); 526 fLS->fObjFunction->AddItem(fDNegObjSummand); 527 varIndexes[i] = fDNegObjSummand->Var()->Index(); 528 coeffs[i] = 1.0; 529 i++; 530 } 531 else 532 fDNegObjSummand = NULL; 533 534 if (penaltyPos != INFINITY 535 && fOp != OperatorType(GE)) { 536 fDPosObjSummand = new Summand(penaltyPos, new Variable(fLS)); 537 fLS->fObjFunction->AddItem(fDPosObjSummand); 538 varIndexes[i] = fDPosObjSummand->Var()->Index(); 539 coeffs[i] = -1.0; 540 i++; 541 } 542 else 543 fDPosObjSummand = NULL; 544 545 if (!add_constraintex(fLS->fLP, i, &coeffs[0], &varIndexes[0], 546 ((fOp == OperatorType(EQ)) ? EQ 547 : (fOp == OperatorType(GE)) ? GE 548 : LE), rightSide)) 549 STRACE(("Error in add_constraintex.")); 550 551 fLS->UpdateObjFunction(); 552 fLS->Constraints()->AddItem(this); 553 } 554 555 556 /** 557 * Destructor. 558 * Removes the constraint from its specification and deletes all the summands. 559 */ 560 Constraint::~Constraint() 561 { 562 Invalidate(); 563 } 564 565