1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */ 7 /* */ 8 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 9 /* you may not use this file except in compliance with the License. */ 10 /* You may obtain a copy of the License at */ 11 /* */ 12 /* http://www.apache.org/licenses/LICENSE-2.0 */ 13 /* */ 14 /* Unless required by applicable law or agreed to in writing, software */ 15 /* distributed under the License is distributed on an "AS IS" BASIS, */ 16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 17 /* See the License for the specific language governing permissions and */ 18 /* limitations under the License. */ 19 /* */ 20 /* You should have received a copy of the Apache-2.0 license */ 21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 /**@file misc_linear.c 26 * @ingroup OTHER_CFILES 27 * @brief miscellaneous methods for linear constraints 28 * @author Jakob Witzig 29 * @author Ambros Gleixner 30 */ 31 32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 33 34 #include <assert.h> 35 #include <string.h> 36 37 #include "scip/def.h" 38 #include "scip/scip.h" 39 #include "scip/pub_misc_linear.h" 40 #include "scip/cons_setppc.h" 41 #include "scip/scipdefplugins.h" 42 43 44 /** returns the right-hand side of an arbitrary SCIP constraint that can be represented as a single linear constraint 45 * 46 * @note The success pointer indicates if the individual contraint handler was able to return the involved values 47 */ 48 SCIP_Real SCIPconsGetRhs( 49 SCIP* scip, /**< SCIP data structure */ 50 SCIP_CONS* cons, /**< constraint for which right-hand side is queried */ 51 SCIP_Bool* success /**< pointer to store whether a valid right-hand side was returned */ 52 ) 53 { 54 SCIP_CONSHDLR* conshdlr; 55 const char* conshdlrname; 56 SCIP_Real rhs; 57 58 assert(scip != NULL); 59 assert(cons != NULL); 60 assert(success != NULL); 61 62 conshdlr = SCIPconsGetHdlr(cons); 63 assert(conshdlr != NULL); 64 conshdlrname = SCIPconshdlrGetName(conshdlr); 65 66 *success = TRUE; 67 rhs = SCIP_INVALID; 68 69 if( strcmp(conshdlrname, "linear") == 0 ) 70 { 71 rhs = SCIPgetRhsLinear(scip, cons); 72 } 73 else if( strcmp(conshdlrname, "setppc") == 0 ) 74 { 75 switch( SCIPgetTypeSetppc(scip, cons) ) 76 { 77 case SCIP_SETPPCTYPE_PARTITIONING: /* fall through intended */ 78 case SCIP_SETPPCTYPE_PACKING: 79 rhs = 1.0; 80 break; 81 82 case SCIP_SETPPCTYPE_COVERING: 83 rhs = SCIPinfinity(scip); 84 break; 85 } 86 } 87 else if( strcmp(conshdlrname, "logicor") == 0 ) 88 { 89 rhs = SCIPinfinity(scip); 90 } 91 else if( strcmp(conshdlrname, "knapsack") == 0 ) 92 { 93 rhs = SCIPgetCapacityKnapsack(scip, cons); 94 } 95 else if( strcmp(conshdlrname, "varbound") == 0 ) 96 { 97 rhs = SCIPgetRhsVarbound(scip, cons); 98 } 99 else 100 { 101 SCIPwarningMessage(scip, "Cannot return rhs for constraint of type <%s>\n", conshdlrname); 102 *success = FALSE; 103 } 104 105 return rhs; 106 } 107 108 /** returns the left-hand side of an arbitrary SCIP constraint that can be represented as a single linear constraint 109 * 110 * @note The success pointer indicates if the individual contraint handler was able to return the involved values 111 */ 112 SCIP_Real SCIPconsGetLhs( 113 SCIP* scip, /**< SCIP data structure */ 114 SCIP_CONS* cons, /**< constraint to get left-hand side for */ 115 SCIP_Bool* success /**< pointer to store whether a valid left-hand side was returned */ 116 ) 117 { 118 SCIP_CONSHDLR* conshdlr; 119 const char* conshdlrname; 120 SCIP_Real lhs; 121 122 assert(scip != NULL); 123 assert(cons != NULL); 124 assert(success != NULL); 125 126 conshdlr = SCIPconsGetHdlr(cons); 127 assert(conshdlr != NULL); 128 conshdlrname = SCIPconshdlrGetName(conshdlr); 129 130 *success = TRUE; 131 lhs = SCIP_INVALID; 132 133 if( strcmp(conshdlrname, "linear") == 0 ) 134 { 135 lhs = SCIPgetLhsLinear(scip, cons); 136 } 137 else if( strcmp(conshdlrname, "setppc") == 0 ) 138 { 139 switch( SCIPgetTypeSetppc(scip, cons) ) 140 { 141 case SCIP_SETPPCTYPE_PARTITIONING: /* fall through intended */ 142 case SCIP_SETPPCTYPE_COVERING: 143 lhs = 1.0; 144 break; 145 146 case SCIP_SETPPCTYPE_PACKING: 147 lhs = -SCIPinfinity(scip); 148 break; 149 } 150 } 151 else if( strcmp(conshdlrname, "logicor") == 0 ) 152 { 153 lhs = 1.0; 154 } 155 else if( strcmp(conshdlrname, "knapsack") == 0 ) 156 { 157 lhs = -SCIPinfinity(scip); 158 } 159 else if( strcmp(conshdlrname, "varbound") == 0 ) 160 { 161 lhs = SCIPgetLhsVarbound(scip, cons); 162 } 163 else 164 { 165 SCIPwarningMessage(scip, "Cannot return lhs for constraint of type <%s>\n", conshdlrname); 166 *success = FALSE; 167 } 168 169 return lhs; 170 } 171 172 /** returns the value array of an arbitrary SCIP constraint that can be represented as a single linear constraint 173 * 174 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref 175 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes. 176 * 177 * @note The success pointer indicates if the individual contraint handler was able to return the involved values 178 */ 179 SCIP_RETCODE SCIPgetConsVals( 180 SCIP* scip, /**< SCIP data structure */ 181 SCIP_CONS* cons, /**< constraint for which the coefficients are wanted */ 182 SCIP_Real* vals, /**< array to store the coefficients of the constraint */ 183 int varssize, /**< available slots in vals array needed to check if the array is large enough */ 184 SCIP_Bool* success /**< pointer to store whether the coefficients are successfully copied */ 185 ) 186 { 187 SCIP_CONSHDLR* conshdlr; 188 const char* conshdlrname; 189 int nvars; 190 int i; 191 192 assert(scip != NULL); 193 assert(cons != NULL); 194 assert(vals != NULL); 195 assert(success != NULL); 196 197 conshdlr = SCIPconsGetHdlr(cons); 198 assert(conshdlr != NULL); 199 200 conshdlrname = SCIPconshdlrGetName(conshdlr); 201 202 *success = TRUE; 203 204 SCIP_CALL( SCIPgetConsNVars(scip, cons, &nvars, success) ); 205 206 if( !(*success) ) 207 { 208 SCIPwarningMessage(scip, "Cannot return value array for constraint of type <%s>\n", conshdlrname); 209 return SCIP_OKAY; 210 } 211 212 if( varssize < nvars ) 213 { 214 SCIPwarningMessage(scip, "Cannot return value array for constraint of type <%s> (insufficient memory provided)\n", conshdlrname); 215 *success = FALSE; 216 return SCIP_OKAY; 217 } 218 219 if( strcmp(conshdlrname, "linear") == 0 ) 220 { 221 SCIP_Real* linvals; 222 223 linvals = SCIPgetValsLinear(scip, cons); 224 assert(linvals != NULL); 225 226 for( i = 0; i < nvars; i++ ) 227 { 228 vals[i] = linvals[i]; 229 } 230 } 231 else if( strcmp(conshdlrname, "setppc") == 0 ) 232 { 233 for( i = 0; i < nvars; i++ ) 234 { 235 vals[i] = 1.0; 236 } 237 } 238 else if( strcmp(conshdlrname, "logicor") == 0 ) 239 { 240 for( i = 0; i < nvars; i++ ) 241 { 242 vals[i] = 1.0; 243 } 244 } 245 else if( strcmp(conshdlrname, "knapsack") == 0 ) 246 { 247 SCIP_Longint* weights; 248 249 weights = SCIPgetWeightsKnapsack(scip, cons); 250 assert(weights != NULL); 251 252 for( i = 0; i < nvars; i++ ) 253 { 254 vals[i] = (SCIP_Real)weights[i]; 255 } 256 } 257 else if( strcmp(conshdlrname, "varbound") == 0 ) 258 { 259 assert(nvars == 2); 260 261 vals[0] = 1.0; 262 vals[1] = SCIPgetVbdcoefVarbound(scip, cons); 263 } 264 else if( strcmp(conshdlrname, "SOS1") == 0 ) 265 { 266 SCIP_Real* weights; 267 268 weights = SCIPgetWeightsSOS1(scip, cons); 269 assert(weights != NULL); 270 271 for( i = 0; i < nvars; i++ ) 272 { 273 vals[i] = weights[i]; 274 } 275 } 276 else if( strcmp(conshdlrname, "SOS2") == 0 ) 277 { 278 SCIP_Real* weights; 279 280 weights = SCIPgetWeightsSOS2(scip, cons); 281 assert(weights != NULL); 282 283 for( i = 0; i < nvars; i++ ) 284 { 285 vals[i] = weights[i]; 286 } 287 } 288 else 289 { 290 SCIPwarningMessage(scip, "Cannot return value array for constraint of type <%s>\n", conshdlrname); 291 *success = FALSE; 292 } 293 294 return SCIP_OKAY; 295 } 296 297 /** returns the dual farkas sol of an arbitrary SCIP constraint that can be represented as a single linear constraint 298 * 299 * @note The success pointer indicates if the individual contraint handler was able to return the dual farkas solution 300 */ 301 void SCIPconsGetDualfarkas( 302 SCIP* scip, /**< SCIP data structure */ 303 SCIP_CONS* cons, /**< constraint to get the dual farkas solution for */ 304 SCIP_Real* dualfarkas, /**< pointer to store the dual farkas solution */ 305 SCIP_Bool* success /**< pointer to store whether the dual farkas solution is successfully returned */ 306 ) 307 { 308 SCIP_CONSHDLR* conshdlr; 309 const char* conshdlrname; 310 311 assert(scip != NULL); 312 assert(cons != NULL); 313 314 conshdlr = SCIPconsGetHdlr(cons); 315 assert(conshdlr != NULL); 316 conshdlrname = SCIPconshdlrGetName(conshdlr); 317 318 *success = TRUE; 319 320 if( strcmp(conshdlrname, "linear") == 0 ) 321 { 322 *dualfarkas = SCIPgetDualfarkasLinear(scip, cons); 323 } 324 else if( strcmp(conshdlrname, "setppc") == 0 ) 325 { 326 *dualfarkas = SCIPgetDualfarkasSetppc(scip, cons); 327 } 328 else if( strcmp(conshdlrname, "logicor") == 0 ) 329 { 330 *dualfarkas = SCIPgetDualfarkasLogicor(scip, cons); 331 } 332 else if( strcmp(conshdlrname, "knapsack") == 0 ) 333 { 334 *dualfarkas = SCIPgetDualfarkasKnapsack(scip, cons); 335 } 336 else if( strcmp(conshdlrname, "varbound") == 0 ) 337 { 338 *dualfarkas = SCIPgetDualfarkasVarbound(scip, cons); 339 } 340 /* these are Benders' specific constraint handlers */ 341 else if( strcmp(conshdlrname, "origbranch") == 0 || strcmp(conshdlrname, "masterbranch") == 0 ) 342 { 343 *dualfarkas = 0.0; 344 } 345 else 346 { 347 SCIPwarningMessage(scip, "Cannot return dual farkas solution for constraint of type <%s>\n", conshdlrname); 348 *dualfarkas = 0.0; 349 *success = FALSE; 350 } 351 } 352 353 /** returns the dual sol of an arbitrary SCIP constraint that can be represented as a single linear constraint 354 * 355 * @note The success pointer indicates if the individual contraint handler was able to return the dual solution 356 */ 357 void SCIPconsGetDualsol( 358 SCIP* scip, /**< SCIP data structure */ 359 SCIP_CONS* cons, /**< constraint to get the dual solution for */ 360 SCIP_Real* dualsol, /**< pointer to store the dual solution */ 361 SCIP_Bool* success /**< pointer to store whether the dual solution is successfully returned */ 362 ) 363 { 364 SCIP_CONSHDLR* conshdlr; 365 const char* conshdlrname; 366 367 assert(scip != NULL); 368 assert(cons != NULL); 369 370 conshdlr = SCIPconsGetHdlr(cons); 371 assert(conshdlr != NULL); 372 conshdlrname = SCIPconshdlrGetName(conshdlr); 373 374 *success = TRUE; 375 376 if( strcmp(conshdlrname, "linear") == 0 ) 377 { 378 *dualsol = SCIPgetDualsolLinear(scip, cons); 379 } 380 else if( strcmp(conshdlrname, "setppc") == 0 ) 381 { 382 *dualsol = SCIPgetDualsolSetppc(scip, cons); 383 } 384 else if( strcmp(conshdlrname, "logicor") == 0 ) 385 { 386 *dualsol = SCIPgetDualsolLogicor(scip, cons); 387 } 388 else if( strcmp(conshdlrname, "knapsack") == 0 ) 389 { 390 *dualsol = SCIPgetDualsolKnapsack(scip, cons); 391 } 392 else if( strcmp(conshdlrname, "varbound") == 0 ) 393 { 394 *dualsol = SCIPgetDualsolVarbound(scip, cons); 395 } 396 /* these are Benders' specific constraint handlers */ 397 else if( strcmp(conshdlrname, "origbranch") == 0 || strcmp(conshdlrname, "masterbranch") == 0 ) 398 { 399 *dualsol = 0.0; 400 } 401 else 402 { 403 SCIPwarningMessage(scip, "Cannot return dual solution for constraint of type <%s>\n", conshdlrname); 404 *dualsol = 0.0; 405 *success = FALSE; 406 } 407 } 408 409 /** returns the row of an arbitrary SCIP constraint that can be represented as a single linear constraint 410 * or NULL of no row is available 411 */ 412 SCIP_ROW* SCIPconsGetRow( 413 SCIP* scip, /**< SCIP data structure */ 414 SCIP_CONS* cons /**< constraint for which row is queried */ 415 ) 416 { 417 SCIP_CONSHDLR* conshdlr; 418 const char* conshdlrname; 419 420 assert(scip != NULL); 421 assert(cons != NULL); 422 423 conshdlr = SCIPconsGetHdlr(cons); 424 assert(conshdlr != NULL); 425 conshdlrname = SCIPconshdlrGetName(conshdlr); 426 427 if( strcmp(conshdlrname, "linear") == 0 ) 428 { 429 return SCIPgetRowLinear(scip, cons); 430 } 431 else if( strcmp(conshdlrname, "setppc") == 0 ) 432 { 433 return SCIPgetRowSetppc(scip, cons); 434 } 435 else if( strcmp(conshdlrname, "logicor") == 0 ) 436 { 437 return SCIPgetRowLogicor(scip, cons); 438 } 439 else if( strcmp(conshdlrname, "knapsack") == 0 ) 440 { 441 return SCIPgetRowKnapsack(scip, cons); 442 } 443 else if( strcmp(conshdlrname, "varbound") == 0 ) 444 { 445 return SCIPgetRowVarbound(scip, cons); 446 } 447 448 return NULL; 449 } 450 451 /** adds the given variable to the input constraint. 452 * If the constraint is setppc or logicor the value is ignored. If the constraint is knapsack, then the value is 453 * converted to an int. A warning is passed if the SCIP_Real is not an integer. 454 * TODO: Allow val to be a pointer. 455 */ 456 SCIP_RETCODE SCIPconsAddCoef( 457 SCIP* scip, /**< SCIP data structure */ 458 SCIP_CONS* cons, /**< constraint for which row is queried */ 459 SCIP_VAR* var, /**< variable of the constraint entry */ 460 SCIP_Real val /**< the coefficient of the constraint entry */ 461 ) 462 { 463 SCIP_CONSHDLR* conshdlr; 464 const char* conshdlrname; 465 466 assert(scip != NULL); 467 assert(cons != NULL); 468 assert(var != NULL); 469 470 conshdlr = SCIPconsGetHdlr(cons); 471 assert(conshdlr != NULL); 472 conshdlrname = SCIPconshdlrGetName(conshdlr); 473 474 if( strcmp(conshdlrname, "linear") == 0 ) 475 { 476 SCIP_CALL( SCIPaddCoefLinear(scip, cons, var, val) ); 477 } 478 else if( strcmp(conshdlrname, "setppc") == 0 ) 479 { 480 SCIP_CALL( SCIPaddCoefSetppc(scip, cons, var) ); 481 } 482 else if( strcmp(conshdlrname, "logicor") == 0 ) 483 { 484 SCIP_CALL( SCIPaddCoefLogicor(scip, cons, var) ); 485 } 486 else if( strcmp(conshdlrname, "knapsack") == 0 ) 487 { 488 if( !SCIPisIntegral(scip, val) ) 489 { 490 SCIPerrorMessage("The coefficient value %g is not valid. " 491 "The coefficient for a knapsack constraint must be integer.\n", val); 492 return SCIP_ERROR; 493 } 494 495 SCIP_CALL( SCIPaddCoefKnapsack(scip, cons, var, (SCIP_Longint)val) ); 496 } 497 else if( strcmp(conshdlrname, "varbound") == 0 ) 498 { 499 SCIPerrorMessage("Sorry, can't add coefficient for constraint of type <%s>\n", conshdlrname); 500 return SCIP_ERROR; 501 } 502 else 503 { 504 SCIPerrorMessage("Sorry, can't add coefficient for constraint of type <%s>\n", conshdlrname); 505 return SCIP_ERROR; 506 } 507 508 return SCIP_OKAY; 509 } 510