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