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