1# PuLP : Python LP Modeler 2# Version 1.4.2 3 4# Copyright (c) 2002-2005, Jean-Sebastien Roy (js@jeannot.org) 5# Modifications Copyright (c) 2007- Stuart Anthony Mitchell (s.mitchell@auckland.ac.nz) 6# $Id:solvers.py 1791 2008-04-23 22:54:34Z smit023 $ 7 8# Permission is hereby granted, free of charge, to any person obtaining a 9# copy of this software and associated documentation files (the 10# "Software"), to deal in the Software without restriction, including 11# without limitation the rights to use, copy, modify, merge, publish, 12# distribute, sublicense, and/or sell copies of the Software, and to 13# permit persons to whom the Software is furnished to do so, subject to 14# the following conditions: 15 16# The above copyright notice and this permission notice shall be included 17# in all copies or substantial portions of the Software. 18 19# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 20# OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 21# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 22# IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY 23# CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, 24# TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 25# SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.""" 26 27""" 28This file contains the solver classes for PuLP 29Note that the solvers that require a compiled extension may not work in 30the current version 31""" 32 33import os 34import sys 35 36 37if os.name == "posix": 38 from ..utilities import resource_clock as clock 39else: 40 try: 41 from time import monotonic as clock 42 except ImportError: 43 from time import clock 44 45try: 46 import configparser 47except ImportError: 48 import ConfigParser as configparser 49try: 50 Parser = configparser.ConfigParser 51except AttributeError: 52 Parser = configparser.SafeConfigParser 53from .. import sparse 54from .. import constants as const 55 56import logging 57 58try: 59 import ujson as json 60except ImportError: 61 import json 62 63log = logging.getLogger(__name__) 64 65if os.name == "posix" and sys.version_info[0] < 3: 66 try: 67 import subprocess32 as subprocess 68 except ImportError: 69 log.debug( 70 "Thread-safe subprocess32 module not found! " 71 "Using unsafe built-in subprocess module instead." 72 ) 73 import subprocess 74else: 75 import subprocess 76 77if sys.version_info[0] < 3: 78 devnull = open(os.devnull, "wb") 79 to_string = lambda _obj: str(_obj) 80else: 81 devnull = subprocess.DEVNULL 82 to_string = lambda _obj: str(_obj).encode() 83 84from uuid import uuid4 85 86 87class PulpSolverError(const.PulpError): 88 """ 89 Pulp Solver-related exceptions 90 """ 91 92 pass 93 94 95# import configuration information 96def initialize(filename, operating_system="linux", arch="64"): 97 """reads the configuration file to initialise the module""" 98 here = os.path.dirname(filename) 99 config = Parser({"here": here, "os": operating_system, "arch": arch}) 100 config.read(filename) 101 102 try: 103 cplex_dll_path = config.get("locations", "CplexPath") 104 except configparser.Error: 105 cplex_dll_path = "libcplex110.so" 106 try: 107 try: 108 ilm_cplex_license = ( 109 config.get("licenses", "ilm_cplex_license") 110 .decode("string-escape") 111 .replace('"', "") 112 ) 113 except AttributeError: 114 ilm_cplex_license = config.get("licenses", "ilm_cplex_license").replace( 115 '"', "" 116 ) 117 except configparser.Error: 118 ilm_cplex_license = "" 119 try: 120 ilm_cplex_license_signature = config.getint( 121 "licenses", "ilm_cplex_license_signature" 122 ) 123 except configparser.Error: 124 ilm_cplex_license_signature = 0 125 try: 126 coinMP_path = config.get("locations", "CoinMPPath").split(", ") 127 except configparser.Error: 128 coinMP_path = ["libCoinMP.so"] 129 try: 130 gurobi_path = config.get("locations", "GurobiPath") 131 except configparser.Error: 132 gurobi_path = "/opt/gurobi201/linux32/lib/python2.5" 133 try: 134 cbc_path = config.get("locations", "CbcPath") 135 except configparser.Error: 136 cbc_path = "cbc" 137 try: 138 glpk_path = config.get("locations", "GlpkPath") 139 except configparser.Error: 140 glpk_path = "glpsol" 141 try: 142 pulp_cbc_path = config.get("locations", "PulpCbcPath") 143 except configparser.Error: 144 pulp_cbc_path = "cbc" 145 try: 146 scip_path = config.get("locations", "ScipPath") 147 except configparser.Error: 148 scip_path = "scip" 149 for i, path in enumerate(coinMP_path): 150 if not os.path.dirname(path): 151 # if no pathname is supplied assume the file is in the same directory 152 coinMP_path[i] = os.path.join(os.path.dirname(config_filename), path) 153 return ( 154 cplex_dll_path, 155 ilm_cplex_license, 156 ilm_cplex_license_signature, 157 coinMP_path, 158 gurobi_path, 159 cbc_path, 160 glpk_path, 161 pulp_cbc_path, 162 scip_path, 163 ) 164 165 166# pick up the correct config file depending on operating system 167PULPCFGFILE = "pulp.cfg" 168is_64bits = sys.maxsize > 2 ** 32 169if is_64bits: 170 arch = "64" 171else: 172 arch = "32" 173operating_system = None 174if sys.platform in ["win32", "cli"]: 175 operating_system = "win" 176 PULPCFGFILE += ".win" 177elif sys.platform in ["darwin"]: 178 operating_system = "osx" 179 arch = "64" 180 PULPCFGFILE += ".osx" 181elif sys.platform in ['dragonfly']: 182 operating_system = "dragonfly" 183 PULPCFGFILE += ".dragonfly" 184else: 185 operating_system = "linux" 186 PULPCFGFILE += ".linux" 187 188DIRNAME = os.path.dirname(__file__) 189config_filename = os.path.join(DIRNAME, "..", PULPCFGFILE) 190( 191 cplex_dll_path, 192 ilm_cplex_license, 193 ilm_cplex_license_signature, 194 coinMP_path, 195 gurobi_path, 196 cbc_path, 197 glpk_path, 198 pulp_cbc_path, 199 scip_path, 200) = initialize(config_filename, operating_system, arch) 201 202 203class LpSolver: 204 """A generic LP Solver""" 205 206 name = "LpSolver" 207 208 def __init__( 209 self, mip=True, msg=True, options=None, timeLimit=None, *args, **kwargs 210 ): 211 """ 212 :param bool mip: if False, assume LP even if integer variables 213 :param bool msg: if False, no log is shown 214 :param list options: 215 :param float timeLimit: maximum time for solver (in seconds) 216 :param args: 217 :param kwargs: optional named options to pass to each solver, 218 e.g. gapRel=0.1, gapAbs=10, logPath="", 219 """ 220 if options is None: 221 options = [] 222 self.mip = mip 223 self.msg = msg 224 self.options = options 225 self.timeLimit = timeLimit 226 227 # this keeps the solver time in cpu time 228 self.solution_time = 0 229 230 # here we will store all other relevant information including: 231 # gapRel, gapAbs, maxMemory, maxNodes, threads, logPath, timeMode 232 self.optionsDict = {k: v for k, v in kwargs.items() if v is not None} 233 234 def available(self): 235 """True if the solver is available""" 236 raise NotImplementedError 237 238 def actualSolve(self, lp): 239 """Solve a well formulated lp problem""" 240 raise NotImplementedError 241 242 def actualResolve(self, lp, **kwargs): 243 """ 244 uses existing problem information and solves the problem 245 If it is not implemented in the solver 246 just solve again 247 """ 248 self.actualSolve(lp, **kwargs) 249 250 def copy(self): 251 """Make a copy of self""" 252 253 aCopy = self.__class__() 254 aCopy.mip = self.mip 255 aCopy.msg = self.msg 256 aCopy.options = self.options 257 return aCopy 258 259 def solve(self, lp): 260 """Solve the problem lp""" 261 # Always go through the solve method of LpProblem 262 return lp.solve(self) 263 264 # TODO: Not sure if this code should be here or in a child class 265 def getCplexStyleArrays( 266 self, lp, senseDict=None, LpVarCategories=None, LpObjSenses=None, infBound=1e20 267 ): 268 """returns the arrays suitable to pass to a cdll Cplex 269 or other solvers that are similar 270 271 Copyright (c) Stuart Mitchell 2007 272 """ 273 if senseDict is None: 274 senseDict = { 275 const.LpConstraintEQ: "E", 276 const.LpConstraintLE: "L", 277 const.LpConstraintGE: "G", 278 } 279 if LpVarCategories is None: 280 LpVarCategories = {const.LpContinuous: "C", const.LpInteger: "I"} 281 if LpObjSenses is None: 282 LpObjSenses = {const.LpMaximize: -1, const.LpMinimize: 1} 283 284 import ctypes 285 286 rangeCount = 0 287 variables = list(lp.variables()) 288 numVars = len(variables) 289 # associate each variable with a ordinal 290 self.v2n = dict(((variables[i], i) for i in range(numVars))) 291 self.vname2n = dict(((variables[i].name, i) for i in range(numVars))) 292 self.n2v = dict((i, variables[i]) for i in range(numVars)) 293 # objective values 294 objSense = LpObjSenses[lp.sense] 295 NumVarDoubleArray = ctypes.c_double * numVars 296 objectCoeffs = NumVarDoubleArray() 297 # print "Get objective Values" 298 for v, val in lp.objective.items(): 299 objectCoeffs[self.v2n[v]] = val 300 # values for variables 301 objectConst = ctypes.c_double(0.0) 302 NumVarStrArray = ctypes.c_char_p * numVars 303 colNames = NumVarStrArray() 304 lowerBounds = NumVarDoubleArray() 305 upperBounds = NumVarDoubleArray() 306 initValues = NumVarDoubleArray() 307 for v in lp.variables(): 308 colNames[self.v2n[v]] = to_string(v.name) 309 initValues[self.v2n[v]] = 0.0 310 if v.lowBound != None: 311 lowerBounds[self.v2n[v]] = v.lowBound 312 else: 313 lowerBounds[self.v2n[v]] = -infBound 314 if v.upBound != None: 315 upperBounds[self.v2n[v]] = v.upBound 316 else: 317 upperBounds[self.v2n[v]] = infBound 318 # values for constraints 319 numRows = len(lp.constraints) 320 NumRowDoubleArray = ctypes.c_double * numRows 321 NumRowStrArray = ctypes.c_char_p * numRows 322 NumRowCharArray = ctypes.c_char * numRows 323 rhsValues = NumRowDoubleArray() 324 rangeValues = NumRowDoubleArray() 325 rowNames = NumRowStrArray() 326 rowType = NumRowCharArray() 327 self.c2n = {} 328 self.n2c = {} 329 i = 0 330 for c in lp.constraints: 331 rhsValues[i] = -lp.constraints[c].constant 332 # for ranged constraints a<= constraint >=b 333 rangeValues[i] = 0.0 334 rowNames[i] = to_string(c) 335 rowType[i] = to_string(senseDict[lp.constraints[c].sense]) 336 self.c2n[c] = i 337 self.n2c[i] = c 338 i = i + 1 339 # return the coefficient matrix as a series of vectors 340 coeffs = lp.coefficients() 341 sparseMatrix = sparse.Matrix(list(range(numRows)), list(range(numVars))) 342 for var, row, coeff in coeffs: 343 sparseMatrix.add(self.c2n[row], self.vname2n[var], coeff) 344 ( 345 numels, 346 mystartsBase, 347 mylenBase, 348 myindBase, 349 myelemBase, 350 ) = sparseMatrix.col_based_arrays() 351 elemBase = ctypesArrayFill(myelemBase, ctypes.c_double) 352 indBase = ctypesArrayFill(myindBase, ctypes.c_int) 353 startsBase = ctypesArrayFill(mystartsBase, ctypes.c_int) 354 lenBase = ctypesArrayFill(mylenBase, ctypes.c_int) 355 # MIP Variables 356 NumVarCharArray = ctypes.c_char * numVars 357 columnType = NumVarCharArray() 358 if lp.isMIP(): 359 for v in lp.variables(): 360 columnType[self.v2n[v]] = to_string(LpVarCategories[v.cat]) 361 self.addedVars = numVars 362 self.addedRows = numRows 363 return ( 364 numVars, 365 numRows, 366 numels, 367 rangeCount, 368 objSense, 369 objectCoeffs, 370 objectConst, 371 rhsValues, 372 rangeValues, 373 rowType, 374 startsBase, 375 lenBase, 376 indBase, 377 elemBase, 378 lowerBounds, 379 upperBounds, 380 initValues, 381 colNames, 382 rowNames, 383 columnType, 384 self.n2v, 385 self.n2c, 386 ) 387 388 def toDict(self): 389 data = dict(solver=self.name) 390 for k in ["mip", "msg", "keepFiles"]: 391 try: 392 data[k] = getattr(self, k) 393 except AttributeError: 394 pass 395 for k in ["timeLimit", "options"]: 396 # with these ones, we only export if it has some content: 397 try: 398 value = getattr(self, k) 399 if value: 400 data[k] = value 401 except AttributeError: 402 pass 403 data.update(self.optionsDict) 404 return data 405 406 to_dict = toDict 407 408 def toJson(self, filename, *args, **kwargs): 409 with open(filename, "w") as f: 410 json.dump(self.toDict(), f, *args, **kwargs) 411 412 to_json = toJson 413 414 415class LpSolver_CMD(LpSolver): 416 """A generic command line LP Solver""" 417 418 name = "LpSolver_CMD" 419 420 def __init__(self, path=None, keepFiles=False, *args, **kwargs): 421 """ 422 423 :param bool mip: if False, assume LP even if integer variables 424 :param bool msg: if False, no log is shown 425 :param list options: list of additional options to pass to solver (format depends on the solver) 426 :param float timeLimit: maximum time for solver (in seconds) 427 :param str path: a path to the solver binary 428 :param bool keepFiles: if True, files are saved in the current directory and not deleted after solving 429 :param args: parameters to pass to :py:class:`LpSolver` 430 :param kwargs: parameters to pass to :py:class:`LpSolver` 431 """ 432 LpSolver.__init__(self, *args, **kwargs) 433 if path is None: 434 self.path = self.defaultPath() 435 else: 436 self.path = path 437 self.keepFiles = keepFiles 438 self.setTmpDir() 439 440 def copy(self): 441 """Make a copy of self""" 442 443 aCopy = LpSolver.copy(self) 444 aCopy.path = self.path 445 aCopy.keepFiles = self.keepFiles 446 aCopy.tmpDir = self.tmpDir 447 return aCopy 448 449 def setTmpDir(self): 450 """Set the tmpDir attribute to a reasonnable location for a temporary 451 directory""" 452 if os.name != "nt": 453 # On unix use /tmp by default 454 self.tmpDir = os.environ.get("TMPDIR", "/tmp") 455 self.tmpDir = os.environ.get("TMP", self.tmpDir) 456 else: 457 # On Windows use the current directory 458 self.tmpDir = os.environ.get("TMPDIR", "") 459 self.tmpDir = os.environ.get("TMP", self.tmpDir) 460 self.tmpDir = os.environ.get("TEMP", self.tmpDir) 461 if not os.path.isdir(self.tmpDir): 462 self.tmpDir = "" 463 elif not os.access(self.tmpDir, os.F_OK + os.W_OK): 464 self.tmpDir = "" 465 466 def create_tmp_files(self, name, *args): 467 if self.keepFiles: 468 prefix = name 469 else: 470 prefix = os.path.join(self.tmpDir, uuid4().hex) 471 return ("%s-pulp.%s" % (prefix, n) for n in args) 472 473 def delete_tmp_files(self, *args): 474 if self.keepFiles: 475 return 476 for file in args: 477 try: 478 os.remove(file) 479 except: 480 pass 481 482 def defaultPath(self): 483 raise NotImplementedError 484 485 def executableExtension(name): 486 if os.name != "nt": 487 return name 488 else: 489 return name + ".exe" 490 491 executableExtension = staticmethod(executableExtension) 492 493 def executable(command): 494 """Checks that the solver command is executable, 495 And returns the actual path to it.""" 496 497 if os.path.isabs(command): 498 if os.path.exists(command) and os.access(command, os.X_OK): 499 return command 500 for path in os.environ.get("PATH", []).split(os.pathsep): 501 new_path = os.path.join(path, command) 502 if os.path.exists(new_path) and os.access(new_path, os.X_OK): 503 return os.path.join(path, command) 504 return False 505 506 executable = staticmethod(executable) 507 508 509try: 510 import ctypes 511 512 def ctypesArrayFill(myList, type=ctypes.c_double): 513 """ 514 Creates a c array with ctypes from a python list 515 type is the type of the c array 516 """ 517 ctype = type * len(myList) 518 cList = ctype() 519 for i, elem in enumerate(myList): 520 cList[i] = elem 521 return cList 522 523 524except (ImportError): 525 526 def ctypesArrayFill(myList, type=None): 527 return None 528