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

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

Generalizing the suffix management in the MIP solvers so
they match regular expressions for suffixes. This allows
the user to specify the '.*' suffix, which matches everything.

Reworked the MIP tests, which all pass now.

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.