source: coopr.plugins/trunk/coopr/plugins/solvers/GLPK.py @ 5654

Revision 5654, 18.4 KB checked in by gabeh, 2 years ago (diff)

Fixing typo in GLPK.py

Line 
1#  _________________________________________________________________________
2#
3#  Coopr: A COmmon Optimization Python Repository
4#  Copyright (c) 2008 Sandia Corporation.
5#  This software is distributed under the BSD License.
6#  Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
7#  the U.S. Government retains certain rights in this software.
8#  For more information, see the Coopr README.txt file.
9#  _________________________________________________________________________
10
11import logging
12import os
13import re
14
15from coopr.opt import *
16#from coopr.opt.base import ProblemFormat as PF, ResultsFormat as RF
17#from coopr.opt.results import ProblemSense as PS, SolverResults, \
18                              #SolutionStatus, SolverStatus, TerminationCondition
19from coopr.opt.solver import SystemCallSolver
20
21from pyutilib.common import ApplicationError
22import pyutilib.component.core
23from pyutilib.misc import Bunch, Options
24from pyutilib.services import register_executable, registered_executable
25from pyutilib.services import TempfileManager
26
27Logger = logging.getLogger('coopr.plugins')
28
29glpk_file_flag=None
30
31def configure_glpk():
32    global glpk_file_flag
33    if glpk_file_flag is not None:
34        return
35    glpk_file_flag = False
36    if registered_executable("glpsol") is None:
37        return
38    errcode, results = pyutilib.subprocess.run(
39        [registered_executable('glpsol').get_path(), "--version"])
40    if errcode == 0:
41        lines = results.split('\n')
42        if len(lines) == 0:
43            return
44        m = re.search('(\d+)\.(\d+)', lines[0].split()[-1])
45        if m:
46            _version = tuple(int(i) for i in m.groups())
47            glpk_file_flag = _version >= (4,42)
48
49
50# Not sure how better to get these constants, but pulled from GLPK
51# documentation and source code (include/glpk.h)
52
53   # status of auxiliary / structural variables
54GLP_BS = 1   # inactive constraint / basic variable
55GLP_NL = 2   # active constraint or non-basic variable on lower bound
56GLP_NU = 3   # active constraint or non-basic variable on upper bound
57GLP_NF = 4   # active free row or non-basic free variable
58GLP_NS = 5   # active equality constraint or non-basic fixed variable
59
60   # solution status
61GLP_UNDEF  = 1  # solution is undefined
62GLP_FEAS   = 2  # solution is feasible
63GLP_INFEAS = 3  # solution is infeasible
64GLP_NOFEAS = 4  # no feasible solution exists
65GLP_OPT    = 5  # solution is optimal
66GLP_UNBND  = 6  # solution is unbounded
67
68
69class GLPK(OptSolver):
70    """The GLPK LP/MIP solver"""
71
72    pyutilib.component.core.alias('glpk', doc='The GLPK MIP solver')
73
74    def __new__(cls, *args, **kwds):
75        try:
76            mode = kwds['solver_io']
77            if mode is None:
78                mode = 'lp'
79            del kwds['solver_io']
80        except KeyError:
81            mode = 'lp'
82        #
83        if mode  == 'lp':
84            if glpk_file_flag:
85                return SolverFactory('_glpk_shell', **kwds)
86            else:
87                return SolverFactory('_glpk_shell_old', **kwds)
88        if mode == 'python':
89            opt = SolverFactory('_glpk_direct', **kwds)
90            if opt is None:
91                logging.getLogger('coopr.plugins').error('Python API for GLPK is not installed')
92                return
93            return opt
94        #
95        if mode == 'os':
96            opt = SolverFactory('_ossolver', **kwds)
97        else:
98            logging.getLogger('coopr.plugins').error('Unknown IO type: %s' % mode)
99            return
100        opt.set_options('solver=glpsol')
101        return opt
102
103
104class GLPKSHELL ( SystemCallSolver ):
105    """Shell interface to the GLPK LP/MIP solver"""
106
107    pyutilib.component.core.alias('_glpk_shell', doc='Shell interface to the GNU Linear Programming Kit')
108
109    def __init__ ( self, **kwargs ):
110        #
111        # Call base constructor
112        #
113        kwargs['type'] = 'glpk'
114        SystemCallSolver.__init__( self, **kwargs )
115        #
116        # Valid problem formats, and valid results for each format
117        #
118        self._valid_problem_formats = [ ProblemFormat.cpxlp, ProblemFormat.mps, ProblemFormat.mod ]
119        self._valid_result_formats = {
120          ProblemFormat.mod:   ResultsFormat.soln,
121          ProblemFormat.cpxlp: ResultsFormat.soln,
122          ProblemFormat.mps:   ResultsFormat.soln,
123        }
124
125        # Note: Undefined capabilities default to 'None'
126        self._capabilities = Options()
127        self._capabilities.linear = True
128        self._capabilities.integer = True
129        self._capabilities.sos1 = False
130        self._capabilities.sos2 = False
131        self._capabilities.sosn = False
132
133    def executable ( self ):
134        executable = registered_executable('glpsol')
135        if executable is None:
136            msg = "Could not locate the 'glpsol' executable, which is "          \
137                  "required for solver '%s'"
138            pyutilib.component.core.PluginGlobals.env().log.error(msg % self.name)
139            self.enable = False
140            return None
141
142        return executable.get_path()
143
144
145    def create_command_line ( self, executable, problem_files ):
146        #
147        # Define log file
148        #
149        if self.log_file is None:
150            self.log_file = TempfileManager.create_tempfile(suffix='.glpk.log')
151
152        #
153        # Define solution file
154        #
155        if self.soln_file is None:
156            self.soln_file = \
157                 TempfileManager.create_tempfile(suffix='.glpk.soln')
158        self._glpfile = TempfileManager.create_tempfile(suffix='.glpk.glp')
159        self._rawfile = TempfileManager.create_tempfile(suffix='.glpk.raw')
160
161        #
162        # Define results file
163        #
164        if self._results_format is None or self._results_format == ResultsFormat.soln:
165            self.results_file = self.soln_file
166
167        #
168        # Define command line
169        #
170        cmd = [executable]
171        if self._timer:
172            cmd.insert(0, self._timer)
173        for key in self.options:
174            opt = self.options[ key ]
175            cmd.extend(["--%s" % key, str(opt)])
176            #if isinstance(opt, basestring) and ' ' in opt:
177            #    cmd.append('--%s "%s"' % (key, str(opt)) )
178            #else:
179            #    cmd.append('--%s %s' % (key, str(opt)) )
180
181        if self._timelimit is not None and self._timelimit > 0.0:
182            cmd.extend(['--tmlim', str(self._timelimit)])
183
184        cmd.extend(['--write', self._rawfile])
185        cmd.extend(['--wglp', self._glpfile])
186
187        if self._problem_format == ProblemFormat.cpxlp:
188            cmd.extend(['--cpxlp', problem_files[0]])
189        elif self._problem_format == ProblemFormat.mps:
190            cmd.extend(['--freemps', problem_files[0]])
191        elif self._problem_format == ProblemFormat.mod:
192            cmd.extend(['--math', problem_files[0]])
193            for fname in problem_files[1:]:
194                cmd.extend(['--data', fname])
195
196        return Bunch(cmd=cmd, log_file=self.log_file, env=None)
197
198
199    def process_logfile(self):
200        """
201        Process logfile
202        """
203        results = SolverResults()
204
205          # For the lazy programmer, handle long variable names
206        prob   = results.problem
207        solv   = results.solver
208        solv.termination_condition = TerminationCondition.unknown
209        stats  = results.solver.statistics
210        bbound = stats.branch_and_bound
211
212        prob.upper_bound = float('inf')
213        prob.lower_bound = float('-inf')
214        bbound.number_of_created_subproblems = 0
215        bbound.number_of_bounded_subproblems = 0
216
217        with open( self.log_file, 'r' ) as output:
218            for line in output:
219                toks = line.split()
220                if 'tree is empty' in line:
221                    bbound.number_of_created_subproblems = toks[-1][:-1]
222                    bbound.number_of_bounded_subproblems = toks[-1][:-1]
223                elif len(toks) == 2 and toks[0] == "sys":
224                    solv.system_time = toks[1]
225                elif len(toks) == 2 and toks[0] == "user":
226                    solv.user_time = toks[1]
227                elif len(toks) > 2 and (toks[0], toks[2]) == ("TIME", "EXCEEDED;"):
228                    solv.termination_condition = TerminationCondition.maxTimeLimit
229                elif len(toks) > 5 and (toks[:6] == ['PROBLEM', 'HAS', 'NO', 'DUAL', 'FEASIBLE', 'SOLUTION']):
230                    solv.termination_condition = TerminationCondition.unbounded
231                elif len(toks) > 5 and (toks[:6] == ['PROBLEM', 'HAS', 'NO', 'PRIMAL', 'FEASIBLE', 'SOLUTION']):
232                    solv.termination_condition = TerminationCondition.infeasible
233                elif len(toks) > 4 and (toks[:5] == ['PROBLEM', 'HAS', 'NO', 'FEASIBLE', 'SOLUTION']):
234                    solv.termination_condition = TerminationCondition.infeasible
235                elif len(toks) > 6 and (toks[:7] == ['LP', 'RELAXATION', 'HAS', 'NO', 'DUAL', 'FEASIBLE', 'SOLUTION']):
236                    solv.termination_condition = TerminationCondition.unbounded
237
238        return results
239
240
241    def _glpk_get_solution_status ( self, status ):
242        if   GLP_OPT    == status: return SolutionStatus.optimal
243        elif GLP_FEAS   == status: return SolutionStatus.feasible
244        elif GLP_INFEAS == status: return SolutionStatus.infeasible
245        elif GLP_NOFEAS == status: return SolutionStatus.infeasible
246        elif GLP_UNBND  == status: return SolutionStatus.unbounded
247        elif GLP_UNDEF  == status: return SolutionStatus.other
248        raise RuntimeError, "Unknown solution status returned by GLPK solver"
249
250
251    def process_soln_file ( self, results ):
252        pdata = self._glpfile
253        psoln = self._rawfile
254
255        prob = results.problem
256        solv = results.solver
257
258        prob.name = 'unknown'   # will ostensibly get updated
259
260        # Step 1: Make use of the GLPK's machine parseable format (--wglp) to
261        #    collect variable and constraint names.
262        glp_line_count = ' -- File not yet opened'
263
264        # The trick for getting the variable names correctly matched to their
265        # values is the note that the --wglp option outputs them in the same
266        # order as the --write output.
267        # Note that documentation for these formats is available from the GLPK
268        # documentation of 'glp_read_prob' and 'glp_write_sol'
269        variable_names = dict()    # cols
270        constraint_names = dict()  # rows
271        obj_name = 'objective'
272
273        try:
274            f = open( pdata, 'r')
275
276            glp_line_count = 1
277            pprob, ptype, psense, prows, pcols, pnonz = f.readline().split()
278            prows = int( prows )  # fails if not a number; intentional
279            pcols = int( pcols )  # fails if not a number; intentional
280            pnonz = int( pnonz )  # fails if not a number; intentional
281
282            if pprob != 'p' or \
283               ptype not in ('lp', 'mip') or \
284               psense not in ('max', 'min') or \
285               prows < 0 or pcols < 0 or pnonz < 0:
286                raise ValueError
287
288            self.is_integer = ( 'mip' == ptype and True or False )
289            prob.sense = 'min' == psense and ProblemSense.minimize or ProblemSense.maximize
290            prob.number_of_constraints = prows
291            prob.number_of_nonzeros    = pnonz
292            prob.number_of_variables   = pcols
293
294            extract_duals = False
295            for suffix in self.suffixes:
296                if re.match(suffix, "dual"):
297                    if self.is_integer:
298                        if suffix == 'dual':
299                            raise RuntimeError, 'Request for duals of an integer problem.'
300                    else:
301                        extract_duals = True
302
303            for line in f:
304                glp_line_count += 1
305                tokens = line.split()
306                switch = tokens.pop(0)
307
308                if switch in ('a', 'e', 'i', 'j'):
309                    pass
310                elif 'n' == switch:  # naming some attribute
311                    ntype = tokens.pop(0)
312                    name  = tokens.pop()
313                    if 'i' == ntype:      # row
314                        row = tokens.pop()
315                        constraint_names[ int(row) ] = name
316                        # --write order == --wglp order; store name w/ row no
317                    elif 'j' == ntype:    # var
318                        col = tokens.pop()
319                        variable_names[ int(col) ] = name
320                        # --write order == --wglp order; store name w/ col no
321                    elif 'z' == ntype:    # objective
322                        obj_name = name
323                    elif 'p' == ntype:    # problem name
324                        prob_name = name
325                    else:                 # anything else is incorrect.
326                        raise ValueError
327
328                else:
329                    raise ValueError
330
331            f.close()
332        except Exception, e:
333            msg = "Error parsing solution description file, line %s: %s"
334            raise ValueError, msg % (glp_line_count, str(e))
335
336
337        # Step 2: Make use of the GLPK's machine parseable format (--write) to
338        #    collect solution variable and constraint values.
339        raw_line_count = ' -- File not yet opened'
340        try:
341            f = open( psoln, 'r')
342
343            raw_line_count = 1
344            prows, pcols = f.readline().split()
345            prows = int( prows )  # fails if not a number; intentional
346            pcols = int( pcols )  # fails if not a number; intentional
347
348            raw_line_count = 2
349            if self.is_integer:
350                pstat, obj_val = f.readline().split()
351            else:
352                pstat, dstat, obj_val = f.readline().split()
353                dstat = float( dstat ) # dual status of basic solution.  Ignored.
354            #print "HERE", pstat, obj_val, self.is_integer
355
356            pstat = float( pstat )       # fails if not a number; intentional
357            obj_val = float( obj_val )   # fails if not a number; intentional
358            soln_status = self._glpk_get_solution_status( pstat )
359
360            #print "HEREZ", soln_status
361            if soln_status is SolutionStatus.infeasible:
362                solv.termination_condition = TerminationCondition.infeasible
363
364            elif soln_status is SolutionStatus.unbounded:
365                solv.termination_condition = TerminationCondition.unbounded
366
367            elif soln_status is SolutionStatus.other:
368                if solv.termination_condition == TerminationCondition.unknown:
369                    solv.termination_condition = TerminationCondition.other
370
371            elif soln_status in ( SolutionStatus.optimal, SolutionStatus.feasible ):
372                soln   = results.solution.add()
373                soln.status = soln_status
374
375                prob.lower_bound = obj_val
376                prob.upper_bound = obj_val
377
378                # TODO: Does a 'feasible' status mean that we're optimal?
379                soln.gap=0.0
380                solv.termination_condition = TerminationCondition.optimal
381               
382
383                # I'd like to choose the correct answer rather than just doing
384                # something like commenting the obj_name line.  The point is that
385                # we ostensibly could or should make use of the user's choice in
386                # objective name.  In that vein I'd like to set the objective value
387                # to the objective name.  This would make parsing on the user end
388                # less 'arbitrary', as in the yaml key 'f'.  Weird
389                soln.objective[ obj_name ] = obj_val
390
391                for mm in range( 1, prows +1 ):
392                    raw_line_count += 1
393                    if self.is_integer:
394                        rprim = f.readline()   # should be a single number
395                    else:
396                        rstat, rprim, rdual = f.readline().split()
397                        rstat = float( rstat )
398
399                    cname = constraint_names[ mm ]
400                    if 'ONE_VAR_CONSTANT' == cname[-16:]: continue
401                    rprim = float( rprim )
402                    soln.constraint[ cname ].value = rprim
403
404                    #print "HERE", extract_duals, self.is_integer
405                    if extract_duals and not self.is_integer:
406                        rdual = float(rdual)
407                        soln.constraint[ cname ].dual  = rdual
408
409                for nn in range( 1, pcols +1 ):
410                    raw_line_count += 1
411                    if self.is_integer:
412                        cprim = f.readline()      # should be a single number
413                    else:
414                        cstat, cprim, cdual = f.readline().split()
415                        cstat = float( cstat )  # fails if not a number; intentional
416
417                    vname = variable_names[ nn ]
418                    if 'ONE_VAR_CONSTANT' == vname: continue
419                    cprim = float( cprim )
420                    soln.variable[ vname ] = {"Value" : cprim, "Id" : len(soln.variable)}
421
422                    #if extract_duals and not self.is_integer:
423                    #       cdual = float(cdual)
424                    #       soln.variable[ vname ].dual  = cdual
425                    #       GLPK reports a dual for variables, though Pyomo does not have
426                    #       a place to put them
427
428            f.close()
429        except Exception, e:
430            print e
431            msg = "Error parsing solution data file, line %d" % raw_line_count
432            raise ValueError, msg
433
434
435#class MockGLPK(GLPK,mockmip.MockMIP):
436#       """A Mock GLPK solver used for testing
437#       """
438
439#       pyutilib.component.core.alias('_mock_glpk')
440
441#       def __init__(self, **kwds):
442#               try:
443#                  GLPK.__init__(self, **kwds)
444#               except ApplicationError: #pragma:nocover
445#                  pass                                         #pragma:nocover
446#               mockmip.MockMIP.__init__(self,"glpk")
447#
448#       def available(self, exception_flag=True):
449#               return GLPK.available(self,exception_flag)
450#
451#       def create_command_line(self,executable,problem_files):
452#               command = GLPK.create_command_line(self,executable,problem_files)
453#               mockmip.MockMIP.create_command_line(self,executable,problem_files)
454#               return command
455#
456#       def executable(self):
457#               return mockmip.MockMIP.executable(self)
458#
459#       def _execute_command(self,cmd):
460#               return mockmip.MockMIP._execute_command(self,cmd)
461#
462#       def _convert_problem(self,args,pformat,valid_pformats):
463#               if pformat in [ProblemFormat.mps,ProblemFormat.cpxlp]:
464#                  return (args,pformat,None)
465#               else:
466#                  return (args,ProblemFormat.cpxlp,None)
467
468
469register_executable( name='glpsol')
Note: See TracBrowser for help on using the repository browser.