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