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 16using 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 29SolverInterface::SolverInterface(LinearSpec* linSpec) 30 : 31 fLinearSpec(linSpec) 32{ 33 34} 35 36 37SolverInterface::~SolverInterface() 38{ 39} 40 41 42bool 43SolverInterface::AddConstraint(Constraint* constraint, bool notifyListener) 44{ 45 return fLinearSpec->AddConstraint(constraint, notifyListener); 46} 47 48 49bool 50SolverInterface::RemoveConstraint(Constraint* constraint, bool deleteConstraint, 51 bool notifyListener) 52{ 53 return fLinearSpec->RemoveConstraint(constraint, deleteConstraint, 54 notifyListener); 55} 56 57 58SpecificationListener::~SpecificationListener() 59{ 60} 61 62 63void 64SpecificationListener::VariableAdded(Variable* variable) 65{ 66} 67 68 69void 70SpecificationListener::VariableRemoved(Variable* variable) 71{ 72} 73 74 75void 76SpecificationListener::ConstraintAdded(Constraint* constraint) 77{ 78} 79 80 81void 82SpecificationListener::ConstraintRemoved(Constraint* constraint) 83{ 84} 85 86 87/** 88 * Constructor. 89 * Creates a new specification for a linear programming problem. 90 */ 91LinearSpec::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 */ 105LinearSpec::~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 116bool 117LinearSpec::AddListener(SpecificationListener* listener) 118{ 119 return fListeners.AddItem(listener); 120} 121 122 123bool 124LinearSpec::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 */ 135Variable* 136LinearSpec::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 150bool 151LinearSpec::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 180bool 181LinearSpec::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 221int32 222LinearSpec::IndexOf(const Variable* variable) const 223{ 224 return fUsedVariables.IndexOf(variable); 225} 226 227 228int32 229LinearSpec::GlobalIndexOf(const Variable* variable) const 230{ 231 return fVariables.IndexOf(variable); 232} 233 234 235bool 236LinearSpec::UpdateRange(Variable* variable) 237{ 238 if (!fSolver->VariableRangeChanged(variable)) 239 return false; 240 return true; 241} 242 243 244bool 245LinearSpec::AddConstraint(Constraint* constraint) 246{ 247 return AddConstraint(constraint, true); 248} 249 250 251bool 252LinearSpec::RemoveConstraint(Constraint* constraint, bool deleteConstraint) 253{ 254 return RemoveConstraint(constraint, deleteConstraint, true); 255} 256 257 258bool 259LinearSpec::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 287bool 288LinearSpec::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 316void 317LinearSpec::_AddConstraintRef(Variable* var) 318{ 319 if (var->AddReference() == 1) 320 fUsedVariables.AddItem(var); 321} 322 323 324void 325LinearSpec::_RemoveConstraintRef(Variable* var) 326{ 327 if (var->RemoveReference() == 0) 328 fUsedVariables.RemoveItem(var); 329} 330 331 332bool 333LinearSpec::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 357bool 358LinearSpec::UpdateRightSide(Constraint* constraint) 359{ 360 if (!fSolver->RightSideChanged(constraint)) 361 return false; 362 return true; 363} 364 365 366bool 367LinearSpec::UpdateOperator(Constraint* constraint) 368{ 369 if (!fSolver->OperatorChanged(constraint)) 370 return false; 371 return true; 372} 373 374 375bool 376LinearSpec::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 */ 395Constraint* 396LinearSpec::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 */ 413Constraint* 414LinearSpec::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 */ 439Constraint* 440LinearSpec::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 */ 469Constraint* 470LinearSpec::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 */ 502Constraint* 503LinearSpec::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 521ResultType 522LinearSpec::FindMins(const VariableList* variables) 523{ 524 fResult = fSolver->FindMins(variables); 525 return fResult; 526} 527 528 529ResultType 530LinearSpec::FindMaxs(const VariableList* variables) 531{ 532 fResult = fSolver->FindMaxs(variables); 533 return fResult; 534} 535 536 537bool 538LinearSpec::_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 557Constraint* 558LinearSpec::_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 574static bigtime_t sAverageSolvingTime = 0; 575static int32 sSolvedCount = 0; 576#endif 577 578 579ResultType 580LinearSpec::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 */ 605bool 606LinearSpec::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 */ 616void 617LinearSpec::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 */ 629const ConstraintList& 630LinearSpec::Constraints() const 631{ 632 return fConstraints; 633} 634 635 636const VariableList& 637LinearSpec::UsedVariables() const 638{ 639 return fUsedVariables; 640} 641 642 643const VariableList& 644LinearSpec::AllVariables() const 645{ 646 return fVariables; 647} 648 649 650/** 651 * Gets the result type. 652 * 653 * @return the result type 654 */ 655ResultType 656LinearSpec::Result() const 657{ 658 return fResult; 659} 660 661 662/** 663 * Gets the solving time. 664 * 665 * @return the solving time 666 */ 667bigtime_t 668LinearSpec::SolvingTime() const 669{ 670 return fSolvingTime; 671} 672 673 674BString 675LinearSpec::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