source: coopr.plugins/trunk/coopr/plugins/mip/GLPK.py @ 2336

Last change on this file since 2336 was 2336, checked in by wehart, 10 years ago

Misc documentation update.

File size: 24.5 KB
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
11
12import os
13import re
14from coopr.opt.base import *
15from coopr.opt.results import *
16from coopr.opt.solver import *
17import mockmip
18import pyutilib.services
19import pyutilib.misc
20import pyutilib.common
21import pyutilib.component.core
22
23
24class GLPK(SystemCallSolver):
25    """The GLPK LP/MIP solver
26    """
27
28    def __init__(self, **kwds):
29        #
30        # Call base constructor
31        #
32        kwds['type'] = 'glpk'
33        SystemCallSolver.__init__(self, **kwds)
34        #
35        # Valid problem formats, and valid results for each format
36        #
37        self._valid_problem_formats=[ProblemFormat.mod, ProblemFormat.cpxlp, ProblemFormat.mps]
38        self._valid_result_formats={}
39        self._valid_result_formats[ProblemFormat.mod] = [ResultsFormat.soln]
40        self._valid_result_formats[ProblemFormat.cpxlp] = [ResultsFormat.soln]
41        self._valid_result_formats[ProblemFormat.mps] = [ResultsFormat.soln]
42
43    def executable(self):
44        executable = pyutilib.services.registered_executable("glpsol")
45        if executable is None:
46            pyutilib.component.core.PluginGlobals.env().log.error("Could not locate the 'glpsol' executable, which is required for solver %s" % self.name)
47            self.enable = False
48            return None
49        return executable.get_path()
50
51    def create_command_line(self,executable,problem_files):
52        #
53        # Define log file
54        #
55        if self.log_file is None:
56           self.log_file = pyutilib.services.TempfileManager.create_tempfile(suffix = '.glpk.log')
57
58        #
59        # Define solution file
60        #
61        if self.soln_file is None:
62            self.soln_file = pyutilib.services.TempfileManager.create_tempfile(suffix = '.glpk.soln')
63
64        #
65        # Define results file
66        #
67        if self._results_format is None or self._results_format == ResultsFormat.soln:
68           self.results_file = self.soln_file
69           
70        #
71        # Define command line
72        #
73        if self._timelimit is not None and self._timelimit > 0.0:
74           timing = " --tmlim "+str(self._timelimit)+" "
75        else:
76           timing = ""
77        if (self.mipgap is not None) and (self.mipgap > 0.0):
78           mipgap = " --mipgap "+str(self.mipgap)+" "
79        else:
80           mipgap = ""           
81        if self._problem_format == ProblemFormat.cpxlp:
82            problem=" --cpxlp " + problem_files[0]
83        elif self._problem_format == ProblemFormat.mps:
84            problem=" --freemps " + problem_files[0]
85        elif self._problem_format == ProblemFormat.mod:
86            problem=" --math " + problem_files[0]
87            for filename in problem_files[1:]:
88                problem += " --data " + filename
89        opt = ""
90        for key in self.options:
91            if isinstance(self.options[key],basestring) and ' ' in self.options[key]:
92                opt += " --"+key+" \""+str(self.options[key])+"\""
93            else:
94                opt += " --"+key+" "+str(self.options[key])
95        proc = self._timer + " " + executable + opt + " " + timing + mipgap + " --output " + self.soln_file + problem
96        return pyutilib.misc.Bunch(cmd=proc, log_file=self.log_file, env=None)
97
98    def process_logfile(self):
99        """
100        Process logfile
101        """
102        results = SolverResults()
103        #
104        # Initial values
105        #
106        #results.solver.statistics.branch_and_bound.number_of_created_subproblems=0
107        #results.solver.statistics.branch_and_bound.number_of_bounded_subproblems=0
108        soln = results.solution.add()
109        soln.objective['f']=float('inf')
110        #
111        # Process logfile
112        #
113        OUTPUT = open(self.log_file)
114        output = "".join(OUTPUT.readlines())
115        OUTPUT.close()
116        #
117        # Parse logfile lines
118        #
119        for line in output.split("\n"):
120          tokens = re.split('[ \t]+',line.strip())
121          if len(tokens) > 4 and tokens[1] == "objval":
122             soln.objective['f'] = tokens[3]
123          elif len(tokens) > 3 and tokens[0] == "Objective" and tokens[1] == "value":
124             soln.objective['f'] = tokens[3]
125          elif len(tokens) > 4 and tokens[0] == "!" and tokens[2] == "objval":
126             soln.objective['f'] = tokens[4]
127          elif len(tokens) > 4 and tokens[0] == "+" and tokens[2] == "objval":
128             soln.objective['f'] = tokens[4]
129          elif len(tokens) > 4 and tokens[0] == "*" and tokens[2] == "objval":
130             soln.objective['f'] = tokens[4]
131          elif len(tokens) > 4 and tokens[0] == "+" and tokens[2] == "mip" and tokens[4] == "not":
132             soln.objective['f'] = "unknown"
133             results.problem.lower_bound = tokens[8]
134          elif len(tokens) > 4 and tokens[0] == "+" and tokens[1] == "mip" and tokens[4] == "not":
135             soln.objective['f'] = "unknown"
136             results.problem.lower_bound = tokens[7]
137          elif len(tokens) > 4 and tokens[0] == "+" and tokens[2] == "mip" and tokens[4] != "not":
138             soln.objective['f'] = tokens[4]
139             if tokens[6] != "tree":
140                results.problem.lower_bound = tokens[6]
141          elif len(tokens) > 4 and tokens[0] == "+" and tokens[1] == "mip" and tokens[4] != "not":
142             soln.objective['f'] = tokens[3]
143             results.problem.lower_bound = tokens[5]
144          elif len(tokens) == 6 and tokens[0] == "OPTIMAL" and tokens[1] == "SOLUTION" and tokens[5] == "PRESOLVER":
145             results.solver.statistics.branch_and_bound.number_of_created_subproblems = 0
146             results.solver.statistics.branch_and_bound.number_of_bounded_subproblems = 0
147             soln.status = SolutionStatus.optimal
148          elif len(tokens) == 7 and tokens[1] == "OPTIMAL" and tokens[2] == "SOLUTION" and tokens[6] == "PRESOLVER":
149             results.solver.statistics.branch_and_bound.number_of_created_subproblems = 0
150             results.solver.statistics.branch_and_bound.number_of_bounded_subproblems = 0
151             soln.status = SolutionStatus.optimal
152          elif len(tokens) > 10 and tokens[0] == "+" and tokens[8] == "empty":
153             results.solver.statistics.branch_and_bound.number_of_created_subproblems = tokens[11][:-1]
154             results.solver.statistics.branch_and_bound.number_of_bounded_subproblems = tokens[11][:-1]
155          elif len(tokens) > 9 and tokens[0] == "+" and tokens[7] == "empty":
156             results.solver.statistics.branch_and_bound.number_of_created_subproblems = tokens[10][:-1]
157             results.solver.statistics.branch_and_bound.number_of_bounded_subproblems = tokens[10][:-1]
158          elif len(tokens) == 2 and tokens[0] == "sys":
159             results.solver.system_time=tokens[1]
160          elif len(tokens) == 2 and tokens[0] == "user":
161             results.solver.user_time=tokens[1]
162          elif len(tokens) > 2 and tokens[0] == "OPTIMAL" and tokens[1] == "SOLUTION":
163             soln.status = SolutionStatus.optimal
164          elif len(tokens) > 2 and tokens[0] == "INTEGER" and tokens[1] == "OPTIMAL":
165             soln.status = SolutionStatus.optimal
166          elif len(tokens) > 2 and tokens[0] == "TIME" and tokens[2] == "EXCEEDED;":
167             soln.status = SolutionStatus.stoppedByLimit
168        if results.problem.upper_bound == "inf":
169           results.problem.upper_bound = 'Infinity'
170        if results.problem.lower_bound == "-inf":
171           results.problem.lower_bound = "-Infinity"
172        try:
173            val = results.problem.upper_bound
174            tmp = eval(val.strip())
175            results.problem.upper_bound = str(tmp)
176        except:
177            pass
178        try:
179            val = results.problem.lower_bound
180            tmp = eval(val.strip())
181            results.problem.lower_bound = str(tmp)
182        except:
183            pass
184        try:
185            val = soln.objective['f'].value
186            tmp = eval(val.strip())
187            soln.objective['f'] = str(tmp)
188        except:
189            pass
190        if soln.status is SolutionStatus.optimal:
191           soln.gap=0.0
192        elif soln.status is SolutionStatus.stoppedByLimit:
193           soln.gap = "Infinity" # until proven otherwise
194           if "lower_bound" in dir(results.problem):
195              if results.problem.lower_bound is "-Infinity":
196                 soln.gap="Infinity"
197              elif not results.problem.lower_bound is None:
198                 if "upper_bound" not in dir(results.problem):
199                    gap="Infinity"
200                 elif results.problem.upper_bound is None:
201                    gap="Infinity"
202                 else:
203                    soln.gap=eval(soln.objective['f']) - eval(results.problem.lower_bound)
204           elif "upper_bound" in dir(results.problem):
205              if results.problem.upper_bound is "Infinity":
206                 soln.gap="Infinity"
207              elif not results.problem.upper_bound is None:
208                 soln.gap=eval(results.problem.upper_bound) - eval(soln.objective['f'])
209        if results.solver.status is SolverStatus.error:
210           results.solution.delete(0)
211        return results
212
213    def process_soln_file(self,results):
214
215        # the only suffixes that we extract from GLPK are
216        # constraint duals. scan through the solver suffix
217        # list and throw an exception if the user has
218        # specified any others.
219        extract_duals = False
220        for suffix in self.suffixes:
221            flag=False
222            if re.match(suffix,"dual"):
223                extract_duals = True
224                flag=True
225            if not flag:
226                raise RuntimeError,"***GLPK solver plugin cannot extract solution suffix="+suffix
227
228        lp_solution = True # if false, we're dealing with a MIP!
229        if not os.path.exists(self.soln_file):
230           return
231        soln = results.solution(0)
232        INPUT = open(self.soln_file,"r")
233       
234        state = 0 # 0=initial header, 1=constraints, 2=variables, -1=done
235       
236        results.problem.number_of_objectives = 1
237       
238        number_of_constraints_read = 0 # for validation of the total count read and the order
239        number_of_variables_read = 0
240        active_constraint_name = "" # constraint names and their value/bounds can be split across multiple lines
241        active_variable_name = "" # variable names and their value/bounds can be split across multiple lines
242       
243        for line in INPUT:
244          tokens = re.split('[ \t]+',line.strip())
245
246          if (len(tokens) == 1) and (len(tokens[0]) == 0):
247             pass
248          elif state == 0:
249             #
250             # Processing initial header
251             #
252             if len(tokens) == 2 and tokens[0] == "Problem:":
253                # the problem name may be absent, in which case the "Problem:" line will be skipped.
254                results.problem.name = tokens[1]
255             elif len(tokens) == 2 and tokens[0] == "Rows:":
256                results.problem.number_of_constraints = eval(tokens[1])
257             elif len(tokens) == 2 and tokens[0] == "Columns:":
258                lp_solution = True
259                results.problem.number_of_variables = eval(tokens[1])
260             elif len(tokens) > 2 and tokens[0] == "Columns:":
261                lp_solution = False
262                results.problem.number_of_variables = eval(tokens[1])               
263             elif len(tokens) == 2 and tokens[0] == "Non-zeros:":
264                results.problem.number_of_nonzeros = eval(tokens[1])
265             elif len(tokens) >= 2 and tokens[0] == "Status:":
266                if tokens[1] == "OPTIMAL":
267                   soln.status = SolutionStatus.optimal
268                elif len(tokens) == 3 and tokens[1] == "INTEGER" and tokens[2] == "NON-OPTIMAL":
269                   soln.status = SolutionStatus.bestSoFar
270                elif len(tokens) == 3 and tokens[1] == "INTEGER" and tokens[2] == "OPTIMAL":
271                   soln.status = SolutionStatus.optimal
272                elif len(tokens) == 3 and tokens[1] == "INTEGER" and tokens[2] == "UNDEFINED":
273                   soln.status = SolutionStatus.stoppedByLimit
274                else:
275                   print "GLPK WARNING: unknown status: "+" ".join(tokens[1:])
276             elif len(tokens) >= 2 and tokens[0] == "Objective:":
277                if tokens[4] == "(MINimum)":
278                   results.problem.sense = ProblemSense.minimize
279                else:
280                   results.problem.sense = ProblemSense.maximize
281                soln.objective['f']=tokens[3]
282                if soln.status is SolutionStatus.optimal:
283                   if tokens[4] == "(MINimum)":
284                        results.problem.lower_bound = soln.objective['f'].value
285                        if "upper_bound" in dir(results.problem):
286                            del results.problem.upper_bound
287                   else:
288                        results.problem.upper_bound = soln.objective['f'].value
289                        if "lower_bound" in dir(results.problem):
290                            del results.problem.lower_bound
291                # the objective is the last entry in the problem section - move on to constraints.
292                state = 1
293
294          elif state == 1:
295             #
296             # Process Constraint Info
297             #
298             
299             if (len(tokens) == 2) and (len(active_constraint_name) == 0):
300
301                number_of_constraints_read = number_of_constraints_read + 1
302                active_constraint_name = tokens[1].strip()
303                index = eval(tokens[0].strip())
304
305                # sanity check - the indices should be in sequence.
306                if index != number_of_constraints_read:
307                   raise ValueError,"***ERROR: Unexpected constraint index encountered on line="+line+"; expected value="+str(number_of_constraints_read)+"; actual value="+str(index)
308
309             else:
310
311                index = None
312                activity = None
313                lower_bound = None
314                upper_bound = None
315                marginal = None
316
317                # extract the field names and process accordingly. there
318                # is some wasted processing w.r.t. single versus double-line
319                # entries, but it's not significant enough to worry about.               
320                 
321                index_string = line[0:6].strip()
322                name_string = line[7:19].strip()
323                activity_string = line[23:36].strip()
324                lower_bound_string = line[37:50].strip()
325                upper_bound_string = line[51:64].strip()
326
327                state_string = None               
328                marginal_string = None
329
330                # skip any headers
331                if (index_string == "------") or (index_string == "No."):
332                   continue
333
334                if len(index_string) > 0:
335                   index = eval(index_string)               
336
337                if lp_solution is True:
338                   state_string = line[20:22].strip()
339                   marginal_string = line[65:78].strip()
340                   if (activity_string != "< eps") and (len(activity_string) > 0):
341                      activity = eval(activity_string)
342                   else:
343                      activity = 0.0
344                   if (lower_bound_string != "< eps") and (len(lower_bound_string) > 0):
345                      lower_bound = eval(lower_bound_string)
346                   else:
347                      lower_bound = 0.0
348                   if state_string != "NS":                   
349                      if (upper_bound_string != "< eps") and (len(upper_bound_string) > 0):
350                         upper_bound = eval(upper_bound_string)
351                      else:
352                         upper_bound = 0.0
353                   if (marginal_string != "< eps") and (len(marginal_string) > 0):
354                      marginal = eval(marginal_string)
355                   else:
356                      marginal = 0.0
357
358                else:
359                    # no constraint-related attributes/values are extracted currently for MIPs.
360                    pass
361               
362                constraint_name = None
363                if len(active_constraint_name) > 0:
364                   # if there is an active constraint name, the identifier was
365                   # too long for everything to be on a single line; the second
366                   # line contains all of the value information.                   
367                   constraint_name = active_constraint_name
368                   active_constraint_name = ""
369                else:
370                   # everything is on a single line.
371                   constraint_name = name_string
372                   number_of_constraints_read = number_of_constraints_read + 1 
373                   # sanity check - the indices should be in sequence.
374                   if index != number_of_constraints_read:
375                      raise ValueError,"***ERROR: Unexpected constraint index encountered on line="+line+"; expected value="+str(number_of_constraints_read)+"; actual value="+str(index)
376   
377                if lp_solution is True:
378                   # GLPK doesn't report slacks directly.
379                   constraint_dual = activity
380                   if state_string == "B":
381                      constraint_dual = 0.0
382                   elif (state_string == "NS") or (state_string == "NL") or (state_string == "NU"):
383                      constraint_dual = marginal
384                   else:
385                      raise ValueError, "Unknown status="+tokens[0]+" encountered for constraint="+active_constraint_name+" in line="+line+" of solution file="+self.soln_file
386
387                   if extract_duals is True:
388                      soln.constraint[constraint_name].dual = constraint_dual
389                 
390                else:
391                   # there isn't anything interesting to do with constraints in the MIP case.
392                   pass
393
394                # if all of the constraints have been read, exit.
395                if number_of_constraints_read == results.problem.number_of_constraints:
396                   state = 2
397                     
398          elif state == 2:
399             #
400             # Process Variable Info
401             #
402
403             if (len(tokens) == 2) and (len(active_variable_name) == 0):
404                 
405                # in the case of name over-flow, there are only two tokens
406                # on the first of two lines for the variable entry.
407                number_of_variables_read = number_of_variables_read + 1
408                active_variable_name = tokens[1].strip()
409                index = eval(tokens[0].strip())
410
411                # sanity check - the indices should be in sequence.
412                if index != number_of_variables_read:
413                   raise ValueError,"***ERROR: Unexpected variable index encountered on line="+line+"; expected value="+str(number_of_variables_read)+"; actual value="+str(index)                   
414               
415             else:
416                 
417                index = None
418                activity = None
419                lower_bound = None
420                upper_bound = None
421                marginal = None
422
423                # extract the field names and process accordingly. there
424                # is some wasted processing w.r.t. single versus double-line
425                # entries, but it's not significant enough to worry about.
426
427                index_string = line[0:6].strip()
428                name_string = line[7:19].strip()
429                activity_string = line[23:36].strip()
430                lower_bound_string = line[37:50].strip()
431                upper_bound_string = line[51:64].strip()
432
433                state_string = None
434                marginal_string = None
435
436                # skip any headers
437                if (index_string == "------") or (index_string == "No."):
438                   continue
439
440                if len(index_string) > 0:
441                   index = eval(index_string)
442
443                if lp_solution is True:
444                   state_string = line[20:22].strip()
445                   marginal_string = line[65:78].strip()
446
447                   if (activity_string != "< eps") and (len(activity_string) > 0):
448                      activity = eval(activity_string)
449                   else:
450                      activity = 0.0
451                   if (lower_bound_string != "< eps") and (len(lower_bound_string) > 0):
452                      lower_bound = eval(lower_bound_string)
453                   else:
454                      lower_bound = 0.0
455                   if state_string != "NS":                   
456                      if (upper_bound_string != "< eps") and (len(upper_bound_string) > 0):
457                         upper_bound = eval(upper_bound_string)
458                      else:
459                         upper_bound = 0.0
460                   if (marginal_string != "< eps") and (len(marginal_string) > 0):
461                      marginal = eval(marginal_string)
462                   else:
463                      marginal = 0.0
464
465                else:
466
467                   if (activity_string != "< eps") and (len(activity_string) > 0):
468                      activity = eval(activity_string)
469                   else:
470                      activity = 0.0                   
471
472                variable_name = None
473                if len(active_variable_name) > 0:
474                   # if there is an active variable name, the identifier was
475                   # too long for everything to be on a single line; the second
476                   # line contains all of the value information.
477                   variable_name = active_variable_name
478                   active_variable_name = ""
479                else:
480                   # everything is on a single line.
481                   variable_name = name_string
482                   number_of_variables_read = number_of_variables_read + 1 
483                   # sanity check - the indices should be in sequence.
484                   if index != number_of_variables_read:
485                      raise ValueError,"***ERROR: Unexpected variable index encountered on line="+line+"; expected value="+str(number_of_variables_read)+"; actual value="+str(index)
486
487                if lp_solution is True:
488                   # the "activity" column always specifies the variable value.
489                   # embedding the if-then-else to validate the basis status.
490                   # we are currently ignoring all bound-related information.
491                   variable_value = None
492                   if state_string == "B":
493                      variable_value = activity
494                   elif (state_string == "NL") or (state_string == "NS") or (state_string == "NU"):
495                      variable_value = activity
496                   else:
497                      raise ValueError, "Unknown status="+state_string+" encountered for variable="+active_variable_name+" in line="+line+" of solution file="+self.soln_file
498               
499                   soln.variable[variable_name].value = variable_value
500                else:
501                   soln.variable[variable_name].value = activity
502               
503             # if all of the variables have been read, exit.
504             if number_of_variables_read == results.problem.number_of_variables:
505                state = -1
506             
507          if state==-1:
508             break
509         
510        INPUT.close()
511
512class MockGLPK(GLPK,mockmip.MockMIP):
513    """A Mock GLPK solver used for testing
514    """
515
516    def __init__(self, **kwds):
517        try:
518           GLPK.__init__(self, **kwds)
519        except pyutilib.common.ApplicationError: #pragma:nocover
520           pass                        #pragma:nocover
521        mockmip.MockMIP.__init__(self,"glpk")
522
523    def available(self, exception_flag=True):
524        return GLPK.available(self,exception_flag)
525
526    def create_command_line(self,executable,problem_files):
527        command = GLPK.create_command_line(self,executable,problem_files)
528        mockmip.MockMIP.create_command_line(self,executable,problem_files)
529        return command
530
531    def executable(self):
532        return mockmip.MockMIP.executable(self)
533
534    def _execute_command(self,cmd):
535        return mockmip.MockMIP._execute_command(self,cmd)
536
537    def _convert_problem(self,args,pformat,valid_pformats):
538        if pformat in [ProblemFormat.mps,ProblemFormat.cpxlp]:
539           return (args,pformat,None)
540        else:
541           return (args,ProblemFormat.cpxlp,None)
542
543
544pyutilib.services.register_executable(name="glpsol")
545SolverRegistration("glpk", GLPK)
546SolverRegistration("_mock_glpk", MockGLPK)
Note: See TracBrowser for help on using the repository browser.