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 "LinearSpec.h" 10 11 #include <new> 12 13 #include "ActiveSetSolver.h" 14 15 16 using namespace LinearProgramming; 17 18 19 // #define DEBUG_LINEAR_SPECIFICATIONS 20 21 #ifdef DEBUG_LINEAR_SPECIFICATIONS 22 #include <stdio.h> 23 #define TRACE(x...) printf(x) 24 #else 25 #define TRACE(x...) /* nothing */ 26 #endif 27 28 29 SolverInterface::SolverInterface(LinearSpec* linSpec) 30 : 31 fLinearSpec(linSpec) 32 { 33 34 } 35 36 37 SolverInterface::~SolverInterface() 38 { 39 } 40 41 42 bool 43 SolverInterface::AddConstraint(Constraint* constraint, bool notifyListener) 44 { 45 return fLinearSpec->AddConstraint(constraint, notifyListener); 46 } 47 48 49 bool 50 SolverInterface::RemoveConstraint(Constraint* constraint, bool deleteConstraint, 51 bool notifyListener) 52 { 53 return fLinearSpec->RemoveConstraint(constraint, deleteConstraint, 54 notifyListener); 55 } 56 57 58 SpecificationListener::~SpecificationListener() 59 { 60 } 61 62 63 void 64 SpecificationListener::VariableAdded(Variable* variable) 65 { 66 } 67 68 69 void 70 SpecificationListener::VariableRemoved(Variable* variable) 71 { 72 } 73 74 75 void 76 SpecificationListener::ConstraintAdded(Constraint* constraint) 77 { 78 } 79 80 81 void 82 SpecificationListener::ConstraintRemoved(Constraint* constraint) 83 { 84 } 85 86 87 /** 88 * Constructor. 89 * Creates a new specification for a linear programming problem. 90 */ 91 LinearSpec::LinearSpec() 92 : 93 fResult(kError), 94 fSolvingTime(0) 95 { 96 fSolver = new ActiveSetSolver(this); 97 } 98 99 100 /** 101 * Destructor. 102 * Removes the specification and deletes all constraints, 103 * objective function summands and variables. 104 */ 105 LinearSpec::~LinearSpec() 106 { 107 for (int32 i = 0; i < fConstraints.CountItems(); i++) 108 delete (Constraint*)fConstraints.ItemAt(i); 109 while (fVariables.CountItems() > 0) 110 RemoveVariable(fVariables.ItemAt(0)); 111 112 delete fSolver; 113 } 114 115 116 bool 117 LinearSpec::AddListener(SpecificationListener* listener) 118 { 119 return fListeners.AddItem(listener); 120 } 121 122 123 bool 124 LinearSpec::RemoveListener(SpecificationListener* listener) 125 { 126 return fListeners.RemoveItem(listener); 127 } 128 129 130 /** 131 * Adds a new variable to the specification. 132 * 133 * @return the new variable 134 */ 135 Variable* 136 LinearSpec::AddVariable() 137 { 138 Variable* variable = new(std::nothrow) Variable(this); 139 if (!variable) 140 return NULL; 141 if (!AddVariable(variable)) { 142 delete variable; 143 return NULL; 144 } 145 146 return variable; 147 } 148 149 150 bool 151 LinearSpec::AddVariable(Variable* variable) 152 { 153 if (variable->IsValid()) 154 return false; 155 156 if (!fVariables.AddItem(variable)) 157 return false; 158 159 if (variable->fLS == NULL) 160 variable->fLS = this; 161 162 if (!fSolver->VariableAdded(variable)) { 163 fVariables.RemoveItem(variable); 164 return false; 165 } 166 variable->fIsValid = true; 167 168 if (!UpdateRange(variable)) { 169 RemoveVariable(variable, false); 170 return false; 171 } 172 173 for (int32 i = 0; i < fListeners.CountItems(); i++) 174 fListeners.ItemAt(i)->VariableAdded(variable); 175 176 return true; 177 } 178 179 180 bool 181 LinearSpec::RemoveVariable(Variable* variable, bool deleteVariable) 182 { 183 // must be called first otherwise the index is invalid 184 if (fSolver->VariableRemoved(variable) == false) 185 return false; 186 187 // do we know the variable? 188 if (fVariables.RemoveItem(variable) == false) 189 return false; 190 fUsedVariables.RemoveItem(variable); 191 variable->fIsValid = false; 192 193 // invalidate all constraints that use this variable 194 ConstraintList markedForInvalidation; 195 const ConstraintList& constraints = Constraints(); 196 for (int i = 0; i < constraints.CountItems(); i++) { 197 Constraint* constraint = constraints.ItemAt(i); 198 199 SummandList* summands = constraint->LeftSide(); 200 for (int j = 0; j < summands->CountItems(); j++) { 201 Summand* summand = summands->ItemAt(j); 202 if (summand->Var() == variable) { 203 markedForInvalidation.AddItem(constraint); 204 break; 205 } 206 } 207 } 208 for (int i = 0; i < markedForInvalidation.CountItems(); i++) 209 RemoveConstraint(markedForInvalidation.ItemAt(i)); 210 211 if (deleteVariable) 212 delete variable; 213 214 for (int32 i = 0; i < fListeners.CountItems(); i++) 215 fListeners.ItemAt(i)->VariableRemoved(variable); 216 217 return true; 218 } 219 220 221 int32 222 LinearSpec::IndexOf(const Variable* variable) const 223 { 224 return fUsedVariables.IndexOf(variable); 225 } 226 227 228 int32 229 LinearSpec::GlobalIndexOf(const Variable* variable) const 230 { 231 return fVariables.IndexOf(variable); 232 } 233 234 235 bool 236 LinearSpec::UpdateRange(Variable* variable) 237 { 238 if (!fSolver->VariableRangeChanged(variable)) 239 return false; 240 return true; 241 } 242 243 244 bool 245 LinearSpec::AddConstraint(Constraint* constraint) 246 { 247 return AddConstraint(constraint, true); 248 } 249 250 251 bool 252 LinearSpec::RemoveConstraint(Constraint* constraint, bool deleteConstraint) 253 { 254 return RemoveConstraint(constraint, deleteConstraint, true); 255 } 256 257 258 bool 259 LinearSpec::AddConstraint(Constraint* constraint, bool notifyListener) 260 { 261 if (!fConstraints.AddItem(constraint)) 262 return false; 263 264 // ref count the used variables 265 SummandList* leftSide = constraint->LeftSide(); 266 for (int i = 0; i < leftSide->CountItems(); i++) { 267 Variable* var = leftSide->ItemAt(i)->Var(); 268 _AddConstraintRef(var); 269 } 270 271 if (!fSolver->ConstraintAdded(constraint)) { 272 RemoveConstraint(constraint, false); 273 return false; 274 } 275 276 constraint->fLS = this; 277 278 if (notifyListener) { 279 for (int32 i = 0; i < fListeners.CountItems(); i++) 280 fListeners.ItemAt(i)->ConstraintAdded(constraint); 281 } 282 283 return true; 284 } 285 286 287 bool 288 LinearSpec::RemoveConstraint(Constraint* constraint, bool deleteConstraint, 289 bool notifyListener) 290 { 291 if (constraint == NULL) 292 return false; 293 fSolver->ConstraintRemoved(constraint); 294 if (!fConstraints.RemoveItem(constraint)) 295 return false; 296 297 SummandList* leftSide = constraint->LeftSide(); 298 for (int32 i = 0; i < leftSide->CountItems(); i++) { 299 Variable* var = leftSide->ItemAt(i)->Var(); 300 _RemoveConstraintRef(var); 301 } 302 303 if (notifyListener) { 304 for (int32 i = 0; i < fListeners.CountItems(); i++) 305 fListeners.ItemAt(i)->ConstraintRemoved(constraint); 306 } 307 308 constraint->fLS = NULL; 309 if (deleteConstraint) 310 delete constraint; 311 312 return true; 313 } 314 315 316 void 317 LinearSpec::_AddConstraintRef(Variable* var) 318 { 319 if (var->AddReference() == 1) 320 fUsedVariables.AddItem(var); 321 } 322 323 324 void 325 LinearSpec::_RemoveConstraintRef(Variable* var) 326 { 327 if (var->RemoveReference() == 0) 328 fUsedVariables.RemoveItem(var); 329 } 330 331 332 bool 333 LinearSpec::UpdateLeftSide(Constraint* constraint, 334 const SummandList* oldSummands) 335 { 336 SummandList* leftSide = constraint->LeftSide(); 337 if (leftSide != NULL) { 338 for (int32 i = 0; i < leftSide->CountItems(); i++) { 339 Variable* var = leftSide->ItemAt(i)->Var(); 340 _AddConstraintRef(var); 341 } 342 } 343 if (oldSummands != NULL) { 344 // the summands have changed, update the var ref count 345 for (int32 i = 0; i < oldSummands->CountItems(); i++) { 346 Variable* var = oldSummands->ItemAt(i)->Var(); 347 _RemoveConstraintRef(var); 348 } 349 } 350 351 if (!fSolver->LeftSideChanged(constraint)) 352 return false; 353 return true; 354 } 355 356 357 bool 358 LinearSpec::UpdateRightSide(Constraint* constraint) 359 { 360 if (!fSolver->RightSideChanged(constraint)) 361 return false; 362 return true; 363 } 364 365 366 bool 367 LinearSpec::UpdateOperator(Constraint* constraint) 368 { 369 if (!fSolver->OperatorChanged(constraint)) 370 return false; 371 return true; 372 } 373 374 375 bool 376 LinearSpec::UpdatePenalties(Constraint* constraint) 377 { 378 if (!fSolver->PenaltiesChanged(constraint)) 379 return false; 380 return true; 381 } 382 383 384 /** 385 * Adds a new soft linear constraint to the specification. 386 * i.e. a constraint that does not always have to be satisfied. 387 * 388 * @param coeffs the constraint's coefficients 389 * @param vars the constraint's variables 390 * @param op the constraint's operand 391 * @param rightSide the constant value on the constraint's right side 392 * @param penaltyNeg the coefficient penalizing negative deviations from the exact solution 393 * @param penaltyPos the coefficient penalizing positive deviations from the exact solution 394 */ 395 Constraint* 396 LinearSpec::AddConstraint(SummandList* summands, OperatorType op, 397 double rightSide, double penaltyNeg, double penaltyPos) 398 { 399 return _AddConstraint(summands, op, rightSide, penaltyNeg, penaltyPos); 400 } 401 402 403 /** 404 * Adds a new soft linear constraint to the specification with a single summand. 405 * 406 * @param coeff1 the constraint's first coefficient 407 * @param var1 the constraint's first variable 408 * @param op the constraint's operand 409 * @param rightSide the constant value on the constraint's right side 410 * @param penaltyNeg the coefficient penalizing negative deviations from the exact solution 411 * @param penaltyPos the coefficient penalizing positive deviations from the exact solution 412 */ 413 Constraint* 414 LinearSpec::AddConstraint(double coeff1, Variable* var1, 415 OperatorType op, double rightSide, double penaltyNeg, double penaltyPos) 416 { 417 SummandList* summands = new(std::nothrow) SummandList(1); 418 if (!summands) 419 return NULL; 420 summands->AddItem(new(std::nothrow) Summand(coeff1, var1)); 421 if (!_CheckSummandList(summands)) 422 return NULL; 423 return _AddConstraint(summands, op, rightSide, penaltyNeg, penaltyPos); 424 } 425 426 427 /** 428 * Adds a new soft linear constraint to the specification with two summands. 429 * 430 * @param coeff1 the constraint's first coefficient 431 * @param var1 the constraint's first variable 432 * @param coeff2 the constraint's second coefficient 433 * @param var2 the constraint's second variable 434 * @param op the constraint's operand 435 * @param rightSide the constant value on the constraint's right side 436 * @param penaltyNeg the coefficient penalizing negative deviations from the exact solution 437 * @param penaltyPos the coefficient penalizing positive deviations from the exact solution 438 */ 439 Constraint* 440 LinearSpec::AddConstraint(double coeff1, Variable* var1, 441 double coeff2, Variable* var2, OperatorType op, double rightSide, 442 double penaltyNeg, double penaltyPos) 443 { 444 SummandList* summands = new(std::nothrow) SummandList(2); 445 if (!summands) 446 return NULL; 447 summands->AddItem(new(std::nothrow) Summand(coeff1, var1)); 448 summands->AddItem(new(std::nothrow) Summand(coeff2, var2)); 449 if (!_CheckSummandList(summands)) 450 return NULL; 451 return _AddConstraint(summands, op, rightSide, penaltyNeg, penaltyPos); 452 } 453 454 455 /** 456 * Adds a new soft linear constraint to the specification with three summands. 457 * 458 * @param coeff1 the constraint's first coefficient 459 * @param var1 the constraint's first variable 460 * @param coeff2 the constraint's second coefficient 461 * @param var2 the constraint's second variable 462 * @param coeff3 the constraint's third coefficient 463 * @param var3 the constraint's third variable 464 * @param op the constraint's operand 465 * @param rightSide the constant value on the constraint's right side 466 * @param penaltyNeg the coefficient penalizing negative deviations from the exact solution 467 * @param penaltyPos the coefficient penalizing positive deviations from the exact solution 468 */ 469 Constraint* 470 LinearSpec::AddConstraint(double coeff1, Variable* var1, 471 double coeff2, Variable* var2, double coeff3, Variable* var3, 472 OperatorType op, double rightSide, double penaltyNeg, double penaltyPos) 473 { 474 SummandList* summands = new(std::nothrow) SummandList(2); 475 if (!summands) 476 return NULL; 477 summands->AddItem(new(std::nothrow) Summand(coeff1, var1)); 478 summands->AddItem(new(std::nothrow) Summand(coeff2, var2)); 479 summands->AddItem(new(std::nothrow) Summand(coeff3, var3)); 480 if (!_CheckSummandList(summands)) 481 return NULL; 482 return _AddConstraint(summands, op, rightSide, penaltyNeg, penaltyPos); 483 } 484 485 486 /** 487 * Adds a new soft linear constraint to the specification with four summands. 488 * 489 * @param coeff1 the constraint's first coefficient 490 * @param var1 the constraint's first variable 491 * @param coeff2 the constraint's second coefficient 492 * @param var2 the constraint's second variable 493 * @param coeff3 the constraint's third coefficient 494 * @param var3 the constraint's third variable 495 * @param coeff4 the constraint's fourth coefficient 496 * @param var4 the constraint's fourth variable 497 * @param op the constraint's operand 498 * @param rightSide the constant value on the constraint's right side 499 * @param penaltyNeg the coefficient penalizing negative deviations from the exact solution 500 * @param penaltyPos the coefficient penalizing positive deviations from the exact solution 501 */ 502 Constraint* 503 LinearSpec::AddConstraint(double coeff1, Variable* var1, 504 double coeff2, Variable* var2, double coeff3, Variable* var3, 505 double coeff4, Variable* var4, OperatorType op, double rightSide, 506 double penaltyNeg, double penaltyPos) 507 { 508 SummandList* summands = new(std::nothrow) SummandList(2); 509 if (!summands) 510 return NULL; 511 summands->AddItem(new(std::nothrow) Summand(coeff1, var1)); 512 summands->AddItem(new(std::nothrow) Summand(coeff2, var2)); 513 summands->AddItem(new(std::nothrow) Summand(coeff3, var3)); 514 summands->AddItem(new(std::nothrow) Summand(coeff4, var4)); 515 if (!_CheckSummandList(summands)) 516 return NULL; 517 return _AddConstraint(summands, op, rightSide, penaltyNeg, penaltyPos); 518 } 519 520 521 ResultType 522 LinearSpec::FindMins(const VariableList* variables) 523 { 524 fResult = fSolver->FindMins(variables); 525 return fResult; 526 } 527 528 529 ResultType 530 LinearSpec::FindMaxs(const VariableList* variables) 531 { 532 fResult = fSolver->FindMaxs(variables); 533 return fResult; 534 } 535 536 537 bool 538 LinearSpec::_CheckSummandList(SummandList* list) 539 { 540 bool ok = true; 541 for (int i = 0; i < list->CountItems(); i++) { 542 if (list->ItemAt(i) == NULL) { 543 ok = false; 544 break; 545 } 546 } 547 if (ok) 548 return true; 549 550 for (int i = 0; i < list->CountItems(); i++) 551 delete list->ItemAt(i); 552 delete list; 553 return false; 554 } 555 556 557 Constraint* 558 LinearSpec::_AddConstraint(SummandList* leftSide, OperatorType op, 559 double rightSide, double penaltyNeg, double penaltyPos) 560 { 561 Constraint* constraint = new(std::nothrow) Constraint(this, leftSide, 562 op, rightSide, penaltyNeg, penaltyPos); 563 if (constraint == NULL) 564 return NULL; 565 if (!AddConstraint(constraint)) { 566 delete constraint; 567 return NULL; 568 } 569 return constraint; 570 } 571 572 573 #ifdef DEBUG_LINEAR_SPECIFICATIONS 574 static bigtime_t sAverageSolvingTime = 0; 575 static int32 sSolvedCount = 0; 576 #endif 577 578 579 ResultType 580 LinearSpec::Solve() 581 { 582 bigtime_t startTime = system_time(); 583 584 fResult = fSolver->Solve(); 585 586 fSolvingTime = system_time() - startTime; 587 588 #ifdef DEBUG_LINEAR_SPECIFICATIONS 589 sAverageSolvingTime += fSolvingTime; 590 sSolvedCount++; 591 TRACE("Solving time %i average %i [micro s]\n", (int)fSolvingTime, 592 int(sAverageSolvingTime / sSolvedCount)); 593 #endif 594 595 return fResult; 596 } 597 598 599 /** 600 * Writes the specification into a text file. 601 * The file will be overwritten if it exists. 602 * 603 * @param fname the file name 604 */ 605 bool 606 LinearSpec::Save(const char* fileName) 607 { 608 return fSolver->SaveModel(fileName) == B_OK; 609 } 610 611 612 /** 613 * Gets the constraints generated by calls to Variable::SetRange() 614 * 615 */ 616 void 617 LinearSpec::GetRangeConstraints(const Variable* var, const Constraint** _min, 618 const Constraint** _max) const 619 { 620 fSolver->GetRangeConstraints(var, _min, _max); 621 } 622 623 624 /** 625 * Gets the constraints. 626 * 627 * @return the constraints 628 */ 629 const ConstraintList& 630 LinearSpec::Constraints() const 631 { 632 return fConstraints; 633 } 634 635 636 const VariableList& 637 LinearSpec::UsedVariables() const 638 { 639 return fUsedVariables; 640 } 641 642 643 const VariableList& 644 LinearSpec::AllVariables() const 645 { 646 return fVariables; 647 } 648 649 650 /** 651 * Gets the result type. 652 * 653 * @return the result type 654 */ 655 ResultType 656 LinearSpec::Result() const 657 { 658 return fResult; 659 } 660 661 662 /** 663 * Gets the solving time. 664 * 665 * @return the solving time 666 */ 667 bigtime_t 668 LinearSpec::SolvingTime() const 669 { 670 return fSolvingTime; 671 } 672 673 674 BString 675 LinearSpec::ToString() const 676 { 677 BString string; 678 string << "LinearSpec " << (addr_t)this << ":\n"; 679 for (int i = 0; i < fVariables.CountItems(); i++) { 680 Variable* variable = fVariables.ItemAt(i); 681 string += variable->ToString(); 682 string << "=" << (float)variable->Value() << " "; 683 } 684 string << "\n"; 685 for (int i = 0; i < fConstraints.CountItems(); i++) { 686 Constraint* c = fConstraints.ItemAt(i); 687 string << i << ": "; 688 string += c->ToString(); 689 string << "\n"; 690 } 691 string << "Result="; 692 if (fResult == kError) 693 string << "kError"; 694 else if (fResult == kOptimal) 695 string << "kOptimal"; 696 else if (fResult == kSuboptimal) 697 string << "kSuboptimal"; 698 else if (fResult == kInfeasible) 699 string << "kInfeasible"; 700 else if (fResult == kUnbounded) 701 string << "kUnbounded"; 702 else if (fResult == kDegenerate) 703 string << "kDegenerate"; 704 else if (fResult == kNumFailure) 705 string << "kNumFailure"; 706 else 707 string << fResult; 708 string << " SolvingTime=" << fSolvingTime << "micro s"; 709 return string; 710 } 711 712