1"""Python-MIP interface to the COIN-OR Branch-and-Cut solver CBC""" 2 3import logging 4from typing import Dict, List, Tuple, Optional, Union 5from sys import platform, maxsize 6from os.path import dirname, isfile, exists 7import os 8import multiprocessing as multip 9import numbers 10from cffi import FFI 11from mip.model import xsum 12import mip 13from mip.lists import EmptyVarSol, EmptyRowSol 14from mip.exceptions import ( 15 ParameterNotAvailable, 16 InvalidParameter, 17 MipBaseException, 18) 19from mip import ( 20 Model, 21 Var, 22 Constr, 23 Column, 24 LinExpr, 25 VConstrList, 26 VVarList, 27 Solver, 28 MAXIMIZE, 29 SearchEmphasis, 30 CONTINUOUS, 31 BINARY, 32 INTEGER, 33 MINIMIZE, 34 EQUAL, 35 LESS_OR_EQUAL, 36 GREATER_OR_EQUAL, 37 OptimizationStatus, 38 LP_Method, 39 CutType, 40 CutPool, 41) 42 43logger = logging.getLogger(__name__) 44warningMessages = 0 45 46ffi = FFI() 47has_cbc = False 48os_is_64_bit = maxsize > 2 ** 32 49INF = float("inf") 50cut_idx = 0 51 52# for variables and rows 53MAX_NAME_SIZE = 512 54 55DEF_PUMPP = 30 56 57try: 58 pathmip = dirname(mip.__file__) 59 pathlib = os.path.join(pathmip, "libraries") 60 libfile = "" 61 # if user wants to force the loading of an specific CBC library 62 # (for debugging purposes, for example) 63 if "PMIP_CBC_LIBRARY" in os.environ: 64 libfile = os.environ["PMIP_CBC_LIBRARY"] 65 pathlib = dirname(libfile) 66 67 if platform.lower().startswith("win"): 68 if pathlib not in os.environ["PATH"]: 69 os.environ["PATH"] += ";" + pathlib 70 else: 71 if "linux" in platform.lower(): 72 if os_is_64_bit: 73 pathlibe = os.path.join(pathlib, "lin64") 74 libfile = os.path.join(pathlibe, "libCbcSolver.so") 75 if not exists(libfile): 76 pathlibe = pathlib 77 libfile = os.path.join(pathlib, "cbc-c-linux-x86-64.so") 78 pathlib = pathlibe 79 else: 80 raise NotImplementedError("Linux 32 bits platform not supported.") 81 elif platform.lower().startswith("win"): 82 if os_is_64_bit: 83 pathlibe = os.path.join(pathlib, "win64") 84 libfile = os.path.join(pathlibe, "libCbcSolver-0.dll") 85 if exists(libfile): 86 if pathlibe not in os.environ["PATH"]: 87 os.environ["PATH"] = pathlibe + ";" + os.environ["PATH"] 88 else: 89 pathlibe = pathlib 90 libfile = os.path.join(pathlibe, "cbc-c-windows-x86-64.dll") 91 if pathlibe not in os.environ["PATH"]: 92 os.environ["PATH"] = pathlibe + ";" + os.environ["PATH"] 93 pathlib = pathlibe 94 95 else: 96 raise NotImplementedError("Win32 platform not supported.") 97 elif platform.lower().startswith("darwin") or platform.lower().startswith( 98 "macos" 99 ): 100 if os_is_64_bit: 101 libfile = os.path.join(pathlib, "cbc-c-darwin-x86-64.dylib") 102 if not libfile: 103 raise NotImplementedError("You operating system/platform is not supported") 104 old_dir = os.getcwd() 105 os.chdir(pathlib) 106 cbclib = ffi.dlopen(libfile) 107 os.chdir(old_dir) 108 has_cbc = True 109except Exception as e: 110 logger.error("An error occurred while loading the CBC library:\t " "{}\n".format(e)) 111 has_cbc = False 112 113if has_cbc: 114 ffi.cdef( 115 """ 116 typedef int(*cbc_progress_callback)(void *model, 117 int phase, 118 int step, 119 const char *phaseName, 120 double seconds, 121 double lb, 122 double ub, 123 int nint, 124 int *vecint, 125 void *cbData 126 ); 127 128 typedef void(*cbc_callback)(void *model, int msgno, int ndouble, 129 const double *dvec, int nint, const int *ivec, 130 int nchar, char **cvec); 131 132 typedef void(*cbc_cut_callback)(void *osiSolver, void *osiCuts, void *appdata, int level, int npass); 133 134 typedef int (*cbc_incumbent_callback)(void *cbcModel, 135 double obj, int nz, 136 char **vnames, double *x, void *appData); 137 138 typedef void Cbc_Model; 139 140 void *Cbc_newModel(); 141 142 void Cbc_readLp(Cbc_Model *model, const char *file); 143 144 int Cbc_readBasis(Cbc_Model *model, const char *filename); 145 146 int Cbc_writeBasis(Cbc_Model *model, const char *filename, char 147 writeValues, int formatType); 148 149 void Cbc_readMps(Cbc_Model *model, const char *file); 150 151 char Cbc_supportsGzip(); 152 153 char Cbc_supportsBzip2(); 154 155 void Cbc_writeLp(Cbc_Model *model, const char *file); 156 157 void Cbc_writeMps(Cbc_Model *model, const char *file); 158 159 int Cbc_getNumCols(Cbc_Model *model); 160 161 int Cbc_getNumRows(Cbc_Model *model); 162 163 int Cbc_getNumIntegers(Cbc_Model *model); 164 165 int Cbc_getNumElements(Cbc_Model *model); 166 167 int Cbc_getRowNz(Cbc_Model *model, int row); 168 169 int *Cbc_getRowIndices(Cbc_Model *model, int row); 170 171 double *Cbc_getRowCoeffs(Cbc_Model *model, int row); 172 173 double Cbc_getRowRHS(Cbc_Model *model, int row); 174 175 void Cbc_setRowRHS(Cbc_Model *model, int row, double rhs); 176 177 char Cbc_getRowSense(Cbc_Model *model, int row); 178 179 const double *Cbc_getRowActivity(Cbc_Model *model); 180 181 const double *Cbc_getRowSlack(Cbc_Model *model); 182 183 int Cbc_getColNz(Cbc_Model *model, int col); 184 185 int *Cbc_getColIndices(Cbc_Model *model, int col); 186 187 double *Cbc_getColCoeffs(Cbc_Model *model, int col); 188 189 void Cbc_addCol(Cbc_Model *model, const char *name, 190 double lb, double ub, double obj, char isInteger, 191 int nz, int *rows, double *coefs); 192 193 void Cbc_addRow(Cbc_Model *model, const char *name, int nz, 194 const int *cols, const double *coefs, char sense, double rhs); 195 196 void Cbc_addLazyConstraint(Cbc_Model *model, int nz, 197 int *cols, double *coefs, char sense, double rhs); 198 199 void Cbc_addSOS(Cbc_Model *model, int numRows, const int *rowStarts, 200 const int *colIndices, const double *weights, const int type); 201 202 int Cbc_numberSOS(Cbc_Model *model); 203 204 void Cbc_setObjCoeff(Cbc_Model *model, int index, double value); 205 206 double Cbc_getObjSense(Cbc_Model *model); 207 208 const double *Cbc_getObjCoefficients(Cbc_Model *model); 209 210 const double *Cbc_getColSolution(Cbc_Model *model); 211 212 const double *Cbc_getReducedCost(Cbc_Model *model); 213 214 double *Cbc_bestSolution(Cbc_Model *model); 215 216 int Cbc_numberSavedSolutions(Cbc_Model *model); 217 218 const double *Cbc_savedSolution(Cbc_Model *model, int whichSol); 219 220 double Cbc_savedSolutionObj(Cbc_Model *model, int whichSol); 221 222 double Cbc_getObjValue(Cbc_Model *model); 223 224 void Cbc_setObjSense(Cbc_Model *model, double sense); 225 226 int Cbc_isProvenOptimal(Cbc_Model *model); 227 228 int Cbc_isProvenInfeasible(Cbc_Model *model); 229 230 int Cbc_isContinuousUnbounded(Cbc_Model *model); 231 232 int Cbc_isAbandoned(Cbc_Model *model); 233 234 const double *Cbc_getColLower(Cbc_Model *model); 235 236 const double *Cbc_getColUpper(Cbc_Model *model); 237 238 double Cbc_getColObj(Cbc_Model *model, int colIdx); 239 240 double Cbc_getColLB(Cbc_Model *model, int colIdx); 241 242 double Cbc_getColUB(Cbc_Model *model, int colIdx); 243 244 void Cbc_setColLower(Cbc_Model *model, int index, double value); 245 246 void Cbc_setColUpper(Cbc_Model *model, int index, double value); 247 248 int Cbc_isInteger(Cbc_Model *model, int i); 249 250 void Cbc_getColName(Cbc_Model *model, 251 int iColumn, char *name, size_t maxLength); 252 253 void Cbc_getRowName(Cbc_Model *model, 254 int iRow, char *name, size_t maxLength); 255 256 void Cbc_setContinuous(Cbc_Model *model, int iColumn); 257 258 void Cbc_setInteger(Cbc_Model *model, int iColumn); 259 260 /*! Integer parameters */ 261 enum IntParam { 262 INT_PARAM_PERT_VALUE = 0, /*! Method of perturbation, -5000 to 102, default 50 */ 263 INT_PARAM_IDIOT = 1, /*! Parameter of the "idiot" method to try to produce an initial feasible basis. -1 let the solver decide if this should be applied; 0 deactivates it and >0 sets number of passes. */ 264 INT_PARAM_STRONG_BRANCHING = 2, /*! Number of variables to be evaluated in strong branching. */ 265 INT_PARAM_CUT_DEPTH = 3, /*! Sets the application of cuts to every depth multiple of this value. -1, the default value, let the solve decide. */ 266 INT_PARAM_MAX_NODES = 4, /*! Maximum number of nodes to be explored in the search tree */ 267 INT_PARAM_NUMBER_BEFORE = 5, /*! Number of branches before trusting pseudocodes computed in strong branching. */ 268 INT_PARAM_FPUMP_ITS = 6, /*! Maximum number of iterations in the feasibility pump method. */ 269 INT_PARAM_MAX_SOLS = 7, /*! Maximum number of solutions generated during the search. Stops the search when this number of solutions is found. */ 270 INT_PARAM_CUT_PASS_IN_TREE = 8, /*! Maximum number of cuts passes in the search tree (with the exception of the root node). Default 1. */ 271 INT_PARAM_THREADS = 9, /*! Number of threads that can be used in the branch-and-bound method.*/ 272 INT_PARAM_CUT_PASS = 10, /*! Number of cut passes in the root node. Default -1, solver decides */ 273 INT_PARAM_LOG_LEVEL = 11, /*! Verbosity level, from 0 to 2 */ 274 INT_PARAM_MAX_SAVED_SOLS = 12, /*! Size of the pool to save the best solutions found during the search. */ 275 INT_PARAM_MULTIPLE_ROOTS = 13, /*! Multiple root passes to get additional cuts and solutions. */ 276 INT_PARAM_ROUND_INT_VARS = 14, /*! If integer variables should be round to remove small infeasibilities. This can increase the overall amount of infeasibilities in problems with both continuous and integer variables */ 277 INT_PARAM_RANDOM_SEED = 15, /*! When solving LP and MIP, randomization is used to break ties in some decisions. This changes the random seed so that multiple executions can produce different results */ 278 INT_PARAM_ELAPSED_TIME = 16, /*! When =1 use elapsed (wallclock) time, otherwise use CPU time */ 279 INT_PARAM_CGRAPH = 17, /*! Conflict graph: controls if the conflict graph is created or not. 0: off, 1: auto, 2: on 3: fast weaker clique sep */ 280 INT_PARAM_CLIQUE_MERGING = 18, /*! Clique merging options: 0: off , 1 auto , 2 before solving LP, 3 after solving LP and pre-processing */ 281 INT_PARAM_MAX_NODES_NOT_IMPROV_FS = 19, /*! Maximum number of nodes processed without improving best solution, after a feasible solution is found */ 282 }; 283 #define N_INT_PARAMS 20 284 285 void Cbc_setIntParam(Cbc_Model *model, enum IntParam which, const int val); 286 287 /*! Double parameters 288 * */ 289 enum DblParam { 290 DBL_PARAM_PRIMAL_TOL = 0, /*! Tollerance to consider a solution feasible in the linear programming solver. */ 291 DBL_PARAM_DUAL_TOL = 1, /*! Tollerance for a solution to be considered optimal in the linear programming solver. */ 292 DBL_PARAM_ZERO_TOL = 2, /*! Coefficients less that this value will be ignored when reading instances */ 293 DBL_PARAM_INT_TOL = 3, /*! Maximum allowed distance from integer value for a variable to be considered integral */ 294 DBL_PARAM_PRESOLVE_TOL = 4, /*! Tollerance used in the presolver, should be increased if the pre-solver is declaring infeasible a feasible problem */ 295 DBL_PARAM_TIME_LIMIT = 5, /*! Time limit in seconds */ 296 DBL_PARAM_PSI = 6, /*! Two dimensional princing factor in the Positive Edge pivot strategy. */ 297 DBL_PARAM_CUTOFF = 7, /*! Only search for solutions with cost less-or-equal to this value. */ 298 DBL_PARAM_ALLOWABLE_GAP = 8, /*! Allowable gap between the lower and upper bound to conclude the search */ 299 DBL_PARAM_GAP_RATIO = 9, /*! Stops the search when the difference between the upper and lower bound is less than this fraction of the larger value */ 300 DBL_PARAM_MAX_SECS_NOT_IMPROV_FS = 10, /*! Maximum processing time without improving best solution, after a feasible solution is found */ 301 }; 302 #define N_DBL_PARAMS 11 303 304 void Cbc_setDblParam(Cbc_Model *model, enum DblParam which, const double val); 305 306 void Cbc_setParameter(Cbc_Model *model, const char *name, 307 const char *value); 308 309 double Cbc_getCutoff(Cbc_Model *model); 310 311 void Cbc_setCutoff(Cbc_Model *model, double cutoff); 312 313 double Cbc_getAllowableGap(Cbc_Model *model); 314 315 void Cbc_setAllowableGap(Cbc_Model *model, double allowedGap); 316 317 double Cbc_getAllowableFractionGap(Cbc_Model *model); 318 319 void Cbc_setAllowableFractionGap(Cbc_Model *model, 320 double allowedFracionGap); 321 322 double Cbc_getAllowablePercentageGap(Cbc_Model *model); 323 324 void Cbc_setAllowablePercentageGap(Cbc_Model *model, 325 double allowedPercentageGap); 326 327 double Cbc_getMaximumSeconds(Cbc_Model *model); 328 329 void Cbc_setMaximumSeconds(Cbc_Model *model, double maxSeconds); 330 331 int Cbc_getMaximumNodes(Cbc_Model *model); 332 333 void Cbc_setMaximumNodes(Cbc_Model *model, int maxNodes); 334 335 int Cbc_getMaximumSolutions(Cbc_Model *model); 336 337 void Cbc_setMaximumSolutions(Cbc_Model *model, int maxSolutions); 338 339 int Cbc_getLogLevel(Cbc_Model *model); 340 341 void Cbc_setLogLevel(Cbc_Model *model, int logLevel); 342 343 double Cbc_getBestPossibleObjValue(Cbc_Model *model); 344 345 void Cbc_setMIPStart(Cbc_Model *model, int count, 346 const char **colNames, const double colValues[]); 347 348 void Cbc_setMIPStartI(Cbc_Model *model, int count, const int colIdxs[], 349 const double colValues[]); 350 351 enum LPMethod { 352 LPM_Auto = 0, /*! Solver will decide automatically which method to use */ 353 LPM_Dual = 1, /*! Dual simplex */ 354 LPM_Primal = 2, /*! Primal simplex */ 355 LPM_Barrier = 3 /*! The barrier algorithm. */ 356 }; 357 358 void 359 Cbc_setLPmethod(Cbc_Model *model, enum LPMethod lpm ); 360 361 void Cbc_updateConflictGraph( Cbc_Model *model ); 362 363 const void *Cbc_conflictGraph( Cbc_Model *model ); 364 365 int Cbc_solve(Cbc_Model *model); 366 367 int Cbc_solveLinearProgram(Cbc_Model *model); 368 369 /*! Type of cutting plane */ 370 enum CutType { 371 CT_Probing = 0, /*! Cuts generated evaluating the impact of fixing bounds for integer variables */ 372 CT_Gomory = 1, /*! Gomory cuts obtained from the tableau, implemented by John Forrest */ 373 CT_GMI = 2, /*! Gomory cuts obtained from the tableau, implementation from Giacomo Nannicini focusing on safer cuts */ 374 CT_LaGomory = 3, /*! Additional gomory cuts, simplification of 'A Relax-and-Cut Framework for Gomory's Mixed-Integer Cuts' by Matteo Fischetti & Domenico Salvagnin */ 375 CT_RedSplit = 4, /*! Reduce and split cuts, implemented by Francois Margot */ 376 CT_RedSplitG = 5, /*! Reduce and split cuts, implemented by Giacomo Nannicini */ 377 CT_FlowCover = 6, /*! Flow cover cuts */ 378 CT_MIR = 7, /*! Mixed-integer rounding cuts */ 379 CT_TwoMIR = 8, /*! Two-phase Mixed-integer rounding cuts */ 380 CT_LaTwoMIR = 9, /*! Lagrangean relaxation for two-phase Mixed-integer rounding cuts, as in CT_LaGomory */ 381 CT_LiftAndProject = 10, /*! Lift and project cuts */ 382 CT_ResidualCapacity = 11, /*! Residual capacity cuts */ 383 CT_ZeroHalf = 12, /*! Zero-half cuts */ 384 CT_Clique = 13, /*! Clique cuts */ 385 CT_OddWheel = 14, /*! Lifted odd-hole inequalities */ 386 CT_KnapsackCover = 15, /*! Knapsack cover cuts */ 387 }; 388 389 void Cbc_generateCuts( Cbc_Model *cbcModel, enum CutType ct, void *oc, int depth, int pass ); 390 391 void Cbc_strengthenPacking(Cbc_Model *model); 392 393 void Cbc_strengthenPackingRows(Cbc_Model *model, size_t n, const size_t rows[]); 394 395 void *Cbc_getSolverPtr(Cbc_Model *model); 396 397 void *Cbc_deleteModel(Cbc_Model *model); 398 399 int Osi_getNumIntegers( void *osi ); 400 401 const double *Osi_getReducedCost( void *osi ); 402 403 const double *Osi_getObjCoefficients(); 404 405 double Osi_getObjSense(); 406 407 void *Osi_newSolver(); 408 409 void Osi_deleteSolver( void *osi ); 410 411 void Osi_initialSolve(void *osi); 412 413 void Osi_resolve(void *osi); 414 415 void Osi_branchAndBound(void *osi); 416 417 char Osi_isAbandoned(void *osi); 418 419 char Osi_isProvenOptimal(void *osi); 420 421 char Osi_isProvenPrimalInfeasible(void *osi); 422 423 char Osi_isProvenDualInfeasible(void *osi); 424 425 char Osi_isPrimalObjectiveLimitReached(void *osi); 426 427 char Osi_isDualObjectiveLimitReached(void *osi); 428 429 char Osi_isIterationLimitReached(void *osi); 430 431 double Osi_getObjValue( void *osi ); 432 433 void Osi_setColUpper (void *osi, int elementIndex, double ub); 434 435 void Osi_setColLower(void *osi, int elementIndex, double lb); 436 437 int Osi_getNumCols( void *osi ); 438 439 void Osi_getColName( void *osi, int i, char *name, int maxLen ); 440 441 const double *Osi_getColLower( void *osi ); 442 443 const double *Osi_getColUpper( void *osi ); 444 445 int Osi_isInteger( void *osi, int col ); 446 447 int Osi_getNumRows( void *osi ); 448 449 int Osi_getRowNz(void *osi, int row); 450 451 const int *Osi_getRowIndices(void *osi, int row); 452 453 const double *Osi_getRowCoeffs(void *osi, int row); 454 455 double Osi_getRowRHS(void *osi, int row); 456 457 char Osi_getRowSense(void *osi, int row); 458 459 void Osi_setObjCoef(void *osi, int index, double obj); 460 461 void Osi_setObjSense(void *osi, double sense); 462 463 const double *Osi_getColSolution(void *osi); 464 465 void *OsiCuts_new(); 466 467 void OsiCuts_addRowCut( void *osiCuts, int nz, const int *idx, 468 const double *coef, char sense, double rhs ); 469 470 void OsiCuts_addGlobalRowCut( void *osiCuts, int nz, const int *idx, 471 const double *coef, char sense, double rhs ); 472 473 int OsiCuts_sizeRowCuts( void *osiCuts ); 474 475 int OsiCuts_nzRowCut( void *osiCuts, int iRowCut ); 476 477 const int * OsiCuts_idxRowCut( void *osiCuts, int iRowCut ); 478 479 const double *OsiCuts_coefRowCut( void *osiCuts, int iRowCut ); 480 481 double OsiCuts_rhsRowCut( void *osiCuts, int iRowCut ); 482 483 char OsiCuts_senseRowCut( void *osiCuts, int iRowCut ); 484 485 void OsiCuts_delete( void *osiCuts ); 486 487 void Osi_addCol(void *osi, const char *name, double lb, double ub, 488 double obj, char isInteger, int nz, int *rows, double *coefs); 489 490 void Osi_addRow(void *osi, const char *name, int nz, 491 const int *cols, const double *coefs, char sense, double rhs); 492 493 void Cbc_deleteRows(Cbc_Model *model, int numRows, const int rows[]); 494 495 void Cbc_deleteCols(Cbc_Model *model, int numCols, const int cols[]); 496 497 void Cbc_storeNameIndexes(Cbc_Model *model, char _store); 498 499 int Cbc_getColNameIndex(Cbc_Model *model, const char *name); 500 501 int Cbc_getRowNameIndex(Cbc_Model *model, const char *name); 502 503 void Cbc_problemName(Cbc_Model *model, int maxNumberCharacters, 504 char *array); 505 506 int Cbc_setProblemName(Cbc_Model *model, const char *array); 507 508 double Cbc_getPrimalTolerance(Cbc_Model *model); 509 510 void Cbc_setPrimalTolerance(Cbc_Model *model, double tol); 511 512 double Cbc_getDualTolerance(Cbc_Model *model); 513 514 void Cbc_setDualTolerance(Cbc_Model *model, double tol); 515 516 void Cbc_addCutCallback(Cbc_Model *model, cbc_cut_callback cutcb, 517 const char *name, void *appData, int howOften, char atSolution ); 518 519 void Cbc_addIncCallback( 520 void *model, cbc_incumbent_callback inccb, 521 void *appData ); 522 523 void Cbc_registerCallBack(Cbc_Model *model, 524 cbc_callback userCallBack); 525 526 void Cbc_addProgrCallback(void *model, 527 cbc_progress_callback prgcbc, void *appData); 528 529 void Cbc_clearCallBack(Cbc_Model *model); 530 531 const double *Cbc_getRowPrice(Cbc_Model *model); 532 533 const double *Osi_getRowPrice(void *osi); 534 535 double Osi_getIntegerTolerance(void *osi); 536 537 void Osi_checkCGraph( void *osi ); 538 539 const void * Osi_CGraph( void *osi ); 540 541 size_t CG_nodes( void *cgraph ); 542 543 char CG_conflicting( void *cgraph, int n1, int n2 ); 544 545 double CG_density( void *cgraph ); 546 547 typedef struct { 548 size_t n; 549 const size_t *neigh; 550 } CGNeighbors; 551 552 CGNeighbors CG_conflictingNodes(Cbc_Model *model, void *cgraph, size_t node); 553 554 void Cbc_computeFeatures(Cbc_Model *model, double *features); 555 556 int Cbc_nFeatures(); 557 558 const char *Cbc_featureName(int i); 559 """ 560 ) 561 562CHAR_ONE = "{}".format(chr(1)).encode("utf-8") 563CHAR_ZERO = "\0".encode("utf-8") 564 565 566DBL_PARAM_PRIMAL_TOL = 0 567DBL_PARAM_DUAL_TOL = 1 568DBL_PARAM_ZERO_TOL = 2 569DBL_PARAM_INT_TOL = 3 570DBL_PARAM_PRESOLVE_TOL = 4 571DBL_PARAM_TIME_LIMIT = 5 572DBL_PARAM_PSI = 6 573DBL_PARAM_CUTOFF = 7 574DBL_PARAM_ALLOWABLE_GAP = 8 575DBL_PARAM_GAP_RATIO = 9 576DBL_PARAM_MAX_SECS_NOT_IMPROV_FS = 10 577 578INT_PARAM_PERT_VALUE = 0 579INT_PARAM_IDIOT = 1 580INT_PARAM_STRONG_BRANCHING = 2 581INT_PARAM_CUT_DEPTH = 3 582INT_PARAM_MAX_NODES = 4 583INT_PARAM_NUMBER_BEFORE = 5 584INT_PARAM_FPUMP_ITS = 6 585INT_PARAM_MAX_SOLS = 7 586INT_PARAM_CUT_PASS_IN_TREE = 8 587INT_PARAM_THREADS = 9 588INT_PARAM_CUT_PASS = 10 589INT_PARAM_LOG_LEVEL = 11 590INT_PARAM_MAX_SAVED_SOLS = 12 591INT_PARAM_MULTIPLE_ROOTS = 13 592INT_PARAM_ROUND_INT_VARS = 14 593INT_PARAM_RANDOM_SEED = 15 594INT_PARAM_ELAPSED_TIME = 16 595INT_PARAM_CGRAPH = 17 596INT_PARAM_CLIQUE_MERGING = 18 597INT_PARAM_MAX_NODES_NOT_IMPROV_FS = 19 598 599 600Osi_getNumCols = cbclib.Osi_getNumCols 601Osi_getColSolution = cbclib.Osi_getColSolution 602Osi_getIntegerTolerance = cbclib.Osi_getIntegerTolerance 603Osi_isInteger = cbclib.Osi_isInteger 604Osi_isProvenOptimal = cbclib.Osi_isProvenOptimal 605Cbc_setIntParam = cbclib.Cbc_setIntParam 606Cbc_setDblParam = cbclib.Cbc_setDblParam 607Cbc_getSolverPtr = cbclib.Cbc_getSolverPtr 608 609Cbc_generateCuts = cbclib.Cbc_generateCuts 610Cbc_solveLinearProgram = cbclib.Cbc_solveLinearProgram 611 612Cbc_computeFeatures = cbclib.Cbc_computeFeatures 613Cbc_nFeatures = cbclib.Cbc_nFeatures 614Cbc_featureName = cbclib.Cbc_featureName 615 616OsiCuts_new = cbclib.OsiCuts_new 617OsiCuts_addRowCut = cbclib.OsiCuts_addRowCut 618OsiCuts_addGlobalRowCut = cbclib.OsiCuts_addGlobalRowCut 619OsiCuts_sizeRowCuts = cbclib.OsiCuts_sizeRowCuts 620OsiCuts_nzRowCut = cbclib.OsiCuts_nzRowCut 621OsiCuts_idxRowCut = cbclib.OsiCuts_idxRowCut 622OsiCuts_coefRowCut = cbclib.OsiCuts_coefRowCut 623OsiCuts_rhsRowCut = cbclib.OsiCuts_rhsRowCut 624OsiCuts_senseRowCut = cbclib.OsiCuts_senseRowCut 625OsiCuts_delete = cbclib.OsiCuts_delete 626 627 628def cbc_set_parameter(model: Solver, param: str, value: str): 629 cbclib.Cbc_setParameter(model._model, param.encode("utf-8"), value.encode("utf-8")) 630 631 632class SolverCbc(Solver): 633 def __init__(self, model: Model, name: str, sense: str): 634 super().__init__(model, name, sense) 635 636 self._model = cbclib.Cbc_newModel() 637 cbclib.Cbc_storeNameIndexes(self._model, CHAR_ONE) 638 639 self.iidx_space = 4096 640 self.iidx = ffi.new("int[%d]" % self.iidx_space) 641 self.dvec = ffi.new("double[%d]" % self.iidx_space) 642 643 self._objconst = 0.0 644 645 # to not add cut generators twice when reoptimizing 646 self.added_cut_callback = False 647 self.added_inc_callback = False 648 649 # setting objective sense 650 if sense == MAXIMIZE: 651 cbclib.Cbc_setObjSense(self._model, -1.0) 652 653 self.emphasis = SearchEmphasis.DEFAULT 654 self.__threads = 0 655 self.__verbose = 1 656 # pre-allocate temporary space to query names 657 self.__name_space = ffi.new("char[{}]".format(MAX_NAME_SIZE)) 658 # in cut generation 659 self.__name_spacec = ffi.new("char[{}]".format(MAX_NAME_SIZE)) 660 self.__log = ( 661 [] 662 ) # type: List[Tuple[numbers.Real, Tuple[numbers.Real, numbers.Real]]] 663 self.set_problem_name(name) 664 self.__pumpp = DEF_PUMPP 665 666 # where solution will be stored 667 self.__x = EmptyVarSol(model) 668 self.__rc = EmptyVarSol(model) 669 self.__pi = EmptyRowSol(model) 670 self.__slack = EmptyRowSol(model) 671 self.__obj_val = None 672 self.__obj_bound = None 673 self.__num_solutions = 0 674 675 def __clear_sol(self: "SolverCbc"): 676 self.__x = EmptyVarSol(self.model) 677 self.__rc = EmptyVarSol(self.model) 678 self.__pi = EmptyRowSol(self.model) 679 self.__slack = EmptyRowSol(self.model) 680 self.__obj_val = None 681 self.__obj_bound = None 682 self.__num_solutions = 0 683 684 def add_var( 685 self, 686 obj: numbers.Real = 0, 687 lb: numbers.Real = 0, 688 ub: numbers.Real = float("inf"), 689 coltype: str = "C", 690 column: Optional[Column] = None, 691 name: str = "", 692 ): 693 if column is None: 694 vind = ffi.NULL 695 vval = ffi.NULL 696 numnz = 0 697 else: 698 numnz = len(column.constrs) 699 vind = ffi.new("int[]", [c.idx for c in column.constrs]) 700 vval = ffi.new("double[]", [coef for coef in column.coeffs]) 701 702 isInt = ( 703 CHAR_ONE if coltype.upper() == "B" or coltype.upper() == "I" else CHAR_ZERO 704 ) 705 cbclib.Cbc_addCol( 706 self._model, 707 name.encode("utf-8"), 708 lb, 709 ub, 710 obj, 711 isInt, 712 numnz, 713 vind, 714 vval, 715 ) 716 717 def update_conflict_graph(self: "SolverCbc"): 718 cbclib.Cbc_updateConflictGraph(self._model) 719 720 def cgraph_density(self: "SolverCbc") -> float: 721 cg = cbclib.Cbc_conflictGraph(self._model) 722 if cg == ffi.NULL: 723 return 0.0 724 return cbclib.CG_density(cg) 725 726 def conflicting( 727 self: "SolverCbc", 728 e1: Union["LinExpr", "Var"], 729 e2: Union["LinExpr", "Var"], 730 ) -> bool: 731 idx1, idx2 = (None, None) 732 if isinstance(e1, Var): 733 idx1 = e1.idx 734 elif isinstance(e1, LinExpr): 735 if len(e1.expr) == 1 and e1.sense == EQUAL: 736 v1 = next(iter(e1.expr.keys())) 737 if abs(e1.const) <= 1e-15: 738 idx1 = v1.idx + v1.model.num_cols 739 elif abs(e1.const + 1.0) <= 1e-15: 740 idx1 = v1.idx 741 else: 742 raise InvalidParameter( 743 "LinExpr should contain an " 744 "assignment to a binary variable, " 745 "e.g.: x1 == 1" 746 ) 747 else: 748 raise InvalidParameter( 749 "LinExpr should contain an " 750 "assignment to a binary variable, " 751 "e.g.: x1 == 1" 752 ) 753 else: 754 raise TypeError("type {} not supported".format(type(e1))) 755 756 if isinstance(e2, Var): 757 idx2 = e2.idx 758 elif isinstance(e2, LinExpr): 759 if len(e2.expr) == 1 and e2.sense == EQUAL: 760 v2 = next(iter(e2.expr.keys())) 761 if abs(e2.const) <= 1e-15: 762 idx2 = v2.idx + v2.model.num_cols 763 elif abs(e2.const + 1.0) <= 1e-15: 764 idx2 = v2.idx 765 else: 766 raise InvalidParameter( 767 "LinExpr should contain an " 768 "assignment to a binary variable, " 769 "e.g.: x1 == 1" 770 ) 771 else: 772 raise InvalidParameter( 773 "LinExpr should contain an " 774 "assignment to a binary variable, " 775 "e.g.: x1 == 1" 776 ) 777 else: 778 raise TypeError("type {} not supported".format(type(e2))) 779 780 cg = cbclib.Cbc_conflictGraph(self._model) 781 if cg == ffi.NULL: 782 return False 783 784 return cbclib.CG_conflicting(cg, idx1, idx2) == CHAR_ONE 785 786 def conflicting_nodes( 787 self: "SolverCbc", v1: Union["Var", "LinExpr"] 788 ) -> Tuple[List["Var"], List["Var"]]: 789 """Returns all assignment conflicting with the assignment in v1 in the 790 conflict graph. 791 """ 792 cg = cbclib.Cbc_conflictGraph(self._model) 793 if cg == ffi.NULL: 794 return (list(), list()) 795 796 idx1 = None 797 if isinstance(v1, Var): 798 idx1 = v1.idx 799 elif isinstance(v1, LinExpr): 800 if len(v1.expr) == 1 and v1.sense == EQUAL: 801 var = next(iter(v1.expr.keys())) 802 if abs(v1.const) <= 1e-15: 803 idx1 = var.idx + var.model.num_cols 804 elif abs(v1.const + 1.0) <= 1e-15: 805 idx1 = var.idx 806 else: 807 raise InvalidParameter( 808 "LinExpr should contain an " 809 "assignment to a binary variable, " 810 "e.g.: x1 == 1" 811 ) 812 else: 813 raise InvalidParameter( 814 "LinExpr should contain an " 815 "assignment to a binary variable, " 816 "e.g.: x1 == 1" 817 ) 818 else: 819 raise TypeError("type {} not supported".format(type(v1))) 820 821 cgn = cbclib.CG_conflictingNodes(self._model, cg, idx1) 822 n = cgn.n 823 neighs = cgn.neigh 824 cols = self.model.num_cols 825 l1, l0 = list(), list() 826 for i in range(n): 827 if cgn.neigh[i] < cols: 828 l1.append(self.model.vars[neighs[i]]) 829 else: 830 l0.append(self.model.vars[neighs[i] - cols]) 831 832 return (l1, l0) 833 834 def get_objective_const(self) -> numbers.Real: 835 return self._objconst 836 837 def get_objective(self) -> LinExpr: 838 obj = cbclib.Cbc_getObjCoefficients(self._model) 839 if obj == ffi.NULL: 840 raise ParameterNotAvailable("Error getting objective function coefficients") 841 return ( 842 xsum( 843 obj[j] * self.model.vars[j] 844 for j in range(self.num_cols()) 845 if abs(obj[j]) >= 1e-15 846 ) 847 + self._objconst 848 ) 849 850 def set_objective(self, lin_expr: "LinExpr", sense: str = "") -> None: 851 # collecting variable coefficients 852 853 c = ffi.new("double[]", [0.0 for i in range(self.num_cols())]) 854 for var, coeff in lin_expr.expr.items(): 855 c[var.idx] = coeff 856 857 for i in range(self.num_cols()): 858 cbclib.Cbc_setObjCoeff(self._model, i, c[i]) 859 860 # objective function constant 861 self._objconst = lin_expr.const 862 863 # setting objective sense 864 if MAXIMIZE in (lin_expr.sense, sense): 865 cbclib.Cbc_setObjSense(self._model, -1.0) 866 elif MINIMIZE in (lin_expr.sense, sense): 867 cbclib.Cbc_setObjSense(self._model, 1.0) 868 869 def relax(self): 870 for var in self.model.vars: 871 if cbclib.Cbc_isInteger(self._model, var.idx): 872 cbclib.Cbc_setContinuous(self._model, var.idx) 873 874 def get_max_seconds(self) -> numbers.Real: 875 return cbclib.Cbc_getMaximumSeconds(self._model) 876 877 def set_max_seconds(self, max_seconds: numbers.Real): 878 cbclib.Cbc_setMaximumSeconds(self._model, max_seconds) 879 880 def get_max_solutions(self) -> int: 881 return cbclib.Cbc_getMaximumSolutions(self._model) 882 883 def set_max_solutions(self, max_solutions: int): 884 cbclib.Cbc_setMaximumSolutions(self._model, max_solutions) 885 886 def get_max_nodes(self) -> int: 887 return cbclib.Cbc_getMaximumNodes(self._model) 888 889 def set_max_nodes(self, max_nodes: int): 890 cbclib.Cbc_setMaximumNodes(self._model, max_nodes) 891 892 def get_verbose(self) -> int: 893 return self.__verbose 894 895 def set_verbose(self, verbose: int): 896 self.__verbose = verbose 897 898 def var_set_var_type(self, var: "Var", value: str): 899 cv = var.var_type 900 if value == cv: 901 return 902 if cv == CONTINUOUS: 903 if value == INTEGER or value == BINARY: 904 cbclib.Cbc_setInteger(self._model, var.idx) 905 else: 906 if value == CONTINUOUS: 907 cbclib.Cbc_setContinuous(self._model, var.idx) 908 if value == BINARY: 909 # checking bounds 910 if var.lb != 0.0: 911 var.lb = 0.0 912 if var.ub != 1.0: 913 var.ub = 1.0 914 915 def var_set_obj(self, var: "Var", value: numbers.Real): 916 cbclib.Cbc_setObjCoeff(self._model, var.idx, value) 917 918 def generate_cuts( 919 self, 920 cut_types: Optional[List[CutType]] = None, 921 depth: int = 0, 922 npass: int = 0, 923 max_cuts: int = maxsize, 924 min_viol: numbers.Real = 1e-4, 925 ) -> CutPool: 926 cp = CutPool() 927 cbc_model = self._model 928 osi_solver = Cbc_getSolverPtr(cbc_model) 929 osi_cuts = OsiCuts_new() 930 nbin = 0 931 for v in self.model.vars: 932 if v.var_type == BINARY: 933 nbin += 1 934 935 if not cut_types: 936 cut_types = [ 937 CutType.GOMORY, 938 CutType.MIR, 939 CutType.TWO_MIR, 940 CutType.KNAPSACK_COVER, 941 CutType.CLIQUE, 942 CutType.ZERO_HALF, 943 CutType.ODD_WHEEL, 944 ] 945 for cut_type in cut_types: 946 if self.__verbose >= 1: 947 logger.info( 948 "searching for violated " "{} cuts ... ".format(cut_type.name) 949 ) 950 951 if nbin == 0: 952 if cut_type in [CutType.CLIQUE, CutType.ODD_WHEEL]: 953 continue 954 955 nc1 = OsiCuts_sizeRowCuts(osi_cuts) 956 957 Cbc_generateCuts( 958 self._model, 959 int(cut_type.value), 960 osi_cuts, 961 int(depth), 962 int(npass), 963 ) 964 nc2 = OsiCuts_sizeRowCuts(osi_cuts) 965 if self.__verbose >= 1: 966 logger.info("{} found.\n".format(nc2 - nc1)) 967 if OsiCuts_sizeRowCuts(osi_cuts) >= max_cuts: 968 break 969 970 for i in range(OsiCuts_sizeRowCuts(osi_cuts)): 971 rhs = OsiCuts_rhsRowCut(osi_cuts, i) 972 rsense = OsiCuts_senseRowCut(osi_cuts, i).decode("utf-8").upper() 973 974 sense = "" 975 if rsense == "E": 976 sense = EQUAL 977 elif rsense == "L": 978 sense = LESS_OR_EQUAL 979 elif rsense == "G": 980 sense = GREATER_OR_EQUAL 981 else: 982 raise ValueError("Unknow sense: {}".format(rsense)) 983 idx = OsiCuts_idxRowCut(osi_cuts, i) 984 coef = OsiCuts_coefRowCut(osi_cuts, i) 985 nz = OsiCuts_nzRowCut(osi_cuts, i) 986 model = self.model 987 levars = [model.vars[idx[j]] for j in range(nz)] 988 lecoefs = [coef[j] for j in range(nz)] 989 cut = LinExpr(levars, lecoefs, -rhs, sense) 990 if cut.violation < min_viol: 991 continue 992 cp.add(cut) 993 994 OsiCuts_delete(osi_cuts) 995 return cp 996 997 def clique_merge(self, constrs: Optional[List["mip.Constr"]] = None): 998 if constrs is None: 999 cbclib.Cbc_strengthenPacking(self._model) 1000 else: 1001 nr = len(constrs) 1002 idxr = ffi.new("int[]", [c.idx for c in constrs]) 1003 strengthenPacking = cbclib.Cbc_strengthenPackingRows 1004 strengthenPacking(self._model, nr, idxr) 1005 1006 def optimize(self, relax: bool = False) -> OptimizationStatus: 1007 # get name indexes from an osi problem 1008 def cbc_get_osi_name_indexes(osi_solver) -> Dict[str, int]: 1009 nameIdx = {} 1010 n = cbclib.Osi_getNumCols(osi_solver) 1011 for i in range(n): 1012 cbclib.Osi_getColName(osi_solver, i, self.__name_spacec, MAX_NAME_SIZE) 1013 cname = ffi.string(self.__name_spacec).decode("utf-8") 1014 nameIdx[cname] = i 1015 1016 return nameIdx 1017 1018 # progress callback 1019 @ffi.callback( 1020 """ 1021 int (void *, int, int, const char *, double, double, double, 1022 int, int *, void *) 1023 """ 1024 ) 1025 def cbc_progress_callback( 1026 model, 1027 phase: int, 1028 step: int, 1029 phaseName, 1030 seconds: numbers.Real, 1031 lb: numbers.Real, 1032 ub: numbers.Real, 1033 nint: int, 1034 vint, 1035 cbData, 1036 ) -> int: 1037 self.__log.append((seconds, (lb, ub))) 1038 return -1 1039 1040 # incumbent callback 1041 def cbc_inc_callback( 1042 cbc_model, obj: numbers.Real, nz: int, colNames, colValues, appData 1043 ): 1044 return 1045 1046 # cut callback 1047 @ffi.callback( 1048 """ 1049 void (void *osi_solver, void *osi_cuts, void *app_data, int level, int npass) 1050 """ 1051 ) 1052 def cbc_cut_callback(osi_solver, osi_cuts, app_data, depth, npass): 1053 if ( 1054 osi_solver == ffi.NULL 1055 or osi_cuts == ffi.NULL 1056 or ( 1057 self.model.cuts_generator is None 1058 and self.model.lazy_constrs_generator is None 1059 ) 1060 ): 1061 return 1062 if Osi_isProvenOptimal(osi_solver) != CHAR_ONE: 1063 return 1064 1065 # checking if solution is fractional or not 1066 nc = Osi_getNumCols(osi_solver) 1067 x = Osi_getColSolution(osi_solver) 1068 itol = Osi_getIntegerTolerance(osi_solver) 1069 fractional = False 1070 for j in range(nc): 1071 if Osi_isInteger(osi_solver, j): 1072 if abs(x[j] - round(x[j])) > itol: 1073 fractional = True 1074 break 1075 1076 osi_model = ModelOsi(osi_solver) 1077 osi_model._status = osi_model.solver.get_status() 1078 osi_model.solver.osi_cutsp = osi_cuts 1079 osi_model.fractional = fractional 1080 if fractional and self.model.cuts_generator: 1081 self.model.cuts_generator.generate_constrs(osi_model, depth, npass) 1082 if (not fractional) and self.model.lazy_constrs_generator: 1083 self.model.lazy_constrs_generator.generate_constrs( 1084 osi_model, depth, npass 1085 ) 1086 1087 if self.__verbose == 0: 1088 cbclib.Cbc_setLogLevel(self._model, 0) 1089 else: 1090 cbclib.Cbc_setLogLevel(self._model, 1) 1091 1092 if relax: 1093 self.__clear_sol() 1094 res = Cbc_solveLinearProgram(self._model) 1095 if res == 0: 1096 self.__x = cbclib.Cbc_getColSolution(self._model) 1097 self.__rc = cbclib.Cbc_getReducedCost(self._model) 1098 self.__pi = cbclib.Cbc_getRowPrice(self._model) 1099 self.__slack = cbclib.Cbc_getRowSlack(self._model) 1100 self.__obj_val = cbclib.Cbc_getObjValue(self._model) + self._objconst 1101 self.__obj_bound = self.__obj_val 1102 self.__num_solutions = 1 1103 1104 return OptimizationStatus.OPTIMAL 1105 if res == 2: 1106 return OptimizationStatus.UNBOUNDED 1107 if res == 3: 1108 return OptimizationStatus.INFEASIBLE 1109 return OptimizationStatus.ERROR 1110 1111 # adding cut generators 1112 m = self.model 1113 if m.cuts_generator is not None: 1114 atSol = CHAR_ZERO 1115 cbclib.Cbc_addCutCallback( 1116 self._model, 1117 cbc_cut_callback, 1118 "UserCuts".encode("utf-8"), 1119 ffi.NULL, 1120 1, 1121 atSol, 1122 ) 1123 if m.lazy_constrs_generator is not None: 1124 atSol = CHAR_ONE 1125 cbc_set_parameter(self, "preprocess", "off") 1126 cbc_set_parameter(self, "clqstr", "off") 1127 cbc_set_parameter(self, "heur", "off") 1128 cbclib.Cbc_addCutCallback( 1129 self._model, 1130 cbc_cut_callback, 1131 "LazyConstraints".encode("utf-8"), 1132 ffi.NULL, 1133 1, 1134 atSol, 1135 ) 1136 else: 1137 # no lazy constraints, more freedom to change parameters 1138 if self.model.preprocess == 0: 1139 cbc_set_parameter(self, "preprocess", "off") 1140 elif self.model.preprocess == 1: 1141 cbc_set_parameter(self, "preprocess", "sos") 1142 if self.__pumpp != DEF_PUMPP: 1143 cbc_set_parameter(self, "passf", "{}".format(self.__pumpp)) 1144 1145 if self.emphasis == SearchEmphasis.FEASIBILITY: 1146 cbc_set_parameter(self, "passf", "50") 1147 cbc_set_parameter(self, "proximity", "on") 1148 if self.emphasis == SearchEmphasis.OPTIMALITY: 1149 cbc_set_parameter(self, "strong", "10") 1150 cbc_set_parameter(self, "trust", "20") 1151 cbc_set_parameter(self, "lagomory", "endonly") 1152 cbc_set_parameter(self, "latwomir", "endonly") 1153 1154 if self.model.cuts == 0: 1155 cbc_set_parameter(self, "cuts", "off") 1156 1157 if self.model.cuts >= 1: 1158 cbc_set_parameter(self, "cuts", "on") 1159 if self.model.cuts >= 2: 1160 cbc_set_parameter(self, "lagomory", "endcleanroot") 1161 cbc_set_parameter(self, "latwomir", "endcleanroot") 1162 cbc_set_parameter(self, "passC", "-25") 1163 if self.model.cuts >= 3: 1164 cbc_set_parameter(self, "passC", "-35") 1165 cbc_set_parameter(self, "lift", "ifmove") 1166 1167 if self.__threads >= 1: 1168 cbc_set_parameter(self, "timeM", "{}".format("elapsed")) 1169 Cbc_setIntParam(self._model, INT_PARAM_THREADS, self.__threads) 1170 elif self.__threads == -1: 1171 cbc_set_parameter(self, "threads", "{}".format(multip.cpu_count())) 1172 1173 if self.model.cut_passes != -1: 1174 cbc_set_parameter(self, "passc", "{}".format(self.model.cut_passes)) 1175 1176 if self.model.clique == 0: 1177 cbc_set_parameter(self, "clique", "off") 1178 elif self.model.clique == 1: 1179 cbc_set_parameter(self, "clique", "forceon") 1180 1181 cbc_set_parameter(self, "maxSavedSolutions", "10") 1182 1183 if self.model.store_search_progress_log: 1184 cbclib.Cbc_addProgrCallback(self._model, cbc_progress_callback, ffi.NULL) 1185 1186 if self.model.integer_tol >= 0.0: 1187 cbclib.Cbc_setDblParam( 1188 self._model, DBL_PARAM_INT_TOL, self.model.integer_tol 1189 ) 1190 1191 if self.model.infeas_tol >= 0.0: 1192 cbclib.Cbc_setPrimalTolerance(self._model, self.model.infeas_tol) 1193 1194 if self.model.opt_tol >= 0.0: 1195 cbclib.Cbc_setDualTolerance(self._model, self.model.opt_tol) 1196 1197 if self.model.lp_method == LP_Method.BARRIER: 1198 cbclib.Cbc_setLPmethod(self._model, cbclib.LPM_Barrier) 1199 elif self.model.lp_method == LP_Method.DUAL: 1200 cbclib.Cbc_setLPmethod(self._model, cbclib.LPM_Dual) 1201 elif self.model.lp_method == LP_Method.PRIMAL: 1202 cbclib.Cbc_setLPmethod(self._model, cbclib.LPM_Primal) 1203 else: 1204 cbclib.Cbc_setLPmethod(self._model, cbclib.LPM_Auto) 1205 1206 cbclib.Cbc_setAllowableFractionGap(self._model, self.model.max_mip_gap) 1207 cbclib.Cbc_setAllowableGap(self._model, self.model.max_mip_gap_abs) 1208 cbclib.Cbc_setIntParam(self._model, INT_PARAM_RANDOM_SEED, self.model.seed) 1209 1210 cbclib.Cbc_setIntParam( 1211 self._model, 1212 INT_PARAM_ROUND_INT_VARS, 1213 int(self.model.round_int_vars), 1214 ) 1215 1216 cbclib.Cbc_setIntParam( 1217 self._model, INT_PARAM_MAX_SAVED_SOLS, self.model.sol_pool_size 1218 ) 1219 1220 self.__clear_sol() 1221 cbclib.Cbc_solve(self._model) 1222 1223 if cbclib.Cbc_isAbandoned(self._model): 1224 return OptimizationStatus.ERROR 1225 1226 if cbclib.Cbc_isProvenOptimal(self._model): 1227 self.__x = cbclib.Cbc_getColSolution(self._model) 1228 self.__slack = cbclib.Cbc_getRowSlack(self._model) 1229 self.__obj_val = cbclib.Cbc_getObjValue(self._model) + self._objconst 1230 self.__obj_bound = self.__obj_val 1231 self.__num_solutions = 1 1232 1233 if self.model.num_int == 0 and cbclib.Cbc_numberSOS(self._model) == 0: 1234 self.__rc = cbclib.Cbc_getReducedCost(self._model) 1235 self.__pi = cbclib.Cbc_getRowPrice(self._model) 1236 self.__slack = cbclib.Cbc_getRowSlack(self._model) 1237 else: 1238 self.__obj_bound = ( 1239 cbclib.Cbc_getBestPossibleObjValue(self._model) + self._objconst 1240 ) 1241 self.__num_solutions = cbclib.Cbc_numberSavedSolutions(self._model) 1242 return OptimizationStatus.OPTIMAL 1243 1244 if cbclib.Cbc_isProvenInfeasible(self._model): 1245 return OptimizationStatus.INFEASIBLE 1246 1247 if cbclib.Cbc_isContinuousUnbounded(self._model): 1248 return OptimizationStatus.UNBOUNDED 1249 1250 if cbclib.Cbc_getNumIntegers(self._model): 1251 self.__obj_bound = ( 1252 cbclib.Cbc_getBestPossibleObjValue(self._model) + self._objconst 1253 ) 1254 1255 if cbclib.Cbc_numberSavedSolutions(self._model) >= 1: 1256 self.__x = cbclib.Cbc_getColSolution(self._model) 1257 self.__slack = cbclib.Cbc_getRowSlack(self._model) 1258 self.__obj_val = cbclib.Cbc_getObjValue(self._model) + self._objconst 1259 self.__num_solutions = cbclib.Cbc_numberSavedSolutions(self._model) 1260 1261 return OptimizationStatus.FEASIBLE 1262 1263 return OptimizationStatus.NO_SOLUTION_FOUND 1264 1265 def get_objective_sense(self) -> str: 1266 obj = cbclib.Cbc_getObjSense(self._model) 1267 if obj < 0.0: 1268 return MAXIMIZE 1269 1270 return MINIMIZE 1271 1272 def set_objective_sense(self, sense: str): 1273 if sense.strip().upper() == MAXIMIZE.strip().upper(): 1274 cbclib.Cbc_setObjSense(self._model, -1.0) 1275 elif sense.strip().upper() == MINIMIZE.strip().upper(): 1276 cbclib.Cbc_setObjSense(self._model, 1.0) 1277 else: 1278 raise ValueError( 1279 "Unknown sense: {}, use {} or {}".format(sense, MAXIMIZE, MINIMIZE) 1280 ) 1281 1282 def get_objective_value(self) -> numbers.Real: 1283 # return 1284 return self.__obj_val 1285 1286 def get_status(self) -> OptimizationStatus: 1287 if cbclib.Cbc_isAbandoned(self._model): 1288 return OptimizationStatus.ERROR 1289 1290 if cbclib.Cbc_isProvenOptimal(self._model): 1291 return OptimizationStatus.OPTIMAL 1292 1293 if cbclib.Cbc_isProvenInfeasible(self._model): 1294 return OptimizationStatus.INFEASIBLE 1295 1296 if cbclib.Cbc_isContinuousUnbounded(self._model): 1297 return OptimizationStatus.UNBOUNDED 1298 1299 if cbclib.Cbc_getNumIntegers(self._model): 1300 if cbclib.Cbc_bestSolution(self._model): 1301 return OptimizationStatus.FEASIBLE 1302 1303 return OptimizationStatus.NO_SOLUTION_FOUND 1304 1305 def get_log( 1306 self, 1307 ) -> List[Tuple[numbers.Real, Tuple[numbers.Real, numbers.Real]]]: 1308 return self.__log 1309 1310 def get_objective_bound(self) -> numbers.Real: 1311 return self.__obj_bound 1312 1313 def var_get_x(self, var: Var) -> Optional[numbers.Real]: 1314 # model status is *already checked* Var x property 1315 # (returns None if no solution available) 1316 return self.__x[var.idx] 1317 1318 def get_num_solutions(self) -> int: 1319 return self.__num_solutions 1320 1321 def get_objective_value_i(self, i: int) -> numbers.Real: 1322 return cbclib.Cbc_savedSolutionObj(self._model, i) + self._objconst 1323 1324 def var_get_xi(self, var: "Var", i: int) -> numbers.Real: 1325 # model status is *already checked* Var xi property 1326 # (returns None if no solution available) 1327 return cbclib.Cbc_savedSolution(self._model, i)[var.idx] 1328 1329 def var_get_rc(self, var: Var) -> numbers.Real: 1330 # model status is *already checked* Var rc property 1331 # (returns None if no solution available) 1332 return self.__rc[var.idx] 1333 1334 def var_get_lb(self, var: "Var") -> numbers.Real: 1335 return cbclib.Cbc_getColLB(self._model, var.idx) 1336 1337 def var_set_lb(self, var: "Var", value: numbers.Real): 1338 cbclib.Cbc_setColLower(self._model, var.idx, value) 1339 1340 def var_get_ub(self, var: "Var") -> numbers.Real: 1341 return cbclib.Cbc_getColUB(self._model, var.idx) 1342 1343 def var_set_ub(self, var: "Var", value: numbers.Real): 1344 cbclib.Cbc_setColUpper(self._model, var.idx, value) 1345 1346 def var_get_name(self, idx: int) -> str: 1347 namep = self.__name_space 1348 cbclib.Cbc_getColName(self._model, idx, namep, MAX_NAME_SIZE) 1349 return ffi.string(namep).decode("utf-8") 1350 1351 def var_get_index(self, name: str) -> int: 1352 return cbclib.Cbc_getColNameIndex(self._model, name.encode("utf-8")) 1353 1354 def constr_get_index(self, name: str) -> int: 1355 return cbclib.Cbc_getRowNameIndex(self._model, name.encode("utf-8")) 1356 1357 def constr_get_rhs(self, idx: int) -> numbers.Real: 1358 return cbclib.Cbc_getRowRHS(self._model, idx) 1359 1360 def constr_set_rhs(self, idx: int, rhs: numbers.Real): 1361 cbclib.Cbc_setRowRHS(self._model, idx, rhs) 1362 1363 def var_get_obj(self, var: Var) -> numbers.Real: 1364 return cbclib.Cbc_getColObj(self._model, var.idx) 1365 1366 def var_get_var_type(self, var: "Var") -> str: 1367 isInt = cbclib.Cbc_isInteger(self._model, var.idx) 1368 if isInt: 1369 lb = self.var_get_lb(var) 1370 ub = self.var_get_ub(var) 1371 if abs(lb) <= 1e-15 and abs(ub - 1.0) <= 1e-15: 1372 return BINARY 1373 else: 1374 return INTEGER 1375 1376 return CONTINUOUS 1377 1378 def var_get_column(self, var: "Var") -> Column: 1379 numnz = cbclib.Cbc_getColNz(self._model, var.idx) 1380 if numnz == 0: 1381 return Column() 1382 1383 cidx = cbclib.Cbc_getColIndices(self._model, var.idx) 1384 if cidx == ffi.NULL: 1385 raise ParameterNotAvailable("Error getting column indices'") 1386 ccoef = cbclib.Cbc_getColCoeffs(self._model, var.idx) 1387 1388 return Column( 1389 [Constr(self.model, cidx[i]) for i in range(numnz)], 1390 [ccoef[i] for i in range(numnz)], 1391 ) 1392 1393 def add_constr(self, lin_expr: LinExpr, name: str = ""): 1394 # collecting linear expression data 1395 numnz = len(lin_expr.expr) 1396 1397 if numnz > self.iidx_space: 1398 self.iidx_space = max(numnz, self.iidx_space * 2) 1399 self.iidx = ffi.new("int[%d]" % self.iidx_space) 1400 self.dvec = ffi.new("double[%d]" % self.iidx_space) 1401 1402 # cind = self.iidx 1403 self.iidx = [var.idx for var in lin_expr.expr.keys()] 1404 1405 # cind = ffi.new("int[]", [var.idx for var in lin_expr.expr.keys()]) 1406 # cval = ffi.new("double[]", [coef for coef in lin_expr.expr.values()]) 1407 # cval = self.dvec 1408 self.dvec = [coef for coef in lin_expr.expr.values()] 1409 1410 # constraint sense and rhs 1411 sense = lin_expr.sense.encode("utf-8") 1412 rhs = -lin_expr.const 1413 1414 namestr = name.encode("utf-8") 1415 mp = self._model 1416 cbclib.Cbc_addRow(mp, namestr, numnz, self.iidx, self.dvec, sense, rhs) 1417 1418 def add_lazy_constr(self: "Solver", lin_expr: LinExpr): 1419 # collecting linear expression data 1420 numnz = len(lin_expr.expr) 1421 1422 cind = ffi.new("int[]", [var.idx for var in lin_expr.expr.keys()]) 1423 cval = ffi.new("double[]", [coef for coef in lin_expr.expr.values()]) 1424 1425 # constraint sense and rhs 1426 sense = lin_expr.sense.encode("utf-8") 1427 rhs = -lin_expr.const 1428 1429 mp = self._model 1430 cbclib.Cbc_addLazyConstraint(mp, numnz, cind, cval, sense, rhs) 1431 1432 def add_sos(self, sos: List[Tuple["Var", numbers.Real]], sos_type: int): 1433 starts = ffi.new("int[]", [0, len(sos)]) 1434 idx = ffi.new("int[]", [v.idx for (v, f) in sos]) 1435 w = ffi.new("double[]", [f for (v, f) in sos]) 1436 cbclib.Cbc_addSOS(self._model, 1, starts, idx, w, sos_type) 1437 1438 def add_cut(self, lin_expr: LinExpr): 1439 global cut_idx 1440 name = "cut{}".format(cut_idx) 1441 self.add_constr(lin_expr, name) 1442 1443 def write(self, file_path: str): 1444 fpstr = file_path.encode("utf-8") 1445 if ".mps" in file_path.lower(): 1446 cbclib.Cbc_writeMps(self._model, fpstr) 1447 elif ".lp" in file_path.lower(): 1448 cbclib.Cbc_writeLp(self._model, fpstr) 1449 elif ".bas" in file_path.lower(): 1450 cbclib.Cbc_writeBasis(self._model, fpstr, CHAR_ONE, 2) 1451 else: 1452 raise ValueError( 1453 "Enter a valid extension (.lp, .mps or .bas) \ 1454 to indicate the file format" 1455 ) 1456 1457 def read(self, file_path: str) -> None: 1458 if not isfile(file_path): 1459 raise FileNotFoundError("File {} does not exists".format(file_path)) 1460 1461 if file_path.lower().endswith(".gz") and cbclib.Cbc_supportsGzip() == CHAR_ZERO: 1462 raise MipBaseException("CBC not compiled with gzip support") 1463 if ( 1464 file_path.lower().endswith(".bz2") 1465 and cbclib.Cbc_supportsBzip2() == CHAR_ZERO 1466 ): 1467 raise MipBaseException("CBC not compiled with bzip2 support") 1468 1469 fpstr = file_path.encode("utf-8") 1470 if ".mps" in file_path.lower(): 1471 cbclib.Cbc_readMps(self._model, fpstr) 1472 elif ".lp" in file_path.lower(): 1473 cbclib.Cbc_readLp(self._model, fpstr) 1474 elif ".bas" in file_path.lower(): 1475 status = cbclib.Cbc_readBasis(self._model, fpstr) 1476 if status == -1: 1477 raise IOError("Error reading %s" % file_path) 1478 elif status == 0: 1479 logger.warning("No values read from %s" % file_path) 1480 elif status == 1: 1481 logger.info("Optimal LP basis successfully loaded.") 1482 1483 else: 1484 raise ValueError( 1485 "Enter a valid extension (.lp, .mps or .bas) \ 1486 to indicate the file format" 1487 ) 1488 1489 def set_start(self, start: List[Tuple[Var, numbers.Real]]) -> None: 1490 n = len(start) 1491 dv = ffi.new("double[]", [start[i][1] for i in range(n)]) 1492 keep_alive_str = [ 1493 ffi.new("char[]", str.encode(start[i][0].name)) for i in range(n) 1494 ] 1495 var_names = ffi.new("char *[]", keep_alive_str) 1496 mdl = self._model 1497 cbclib.Cbc_setMIPStart(mdl, n, var_names, dv) 1498 1499 def num_cols(self) -> int: 1500 return cbclib.Cbc_getNumCols(self._model) 1501 1502 def num_int(self) -> int: 1503 return cbclib.Cbc_getNumIntegers(self._model) 1504 1505 def num_rows(self) -> int: 1506 return cbclib.Cbc_getNumRows(self._model) 1507 1508 def num_nz(self) -> int: 1509 return cbclib.Cbc_getNumElements(self._model) 1510 1511 def get_cutoff(self) -> numbers.Real: 1512 return cbclib.Cbc_getCutoff(self._model) 1513 1514 def set_cutoff(self, cutoff: numbers.Real): 1515 cbclib.Cbc_setCutoff(self._model, cutoff) 1516 1517 def get_mip_gap_abs(self) -> numbers.Real: 1518 return cbclib.Cbc_getAllowableGap(self._model) 1519 1520 def set_mip_gap_abs(self, allowable_gap: numbers.Real): 1521 cbclib.Cbc_setAllowableGap(self._model, allowable_gap) 1522 1523 def get_mip_gap(self) -> numbers.Real: 1524 return cbclib.Cbc_getAllowableFractionGap(self._model) 1525 1526 def set_mip_gap(self, allowable_ratio_gap: numbers.Real): 1527 cbclib.Cbc_setAllowableFractionGap(self._model, allowable_ratio_gap) 1528 1529 def constr_get_expr(self, constr: Constr) -> LinExpr: 1530 numnz = cbclib.Cbc_getRowNz(self._model, constr.idx) 1531 1532 ridx = cbclib.Cbc_getRowIndices(self._model, constr.idx) 1533 if ridx == ffi.NULL: 1534 raise ParameterNotAvailable("Error getting row indices.") 1535 rcoef = cbclib.Cbc_getRowCoeffs(self._model, constr.idx) 1536 if rcoef == ffi.NULL: 1537 raise ParameterNotAvailable("Error getting row coefficients.") 1538 1539 rhs = cbclib.Cbc_getRowRHS(self._model, constr.idx) 1540 rsense = cbclib.Cbc_getRowSense(self._model, constr.idx).decode("utf-8").upper() 1541 sense = "" 1542 if rsense == "E": 1543 sense = EQUAL 1544 elif rsense == "L": 1545 sense = LESS_OR_EQUAL 1546 elif rsense == "G": 1547 sense = GREATER_OR_EQUAL 1548 else: 1549 raise ValueError("Unknow sense: {}".format(rsense)) 1550 1551 expr = LinExpr(const=-rhs, sense=sense) 1552 for i in range(numnz): 1553 expr.add_var(self.model.vars[ridx[i]], rcoef[i]) 1554 1555 return expr 1556 1557 def constr_get_name(self, idx: int) -> str: 1558 namep = self.__name_space 1559 cbclib.Cbc_getRowName(self._model, idx, namep, MAX_NAME_SIZE) 1560 return ffi.string(namep).decode("utf-8") 1561 1562 def set_processing_limits( 1563 self: "Solver", 1564 max_time: numbers.Real = mip.INF, 1565 max_nodes: int = mip.INT_MAX, 1566 max_sol: int = mip.INT_MAX, 1567 max_seconds_same_incumbent: int = mip.INT_MAX, 1568 max_nodes_same_incumbent: float = mip.INF, 1569 ): 1570 pmodel = self._model 1571 1572 """processing limits should be set even when they INF, since 1573 smaller limits could have been set in a previous iteration""" 1574 1575 if max_time != mip.INF: 1576 cbc_set_parameter(self, "timeMode", "elapsed") 1577 self.set_max_seconds(max_time) 1578 if max_nodes != mip.INT_MAX: 1579 self.set_max_nodes(max_nodes) 1580 if max_sol != mip.INT_MAX: 1581 self.set_max_solutions(max_sol) 1582 if max_seconds_same_incumbent != mip.INF: 1583 Cbc_setDblParam( 1584 pmodel, DBL_PARAM_MAX_SECS_NOT_IMPROV_FS, max_seconds_same_incumbent 1585 ) 1586 if max_nodes_same_incumbent != mip.INT_MAX: 1587 Cbc_setIntParam( 1588 pmodel, INT_PARAM_MAX_NODES_NOT_IMPROV_FS, max_nodes_same_incumbent 1589 ) 1590 1591 def get_emphasis(self) -> SearchEmphasis: 1592 return self.emphasis 1593 1594 def set_emphasis(self, emph: SearchEmphasis): 1595 self.emphasis = emph 1596 1597 def set_num_threads(self, threads: int): 1598 self.__threads = threads 1599 1600 def remove_constrs(self, constrs: List[int]): 1601 idx = ffi.new("int[]", constrs) 1602 cbclib.Cbc_deleteRows(self._model, len(constrs), idx) 1603 1604 def remove_vars(self, varsList: List[int]): 1605 idx = ffi.new("int[]", varsList) 1606 cbclib.Cbc_deleteCols(self._model, len(varsList), idx) 1607 1608 def __del__(self): 1609 cbclib.Cbc_deleteModel(self._model) 1610 1611 def get_problem_name(self) -> str: 1612 namep = self.__name_space 1613 cbclib.Cbc_problemName(self._model, MAX_NAME_SIZE, namep) 1614 return ffi.string(namep).decode("utf-8") 1615 1616 def set_problem_name(self, name: str): 1617 cbclib.Cbc_setProblemName(self._model, name.encode("utf-8")) 1618 1619 def get_pump_passes(self) -> int: 1620 return self.__pumpp 1621 1622 def set_pump_passes(self, passes: int): 1623 self.__pumpp = passes 1624 1625 def constr_get_pi(self, constr: Constr) -> Optional[numbers.Real]: 1626 return self.__pi[constr.idx] 1627 1628 def constr_get_slack(self, constr: Constr) -> Optional[numbers.Real]: 1629 return self.__slack[constr.idx] 1630 1631 def feature_values(self) -> List[float]: 1632 n = int(Cbc_nFeatures()) 1633 fv = ffi.new("double[%d]" % n) 1634 Cbc_computeFeatures(self._model, fv) 1635 return [float(fv[i]) for i in range(n)] 1636 1637 1638def feature_names() -> List[str]: 1639 n = int(Cbc_nFeatures()) 1640 return [ffi.string(Cbc_featureName(i)).decode("utf-8") for i in range(n)] 1641 1642 1643class ModelOsi(Model): 1644 def __init__(self, osi_ptr): 1645 # initializing variables with default values 1646 self.solver_name = "osi" 1647 existing_solver = osi_ptr != ffi.NULL 1648 1649 self.solver = SolverOsi(self, osi_ptr) 1650 1651 # list of constraints and variables 1652 self.constrs = VConstrList(self) 1653 self.vars = VVarList(self) 1654 1655 # if a fractional solution is being processed 1656 self.fractional = True 1657 1658 if existing_solver: 1659 self._status = self.solver.get_status() 1660 else: 1661 self._status = OptimizationStatus.LOADED 1662 1663 # initializing additional control variables 1664 self.__cuts = -1 1665 self.__cut_passes = -1 1666 self.__clique = -1 1667 self.__preprocess = -1 1668 self.__constrs_generator = None 1669 self.__lazy_constrs_generator = None 1670 self.__start = None 1671 self.__threads = 0 1672 self.__n_cols = 0 1673 self.__n_rows = 0 1674 self.__gap = INF 1675 self.__store_search_progress_log = False 1676 1677 def add_constr(self, lin_expr: LinExpr, name: str = "") -> "Constr": 1678 if self.fractional: 1679 self.add_cut(lin_expr) 1680 return None 1681 1682 self.add_lazy_constr(lin_expr) 1683 return None 1684 1685 1686class SolverOsi(Solver): 1687 """Interface for the OsiSolverInterface, the generic solver interface of 1688 COIN-OR. This solver has a restricted functionality (comparing to 1689 SolverCbc) and it is used mainly in callbacks where only the pre-processed 1690 model is available""" 1691 1692 def __init__(self, model: Model, osi_ptr=ffi.NULL): 1693 super().__init__(model) 1694 1695 self._objconst = 0.0 1696 1697 # pre-allocate temporary space to query names 1698 self.__name_space = ffi.new("char[{}]".format(MAX_NAME_SIZE)) 1699 # in cut generation 1700 self.__name_spacec = ffi.new("char[{}]".format(MAX_NAME_SIZE)) 1701 1702 if osi_ptr != ffi.NULL: 1703 self.osi = osi_ptr 1704 self.owns_solver = False 1705 else: 1706 self.owns_solver = True 1707 self.osi = cbclib.Osi_newSolver() 1708 self.__relaxed = False 1709 1710 # name indexes, created if necessary 1711 self.colNames = None 1712 self.rowNames = None 1713 self._objconst = 0.0 1714 self.osi_cutsp = ffi.NULL 1715 self.__x = EmptyVarSol(model) 1716 self.__rc = EmptyVarSol(model) 1717 self.__pi = EmptyRowSol(model) 1718 self.__obj_val = None 1719 1720 if cbclib.Osi_isProvenOptimal(self.osi): 1721 self.__x = cbclib.Osi_getColSolution(self.osi) 1722 self.__rc = cbclib.Osi_getReducedCost(self.osi) 1723 self.__pi = cbclib.Osi_getRowPrice(self.osi) 1724 self.__obj_val = cbclib.Osi_getObjValue(self.osi) 1725 1726 def __clear_sol(self: "SolverOsi"): 1727 self.__x = EmptyVarSol(self.model) 1728 self.__rc = EmptyVarSol(self.model) 1729 self.__pi = EmptyRowSol(self.model) 1730 self.__obj_val = None 1731 1732 def __del__(self): 1733 if self.owns_solver: 1734 cbclib.Osi_deleteSolver(self.osi) 1735 1736 def add_var( 1737 self, 1738 name: str = "", 1739 obj: numbers.Real = 0, 1740 lb: numbers.Real = 0, 1741 ub: numbers.Real = INF, 1742 var_type: str = CONTINUOUS, 1743 column: "Column" = None, 1744 ): 1745 # collecting column data 1746 if column is None: 1747 vind = ffi.NULL 1748 vval = ffi.NULL 1749 numnz = 0 1750 else: 1751 vind = ffi.new("int[]", [c.idx for c in column.constrs]) 1752 vval = ffi.new("double[]", [coef for coef in column.coeffs]) 1753 numnz = len(column.constrs) 1754 1755 isInt = ( 1756 CHAR_ONE if var_type.upper() == "B" or var_type.upper() == "I" else CHAR_ZERO 1757 ) 1758 cbclib.Osi_addCol( 1759 self.osi, 1760 name.encode("utf-8"), 1761 lb, 1762 ub, 1763 obj, 1764 isInt, 1765 numnz, 1766 vind, 1767 vval, 1768 ) 1769 1770 def add_constr(self, lin_expr: "LinExpr", name: str = ""): 1771 # collecting linear expression data 1772 numnz = len(lin_expr.expr) 1773 1774 cind = ffi.new("int[]", [var.idx for var in lin_expr.expr.keys()]) 1775 cval = ffi.new("double[]", [coef for coef in lin_expr.expr.values()]) 1776 1777 # constraint sense and rhs 1778 sense = lin_expr.sense.encode("utf-8") 1779 rhs = -lin_expr.const 1780 1781 namestr = name.encode("utf-8") 1782 mp = self.osi 1783 cbclib.Osi_addRow(mp, namestr, numnz, cind, cval, sense, rhs) 1784 1785 def add_cut(self, lin_expr: LinExpr): 1786 if self.osi_cutsp != ffi.NULL: 1787 if lin_expr.violation < 1e-5: 1788 return 1789 1790 numnz = len(lin_expr.expr) 1791 1792 cind = ffi.new("int[]", [var.idx for var in lin_expr.expr.keys()]) 1793 cval = ffi.new("double[]", [coef for coef in lin_expr.expr.values()]) 1794 1795 # constraint sense and rhs 1796 sense = lin_expr.sense.encode("utf-8") 1797 rhs = -lin_expr.const 1798 1799 OsiCuts_addGlobalRowCut(self.osi_cutsp, numnz, cind, cval, sense, rhs) 1800 else: 1801 global cut_idx 1802 name = "cut{}".format(cut_idx) 1803 self.add_constr(lin_expr, name) 1804 1805 def add_lazy_constr(self, lin_expr: LinExpr): 1806 if self.osi_cutsp != ffi.NULL: 1807 # checking if violated 1808 if lin_expr.violation < 1e-5: 1809 return 1810 1811 numnz = len(lin_expr.expr) 1812 1813 cind = ffi.new("int[]", [var.idx for var in lin_expr.expr.keys()]) 1814 cval = ffi.new("double[]", [coef for coef in lin_expr.expr.values()]) 1815 1816 # constraint sense and rhs 1817 sense = lin_expr.sense.encode("utf-8") 1818 rhs = -lin_expr.const 1819 1820 OsiCuts_addGlobalRowCut(self.osi_cutsp, numnz, cind, cval, sense, rhs) 1821 else: 1822 global cut_idx 1823 name = "cut{}".format(cut_idx) 1824 self.add_constr(lin_expr, name) 1825 1826 def get_objective_bound(self) -> numbers.Real: 1827 raise NotImplementedError("Not available in OsiSolver") 1828 1829 def get_objective(self) -> LinExpr: 1830 obj = cbclib.Osi_getObjCoefficients(self.osi) 1831 if obj == ffi.NULL: 1832 raise ParameterNotAvailable("Error getting objective function coefficients") 1833 return ( 1834 xsum( 1835 obj[j] * self.model.vars[j] 1836 for j in range(self.num_cols()) 1837 if abs(obj[j]) >= 1e-15 1838 ) 1839 + self._objconst 1840 ) 1841 1842 def get_objective_const(self) -> numbers.Real: 1843 return self._objconst 1844 1845 def relax(self): 1846 self.__relaxed = True 1847 1848 def optimize(self) -> OptimizationStatus: 1849 if self.__relaxed or self.num_int() == 0: 1850 # linear optimization 1851 if cbclib.Osi_isProvenOptimal(self.osi): 1852 cbclib.Osi_resolve(self.osi) 1853 else: 1854 cbclib.Osi_initialSolve(self.osi) 1855 else: 1856 cbclib.Osi_branchAndBound(self.osi) 1857 1858 if cbclib.Osi_isProvenOptimal(self.osi): 1859 self.__x = cbclib.Osi_getColSolution(self.osi) 1860 self.__rc = cbclib.Osi_getReducedCost(self.osi) 1861 self.__pi = cbclib.Osi_getRowPrice(self.osi) 1862 self.__obj_val = cbclib.Osi_getObjValue(self.osi) 1863 1864 return self.get_status() 1865 1866 def get_status(self) -> OptimizationStatus: 1867 if cbclib.Osi_isProvenOptimal(self.osi): 1868 return OptimizationStatus.OPTIMAL 1869 1870 if cbclib.Osi_isProvenPrimalInfeasible( 1871 self.osi 1872 ) or cbclib.Osi_isProvenDualInfeasible(self.osi): 1873 return OptimizationStatus.INFEASIBLE 1874 elif cbclib.Osi_isAbandoned(self.osi): 1875 return OptimizationStatus.ERROR 1876 return OptimizationStatus.LOADED 1877 1878 def get_objective_value(self) -> numbers.Real: 1879 return self.__obj_val 1880 1881 def get_log( 1882 self, 1883 ) -> List[Tuple[numbers.Real, Tuple[numbers.Real, numbers.Real]]]: 1884 return [] 1885 1886 def get_objective_value_i(self, i: int) -> numbers.Real: 1887 raise NotImplementedError("Not available in OsiSolver") 1888 1889 def get_num_solutions(self) -> int: 1890 if cbclib.Osi_isProvenOptimal(self.osi): 1891 return 1 1892 1893 return 0 1894 1895 def get_objective_sense(self) -> str: 1896 objs = cbclib.Osi_getObjSense(self.osi) 1897 if objs <= -0.5: 1898 return MAXIMIZE 1899 1900 return MINIMIZE 1901 1902 def set_objective_sense(self, sense: str): 1903 if sense.strip().upper() == MAXIMIZE.strip().upper(): 1904 cbclib.Osi_setObjSense(self.osi, -1.0) 1905 elif sense.strip().upper() == MINIMIZE.strip().upper(): 1906 cbclib.Osi_setObjSense(self.osi, 1.0) 1907 else: 1908 raise ValueError( 1909 "Unknown sense: {}, use {} or {}".format(sense, MAXIMIZE, MINIMIZE) 1910 ) 1911 1912 def set_start(self, start: List[Tuple["Var", numbers.Real]]): 1913 raise NotImplementedError("MIPstart not available in OsiSolver") 1914 1915 def set_objective(self, lin_expr: "LinExpr", sense: str = ""): 1916 # collecting variable coefficients 1917 for var, coeff in lin_expr.expr.items(): 1918 cbclib.Osi_setObjCoeff(self.osi, var.idx, coeff) 1919 1920 # objective function constant 1921 self._objconst = lin_expr.const 1922 1923 # setting objective sense 1924 if sense == MAXIMIZE: 1925 cbclib.Osi_setObjSense(self.osi, -1.0) 1926 elif sense == MINIMIZE: 1927 cbclib.Osi_setObjSense(self.osi, 1.0) 1928 1929 def set_objective_const(self, const: numbers.Real): 1930 raise NotImplementedError("Still not implemented in OsiSolver") 1931 1932 def set_processing_limits( 1933 self, 1934 max_time: numbers.Real = INF, 1935 max_nodes: int = maxsize, 1936 max_sol: int = maxsize, 1937 ): 1938 raise NotImplementedError("Not available in OsiSolver") 1939 1940 def get_max_seconds(self) -> numbers.Real: 1941 raise NotImplementedError("Not available in OsiSolver") 1942 1943 def set_max_seconds(self, max_seconds: numbers.Real): 1944 raise NotImplementedError("Not available in OsiSolver") 1945 1946 def get_max_solutions(self) -> int: 1947 raise NotImplementedError("Not available in OsiSolver") 1948 1949 def set_max_solutions(self, max_solutions: int): 1950 raise NotImplementedError("Not available in OsiSolver") 1951 1952 def get_pump_passes(self) -> int: 1953 raise NotImplementedError("Not available in OsiSolver") 1954 1955 def set_pump_passes(self, passes: int): 1956 raise NotImplementedError("Not available in OsiSolver") 1957 1958 def get_max_nodes(self) -> int: 1959 raise NotImplementedError("Not available in OsiSolver") 1960 1961 def set_max_nodes(self, max_nodes: int): 1962 raise NotImplementedError("Not available in OsiSolver") 1963 1964 def set_num_threads(self, threads: int): 1965 raise NotImplementedError("Not available in OsiSolver") 1966 1967 def write(self, file_path: str): 1968 raise NotImplementedError("Not available in OsiSolver") 1969 1970 def read(self, file_path: str): 1971 raise NotImplementedError("Not available in OsiSolver") 1972 1973 def num_cols(self) -> int: 1974 return cbclib.Osi_getNumCols(self.osi) 1975 1976 def num_rows(self) -> int: 1977 return cbclib.Osi_getNumRows(self.osi) 1978 1979 def num_nz(self) -> int: 1980 return cbclib.Osi_getNumElements(self.osi) 1981 1982 def num_int(self) -> int: 1983 return cbclib.Osi_getNumIntegers(self.osi) 1984 1985 def get_emphasis(self) -> SearchEmphasis: 1986 raise NotImplementedError("Not available in OsiSolver") 1987 1988 def set_emphasis(self, emph: SearchEmphasis): 1989 raise NotImplementedError("Not available in OsiSolver") 1990 1991 def get_cutoff(self) -> numbers.Real: 1992 raise NotImplementedError("Not available in OsiSolver") 1993 1994 def set_cutoff(self, cutoff: numbers.Real): 1995 raise NotImplementedError("Not available in OsiSolver") 1996 1997 def get_mip_gap_abs(self) -> numbers.Real: 1998 raise NotImplementedError("Not available in OsiSolver") 1999 2000 def set_mip_gap_abs(self, mip_gap_abs: numbers.Real): 2001 raise NotImplementedError("Not available in OsiSolver") 2002 2003 def get_mip_gap(self) -> numbers.Real: 2004 raise NotImplementedError("Not available in OsiSolver") 2005 2006 def set_mip_gap(self, mip_gap: numbers.Real): 2007 raise NotImplementedError("Not available in OsiSolver") 2008 2009 def get_verbose(self) -> int: 2010 raise NotImplementedError("Not available in OsiSolver") 2011 2012 def set_verbose(self, verbose: int): 2013 raise NotImplementedError("Not available in OsiSolver") 2014 2015 # Constraint-related getters/setters 2016 def constr_get_expr(self, constr: Constr) -> LinExpr: 2017 numnz = cbclib.Osi_getRowNz(self.osi, constr.idx) 2018 2019 ridx = cbclib.Osi_getRowIndices(self.osi, constr.idx) 2020 if ridx == ffi.NULL: 2021 raise ParameterNotAvailable("Error getting row indices.") 2022 rcoef = cbclib.Osi_getRowCoeffs(self.osi, constr.idx) 2023 if rcoef == ffi.NULL: 2024 raise ParameterNotAvailable("Error getting row coefficients.") 2025 2026 rhs = cbclib.Osi_getRowRHS(self.osi, constr.idx) 2027 rsense = cbclib.Osi_getRowSense(self.osi, constr.idx).decode("utf-8").upper() 2028 sense = "" 2029 if rsense == "E": 2030 sense = EQUAL 2031 elif rsense == "L": 2032 sense = LESS_OR_EQUAL 2033 elif rsense == "G": 2034 sense = GREATER_OR_EQUAL 2035 else: 2036 raise ValueError("Unknow sense: {}".format(rsense)) 2037 2038 expr = LinExpr(const=-rhs, sense=sense) 2039 for i in range(numnz): 2040 expr.add_var(self.model.vars[ridx[i]], rcoef[i]) 2041 2042 return expr 2043 2044 def constr_set_expr(self, constr: Constr, value: LinExpr) -> LinExpr: 2045 raise NotImplementedError("Not available in OsiSolver") 2046 2047 def constr_get_name(self, idx: int) -> str: 2048 namep = self.__name_space 2049 cbclib.Osi_getRowName(self.osi, idx, namep, MAX_NAME_SIZE) 2050 return ffi.string(namep).decode("utf-8") 2051 2052 def remove_constrs(self, constrsList: List[int]): 2053 raise NotImplementedError("Not available in OsiSolver") 2054 2055 def constr_get_index(self, name: str) -> int: 2056 if self.rowNames is None: 2057 self.rowNames = {} 2058 for i in range(self.num_rows()): 2059 self.rowNames[self.constr_get_name(i)] = i 2060 2061 if name in self.rowNames: 2062 return self.rowNames[name] 2063 2064 return -1 2065 2066 def constr_get_pi(self, constr: Constr) -> Optional[numbers.Real]: 2067 return self.__pi[constr.idx] 2068 2069 def constr_get_slack(self, constr: Constr) -> Optional[float]: 2070 if self.model.status not in [ 2071 OptimizationStatus.OPTIMAL, 2072 OptimizationStatus.FEASIBLE, 2073 ]: 2074 return None 2075 pac = cbclib.Osi_getRowActivity(self.osi) 2076 if pac == ffi.NULL: 2077 return None 2078 rhs = cbclib.Osi_getRowRHS(self.osi, constr.idx) 2079 activity = pac[constr.idx] 2080 2081 sense = cbclib.Osi_getRowSense(self.osi, constr.idx).decode("utf-8").upper() 2082 2083 if sense in "<L": 2084 return rhs - activity 2085 if sense in ">G": 2086 return activity - rhs 2087 if sense in "=E": 2088 return abs(activity - rhs) 2089 2090 return None 2091 2092 # Variable-related getters/setters 2093 def var_get_lb(self, var: "Var") -> numbers.Real: 2094 x = cbclib.Osi_getColLower(self.osi) 2095 return x[var.idx] 2096 2097 def var_set_lb(self, var: "Var", value: numbers.Real): 2098 cbclib.Osi_setColLower(self.osi, var.idx, value) 2099 2100 def var_get_ub(self, var: "Var") -> numbers.Real: 2101 x = cbclib.Osi_getColUpper(self.osi) 2102 return x[var.idx] 2103 2104 def var_set_ub(self, var: "Var", value: numbers.Real): 2105 cbclib.Osi_setColUpper(self.osi, var.idx, value) 2106 2107 def var_get_obj(self, var: "Var") -> numbers.Real: 2108 obj = cbclib.Osi_getObjCoefficients(self.osi) 2109 if obj == ffi.NULL: 2110 raise ParameterNotAvailable("Error getting objective function coefficients") 2111 return obj[var.idx] 2112 2113 def var_set_obj(self, var: "Var", value: numbers.Real): 2114 cbclib.Osi_setObjCoef(self.osi, var.idx, value) 2115 2116 def var_get_var_type(self, var: "Var") -> str: 2117 isInt = cbclib.Osi_isInteger(self.osi, var.idx) 2118 if isInt: 2119 lb = self.var_get_lb(var) 2120 ub = self.var_get_ub(var) 2121 if abs(lb) <= 1e-15 and abs(ub - 1.0) <= 1e-15: 2122 return BINARY 2123 2124 return INTEGER 2125 2126 return CONTINUOUS 2127 2128 def var_set_var_type(self, var: "Var", value: str): 2129 cv = var.var_type 2130 if value == cv: 2131 return 2132 if cv == CONTINUOUS: 2133 if value in (INTEGER, BINARY): 2134 cbclib.Osi_setInteger(self.osi, var.idx) 2135 else: 2136 if value == CONTINUOUS: 2137 cbclib.Osi_setContinuous(self.osi, var.idx) 2138 if value == BINARY: 2139 # checking bounds 2140 if var.lb != 0.0: 2141 var.lb = 0.0 2142 if var.ub != 1.0: 2143 var.ub = 1.0 2144 2145 def var_get_column(self, var: "Var") -> Column: 2146 numnz = cbclib.Cbc_getColNz(self.osi, var.idx) 2147 2148 cidx = cbclib.Cbc_getColIndices(self.osi, var.idx) 2149 if cidx == ffi.NULL: 2150 raise ParameterNotAvailable("Error getting column indices'") 2151 ccoef = cbclib.Cbc_getColCoeffs(self.osi, var.idx) 2152 2153 col = Column() 2154 2155 for i in range(numnz): 2156 col.constrs.append(Constr(self.model, cidx[i])) 2157 col.coeffs.append(ccoef[i]) 2158 2159 return col 2160 2161 def var_set_column(self, var: "Var", value: Column): 2162 raise NotImplementedError("Not available in OsiSolver") 2163 2164 def var_get_rc(self, var: "Var") -> numbers.Real: 2165 return self.__rc[var.idx] 2166 2167 def var_get_x(self, var: "Var") -> numbers.Real: 2168 return self.__x[var.idx] 2169 2170 def var_get_xi(self, var: "Var", i: int) -> numbers.Real: 2171 raise NotImplementedError("Solution pool not supported in OsiSolver") 2172 2173 def var_get_name(self, idx: int) -> str: 2174 namep = self.__name_space 2175 cbclib.Osi_getColName(self.osi, idx, namep, MAX_NAME_SIZE) 2176 return ffi.string(namep).decode("utf-8") 2177 2178 def remove_vars(self, varsList: List[int]): 2179 raise NotImplementedError("Not supported in OsiSolver") 2180 2181 def var_get_index(self, name: str) -> int: 2182 if self.colNames is None: 2183 self.colNames = {} 2184 for i in range(self.num_cols()): 2185 self.colNames[self.var_get_name(i)] = i 2186 2187 if name in self.colNames: 2188 return self.colNames[name] 2189 2190 return -1 2191 2192 def get_problem_name(self) -> str: 2193 raise NotImplementedError("Not supported in OsiSolver") 2194 2195 def set_problem_name(self, name: str): 2196 raise NotImplementedError("Not supported in OsiSolver") 2197 2198 2199# vim: ts=4 sw=4 et 2200