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