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 "LinearSpec.h" 8 9 10 /** 11 * Constructor. 12 * Creates a new specification for a linear programming problem. 13 */ 14 LinearSpec::LinearSpec() 15 : fCountColumns(0), 16 fLpPresolved(NULL), 17 fOptimization(MINIMIZE), 18 fObjFunction(new BList()), 19 fVariables(new BList()), 20 fConstraints(new BList()), 21 fResult(ERROR), 22 fObjectiveValue(NAN), 23 fSolvingTime(NAN) 24 { 25 fLP = make_lp(0, 0); 26 if (fLP == NULL) 27 printf("Couldn't construct a new model."); 28 set_verbose(fLP, 1); 29 } 30 31 32 /** 33 * Destructor. 34 * Removes the specification and deletes all constraints, 35 * objective function summands and variables. 36 */ 37 LinearSpec::~LinearSpec() 38 { 39 RemovePresolved(); 40 for (int32 i=0; i<fConstraints->CountItems(); i++) 41 delete (Constraint*)fConstraints->ItemAt(i); 42 for (int32 i=0; i<fObjFunction->CountItems(); i++) 43 delete (Summand*)fObjFunction->ItemAt(i); 44 for (int32 i=0; i<fVariables->CountItems(); i++) 45 delete (Variable*)fVariables->ItemAt(i); 46 delete_lp(fLP); 47 } 48 49 50 /** 51 * Adds a new variable to the specification. 52 * 53 * @return the new variable 54 */ 55 Variable* 56 LinearSpec::AddVariable() 57 { 58 return new Variable(this); 59 } 60 61 62 /** 63 * Adds a new hard linear constraint to the specification. 64 * 65 * @param coeffs the constraint's coefficients 66 * @param vars the constraint's variables 67 * @param op the constraint's operand 68 * @param rightSide the constant value on the constraint's right side 69 * @return the new constraint 70 */ 71 Constraint* 72 LinearSpec::AddConstraint(BList* summands, OperatorType op, double rightSide) 73 { 74 Constraint* c = new Constraint(this, summands, op, rightSide, 75 INFINITY, INFINITY); 76 RemovePresolved(); 77 return c; 78 } 79 80 81 /** 82 * Adds a new hard linear constraint to the specification with a single summand. 83 * 84 * @param coeff1 the constraint's first coefficient 85 * @param var1 the constraint's first variable 86 * @param op the constraint's operand 87 * @param rightSide the constant value on the constraint's right side 88 * @return the new constraint 89 */ 90 Constraint* 91 LinearSpec::AddConstraint(double coeff1, Variable* var1, 92 OperatorType op, double rightSide) 93 { 94 BList* summands = new BList(1); 95 summands->AddItem(new Summand(coeff1, var1)); 96 Constraint* c = new Constraint(this, summands, op, rightSide, 97 INFINITY, INFINITY); 98 RemovePresolved(); 99 return c; 100 } 101 102 103 /** 104 * Adds a new hard linear constraint to the specification with two summands. 105 * 106 * @param coeff1 the constraint's first coefficient 107 * @param var1 the constraint's first variable 108 * @param coeff2 the constraint's second coefficient 109 * @param var2 the constraint's second variable 110 * @param op the constraint's operand 111 * @param rightSide the constant value on the constraint's right side 112 * @return the new constraint 113 */ 114 Constraint* 115 LinearSpec::AddConstraint(double coeff1, Variable* var1, 116 double coeff2, Variable* var2, OperatorType op, double rightSide) 117 { 118 BList* summands = new BList(2); 119 summands->AddItem(new Summand(coeff1, var1)); 120 summands->AddItem(new Summand(coeff2, var2)); 121 Constraint* c = new Constraint(this, summands, op, rightSide, 122 INFINITY, INFINITY); 123 RemovePresolved(); 124 return c; 125 } 126 127 128 /** 129 * Adds a new hard linear constraint to the specification with three summands. 130 * 131 * @param coeff1 the constraint's first coefficient 132 * @param var1 the constraint's first variable 133 * @param coeff2 the constraint's second coefficient 134 * @param var2 the constraint's second variable 135 * @param coeff3 the constraint's third coefficient 136 * @param var3 the constraint's third variable 137 * @param op the constraint's operand 138 * @param rightSide the constant value on the constraint's right side 139 * @return the new constraint 140 */ 141 Constraint* 142 LinearSpec::AddConstraint(double coeff1, Variable* var1, 143 double coeff2, Variable* var2, double coeff3, Variable* var3, 144 OperatorType op, double rightSide) 145 { 146 BList* summands = new BList(3); 147 summands->AddItem(new Summand(coeff1, var1)); 148 summands->AddItem(new Summand(coeff2, var2)); 149 summands->AddItem(new Summand(coeff3, var3)); 150 Constraint* c = new Constraint(this, summands, op, rightSide, 151 INFINITY, INFINITY); 152 RemovePresolved(); 153 return c; 154 } 155 156 157 /** 158 * Adds a new hard linear constraint to the specification with four summands. 159 * 160 * @param coeff1 the constraint's first coefficient 161 * @param var1 the constraint's first variable 162 * @param coeff2 the constraint's second coefficient 163 * @param var2 the constraint's second variable 164 * @param coeff3 the constraint's third coefficient 165 * @param var3 the constraint's third variable 166 * @param coeff4 the constraint's fourth coefficient 167 * @param var4 the constraint's fourth variable 168 * @param op the constraint's operand 169 * @param rightSide the constant value on the constraint's right side 170 * @return the new constraint 171 */ 172 Constraint* 173 LinearSpec::AddConstraint(double coeff1, Variable* var1, 174 double coeff2, Variable* var2, double coeff3, Variable* var3, 175 double coeff4, Variable* var4, OperatorType op, double rightSide) 176 { 177 BList* summands = new BList(3); 178 summands->AddItem(new Summand(coeff1, var1)); 179 summands->AddItem(new Summand(coeff2, var2)); 180 summands->AddItem(new Summand(coeff3, var3)); 181 summands->AddItem(new Summand(coeff4, var4)); 182 Constraint* c = new Constraint(this, summands, op, rightSide, 183 INFINITY, INFINITY); 184 RemovePresolved(); 185 return c; 186 } 187 188 189 /** 190 * Adds a new soft linear constraint to the specification. 191 * i.e. a constraint that does not always have to be satisfied. 192 * 193 * @param coeffs the constraint's coefficients 194 * @param vars the constraint's variables 195 * @param op the constraint's operand 196 * @param rightSide the constant value on the constraint's right side 197 * @param penaltyNeg the coefficient penalizing negative deviations from the exact solution 198 * @param penaltyPos the coefficient penalizing positive deviations from the exact solution 199 */ 200 Constraint* 201 LinearSpec::AddConstraint(BList* summands, OperatorType op, 202 double rightSide, double penaltyNeg, double penaltyPos) 203 { 204 Constraint* c = new Constraint(this, summands, op, rightSide, 205 penaltyNeg, penaltyPos); 206 RemovePresolved(); 207 return c; 208 } 209 210 211 /** 212 * Adds a new soft linear constraint to the specification with a single summand. 213 * 214 * @param coeff1 the constraint's first coefficient 215 * @param var1 the constraint's first variable 216 * @param op the constraint's operand 217 * @param rightSide the constant value on the constraint's right side 218 * @param penaltyNeg the coefficient penalizing negative deviations from the exact solution 219 * @param penaltyPos the coefficient penalizing positive deviations from the exact solution 220 */ 221 Constraint* 222 LinearSpec::AddConstraint(double coeff1, Variable* var1, 223 OperatorType op, double rightSide, double penaltyNeg, double penaltyPos) 224 { 225 BList* summands = new BList(1); 226 summands->AddItem(new Summand(coeff1, var1)); 227 Constraint* c = new Constraint(this, summands, op, rightSide, 228 penaltyNeg, penaltyPos); 229 RemovePresolved(); 230 return c; 231 } 232 233 234 /** 235 * Adds a new soft linear constraint to the specification with two summands. 236 * 237 * @param coeff1 the constraint's first coefficient 238 * @param var1 the constraint's first variable 239 * @param coeff2 the constraint's second coefficient 240 * @param var2 the constraint's second variable 241 * @param op the constraint's operand 242 * @param rightSide the constant value on the constraint's right side 243 * @param penaltyNeg the coefficient penalizing negative deviations from the exact solution 244 * @param penaltyPos the coefficient penalizing positive deviations from the exact solution 245 */ 246 Constraint* 247 LinearSpec::AddConstraint(double coeff1, Variable* var1, 248 double coeff2, Variable* var2, OperatorType op, double rightSide, 249 double penaltyNeg, double penaltyPos) 250 { 251 BList* summands = new BList(2); 252 summands->AddItem(new Summand(coeff1, var1)); 253 summands->AddItem(new Summand(coeff2, var2)); 254 Constraint* c = new Constraint(this, summands, op, rightSide, 255 penaltyNeg, penaltyPos); 256 RemovePresolved(); 257 return c; 258 } 259 260 261 /** 262 * Adds a new soft linear constraint to the specification with three summands. 263 * 264 * @param coeff1 the constraint's first coefficient 265 * @param var1 the constraint's first variable 266 * @param coeff2 the constraint's second coefficient 267 * @param var2 the constraint's second variable 268 * @param coeff3 the constraint's third coefficient 269 * @param var3 the constraint's third variable 270 * @param op the constraint's operand 271 * @param rightSide the constant value on the constraint's right side 272 * @param penaltyNeg the coefficient penalizing negative deviations from the exact solution 273 * @param penaltyPos the coefficient penalizing positive deviations from the exact solution 274 */ 275 Constraint* 276 LinearSpec::AddConstraint(double coeff1, Variable* var1, 277 double coeff2, Variable* var2, double coeff3, Variable* var3, 278 OperatorType op, double rightSide, double penaltyNeg, double penaltyPos) 279 { 280 BList* summands = new BList(2); 281 summands->AddItem(new Summand(coeff1, var1)); 282 summands->AddItem(new Summand(coeff2, var2)); 283 summands->AddItem(new Summand(coeff3, var3)); 284 Constraint* c = new Constraint(this, summands, op, rightSide, 285 penaltyNeg, penaltyPos); 286 RemovePresolved(); 287 return c; 288 } 289 290 291 /** 292 * Adds a new soft linear constraint to the specification with four summands. 293 * 294 * @param coeff1 the constraint's first coefficient 295 * @param var1 the constraint's first variable 296 * @param coeff2 the constraint's second coefficient 297 * @param var2 the constraint's second variable 298 * @param coeff3 the constraint's third coefficient 299 * @param var3 the constraint's third variable 300 * @param coeff4 the constraint's fourth coefficient 301 * @param var4 the constraint's fourth variable 302 * @param op the constraint's operand 303 * @param rightSide the constant value on the constraint's right side 304 * @param penaltyNeg the coefficient penalizing negative deviations from the exact solution 305 * @param penaltyPos the coefficient penalizing positive deviations from the exact solution 306 */ 307 Constraint* 308 LinearSpec::AddConstraint(double coeff1, Variable* var1, 309 double coeff2, Variable* var2, double coeff3, Variable* var3, 310 double coeff4, Variable* var4, OperatorType op, double rightSide, 311 double penaltyNeg, double penaltyPos) 312 { 313 BList* summands = new BList(2); 314 summands->AddItem(new Summand(coeff1, var1)); 315 summands->AddItem(new Summand(coeff2, var2)); 316 summands->AddItem(new Summand(coeff3, var3)); 317 summands->AddItem(new Summand(coeff4, var4)); 318 Constraint* c = new Constraint(this, summands, op, rightSide, 319 penaltyNeg, penaltyPos); 320 RemovePresolved(); 321 return c; 322 } 323 324 325 /** 326 * Adds a new penalty function to the specification. 327 * 328 * @param var the penalty function's variable 329 * @param xs the penalty function's sampling points 330 * @param gs the penalty function's gradients 331 * @return the new penalty function 332 */ 333 PenaltyFunction* 334 LinearSpec::AddPenaltyFunction(Variable* var, BList* xs, BList* gs) 335 { 336 return new PenaltyFunction(this, var, xs, gs); 337 } 338 339 340 /** 341 * Gets the objective function. 342 * 343 * @return BList containing the objective function's summands 344 */ 345 BList* 346 LinearSpec::ObjFunction() 347 { 348 return fObjFunction; 349 } 350 351 352 /** 353 * Sets a new objective function. 354 * The old objective function summands are NOT deleted. 355 * 356 * @param summands BList containing the objective function's summands 357 */ 358 void 359 LinearSpec::SetObjFunction(BList* summands) 360 { 361 fObjFunction = summands; 362 UpdateObjFunction(); 363 } 364 365 366 /** 367 * Updates the internal representation of the objective function. 368 * Must be called whenever the summands of the objective function are changed. 369 */ 370 void 371 LinearSpec::UpdateObjFunction() 372 { 373 int32 size = fObjFunction->CountItems(); 374 double coeffs[size]; 375 int varIndexes[size]; 376 Summand* current; 377 for (int32 i = 0; i < size; i++) { 378 current = (Summand*)fObjFunction->ItemAt(i); 379 coeffs[i] = current->Coeff(); 380 varIndexes[i] = current->Var()->Index(); 381 } 382 383 if (!set_obj_fnex(fLP, size, &coeffs[0], &varIndexes[0])) 384 printf("Error in set_obj_fnex."); 385 386 RemovePresolved(); 387 } 388 389 390 /** 391 * Remove a cached presolved model, if existent. 392 * This is automatically done each time after the model has been changed, 393 * to avoid an old cached presolved model getting out of sync. 394 */ 395 void 396 LinearSpec::RemovePresolved() 397 { 398 if (fLpPresolved == NULL) 399 return; 400 delete_lp(fLpPresolved); 401 fLpPresolved = NULL; 402 } 403 404 405 /** 406 * Creates and caches a simplified version of the linear programming problem, 407 * where redundant rows, columns and constraints are removed, 408 * if it has not been created before. 409 * Then, the simplified problem is solved. 410 * 411 * @return the result of the solving attempt 412 */ 413 ResultType 414 LinearSpec::Presolve() 415 { 416 bigtime_t start, end; 417 start = system_time(); 418 419 if (fLpPresolved == NULL) { 420 fLpPresolved = copy_lp(fLP); 421 set_presolve(fLpPresolved, PRESOLVE_ROWS | PRESOLVE_COLS | PRESOLVE_LINDEP, 422 get_presolveloops(fLpPresolved)); 423 } 424 425 fResult = (ResultType)solve(fLpPresolved); 426 fObjectiveValue = get_objective(fLpPresolved); 427 428 if (fResult == OPTIMAL) { 429 int32 size = fVariables->CountItems(); 430 for (int32 i = 0; i < size; i++) { 431 Variable* current = (Variable*)fVariables->ItemAt(i); 432 current->SetValue(get_var_primalresult(fLpPresolved, 433 get_Norig_rows(fLpPresolved) + current->Index())); 434 } 435 } 436 437 end = system_time(); 438 fSolvingTime = (end - start) / 1000.0; 439 440 return fResult; 441 } 442 443 444 /** 445 * Tries to solve the linear programming problem. 446 * If a cached simplified version of the problem exists, it is used instead. 447 * 448 * @return the result of the solving attempt 449 */ 450 ResultType 451 LinearSpec::Solve() 452 { 453 if (fLpPresolved != NULL) 454 return Presolve(); 455 456 bigtime_t start, end; 457 start = system_time(); 458 459 fResult = (ResultType)solve(fLP); 460 fObjectiveValue = get_objective(fLP); 461 462 if (fResult == OPTIMAL) { 463 int32 size = fVariables->CountItems(); 464 double x[size]; 465 if (!get_variables(fLP, &x[0])) 466 printf("Error in get_variables."); 467 468 int32 i = 0; 469 while (i < size) { 470 ((Variable*)fVariables->ItemAt(i))->SetValue(x[i]); 471 i++; 472 } 473 } 474 475 end = system_time(); 476 fSolvingTime = (end - start) / 1000.0; 477 478 return fResult; 479 } 480 481 482 /** 483 * Writes the specification into a text file. 484 * The file will be overwritten if it exists. 485 * 486 * @param fname the file name 487 */ 488 void 489 LinearSpec::Save(char* fname) 490 { 491 write_lp(fLP, fname); 492 } 493 494 495 /** 496 * Gets the number of columns. 497 * 498 * @return the number of columns 499 */ 500 int32 501 LinearSpec::CountColumns() const 502 { 503 return fCountColumns; 504 } 505 506 507 /** 508 * Gets the current optimization. 509 * The default is minimization. 510 * 511 * @return the current optimization 512 */ 513 OptimizationType 514 LinearSpec::Optimization() const 515 { 516 return fOptimization; 517 } 518 519 520 /** 521 * Sets whether the solver should minimize or maximize the objective function. 522 * The default is minimization. 523 * 524 * @param optimization the optimization type 525 */ 526 void 527 LinearSpec::SetOptimization(OptimizationType value) 528 { 529 fOptimization = value; 530 if (fOptimization == MINIMIZE) 531 set_minim(fLP); 532 else 533 set_maxim(fLP); 534 } 535 536 537 /** 538 * Gets the the variables. 539 * 540 * @return the variables 541 */ 542 BList* 543 LinearSpec::Variables() const 544 { 545 return fVariables; 546 } 547 548 549 /** 550 * Gets the constraints. 551 * 552 * @return the constraints 553 */ 554 BList* 555 LinearSpec::Constraints() const 556 { 557 return fConstraints; 558 } 559 560 561 /** 562 * Gets the result type. 563 * 564 * @return the result type 565 */ 566 ResultType 567 LinearSpec::Result() const 568 { 569 return fResult; 570 } 571 572 573 /** 574 * Gets the objective value. 575 * 576 * @return the objective value 577 */ 578 double 579 LinearSpec::ObjectiveValue() const 580 { 581 return fObjectiveValue; 582 } 583 584 585 /** 586 * Gets the solving time. 587 * 588 * @return the solving time 589 */ 590 double 591 LinearSpec::SolvingTime() const 592 { 593 return fSolvingTime; 594 } 595 596 597 BString* 598 LinearSpec::ToBString() 599 { 600 BString* str = new BString(); 601 *str << "LinearSpec " << (int32)this << ":\n"; 602 for (int i = 0; i < fVariables->CountItems(); i++) { 603 Variable* variable = static_cast<Variable*>(fVariables->ItemAt(i)); 604 BString* vStr = variable->ToBString(); 605 *str << *vStr << "=" << (float)variable->Value() << " "; 606 delete vStr; 607 } 608 *str << "\n"; 609 for (int i = 0; i < fConstraints->CountItems(); i++) { 610 Constraint* c = static_cast<Constraint*>(fConstraints->ItemAt(i)); 611 BString* cStr = c->ToBString(); 612 *str << i << ": " << *cStr; 613 delete cStr; 614 *str << "\n"; 615 } 616 *str << "Result="; 617 if (fResult==-1) 618 *str << "ERROR"; 619 else if (fResult==0) 620 *str << "OPTIMAL"; 621 else if (fResult==1) 622 *str << "SUBOPTIMAL"; 623 else if (fResult==2) 624 *str << "INFEASIBLE"; 625 else if (fResult==3) 626 *str << "UNBOUNDED"; 627 else if (fResult==4) 628 *str << "DEGENERATE"; 629 else if (fResult==5) 630 *str << "NUMFAILURE"; 631 else 632 *str << fResult; 633 *str << " SolvingTime=" << (float)fSolvingTime << "ms"; 634 return str; 635 } 636 637 638 const char* 639 LinearSpec::ToString() 640 { 641 BString* str = ToBString(); 642 char* result = (char*) malloc(str->Length() + 1); 643 str->CopyInto(result, 0, str->Length()); 644 delete str; 645 return result; 646 } 647 648