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

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

Reworking MIP plugins to more selectively print
branch-and-bound information. Don't print
this info unless solving a MIP.

File size: 24.0 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.plugin.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.plugin.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        lp_solution = True # if false, we're dealing with a MIP!
216        if not os.path.exists(self.soln_file):
217           return
218        soln = results.solution(0)
219        INPUT = open(self.soln_file,"r")
220       
221        state = 0 # 0=initial header, 1=constraints, 2=variables, -1=done
222       
223        results.problem.number_of_objectives = 1
224       
225        number_of_constraints_read = 0 # for validation of the total count read and the order
226        number_of_variables_read = 0
227        active_constraint_name = "" # constraint names and their value/bounds can be split across multiple lines
228        active_variable_name = "" # variable names and their value/bounds can be split across multiple lines
229       
230        for line in INPUT:
231          tokens = re.split('[ \t]+',line.strip())
232
233          if (len(tokens) == 1) and (len(tokens[0]) == 0):
234             pass
235          elif state == 0:
236             #
237             # Processing initial header
238             #
239             if len(tokens) == 2 and tokens[0] == "Problem:":
240                # the problem name may be absent, in which case the "Problem:" line will be skipped.
241                results.problem.name = tokens[1]
242             elif len(tokens) == 2 and tokens[0] == "Rows:":
243                results.problem.number_of_constraints = eval(tokens[1])
244             elif len(tokens) == 2 and tokens[0] == "Columns:":
245                lp_solution = True
246                results.problem.number_of_variables = eval(tokens[1])
247             elif len(tokens) > 2 and tokens[0] == "Columns:":
248                lp_solution = False
249                results.problem.number_of_variables = eval(tokens[1])               
250             elif len(tokens) == 2 and tokens[0] == "Non-zeros:":
251                results.problem.number_of_nonzeros = eval(tokens[1])
252             elif len(tokens) >= 2 and tokens[0] == "Status:":
253                if tokens[1] == "OPTIMAL":
254                   soln.status = SolutionStatus.optimal
255                elif len(tokens) == 3 and tokens[1] == "INTEGER" and tokens[2] == "NON-OPTIMAL":
256                   soln.status = SolutionStatus.bestSoFar
257                elif len(tokens) == 3 and tokens[1] == "INTEGER" and tokens[2] == "OPTIMAL":
258                   soln.status = SolutionStatus.optimal
259                elif len(tokens) == 3 and tokens[1] == "INTEGER" and tokens[2] == "UNDEFINED":
260                   soln.status = SolutionStatus.stoppedByLimit
261                else:
262                   print "GLPK WARNING: unknown status: "+" ".join(tokens[1:])
263             elif len(tokens) >= 2 and tokens[0] == "Objective:":
264                if tokens[4] == "(MINimum)":
265                   results.problem.sense = ProblemSense.minimize
266                else:
267                   results.problem.sense = ProblemSense.maximize
268                soln.objective['f']=tokens[3]
269                if soln.status is SolutionStatus.optimal:
270                   if tokens[4] == "(MINimum)":
271                        results.problem.lower_bound = soln.objective['f'].value
272                        if "upper_bound" in dir(results.problem):
273                            del results.problem.upper_bound
274                   else:
275                        results.problem.upper_bound = soln.objective['f'].value
276                        if "lower_bound" in dir(results.problem):
277                            del results.problem.lower_bound
278                # the objective is the last entry in the problem section - move on to constraints.
279                state = 1
280
281          elif state == 1:
282             #
283             # Process Constraint Info
284             #
285             
286             if (len(tokens) == 2) and (len(active_constraint_name) == 0):
287
288                number_of_constraints_read = number_of_constraints_read + 1
289                active_constraint_name = tokens[1].strip()
290                index = eval(tokens[0].strip())
291
292                # sanity check - the indices should be in sequence.
293                if index != number_of_constraints_read:
294                   raise ValueError,"***ERROR: Unexpected constraint index encountered on line="+line+"; expected value="+str(number_of_constraints_read)+"; actual value="+str(index)
295
296             else:
297
298                index = None
299                activity = None
300                lower_bound = None
301                upper_bound = None
302                marginal = None
303
304                # extract the field names and process accordingly. there
305                # is some wasted processing w.r.t. single versus double-line
306                # entries, but it's not significant enough to worry about.               
307                 
308                index_string = line[0:6].strip()
309                name_string = line[7:19].strip()
310                activity_string = line[23:36].strip()
311                lower_bound_string = line[37:50].strip()
312                upper_bound_string = line[51:64].strip()
313
314                state_string = None               
315                marginal_string = None
316
317                # skip any headers
318                if (index_string == "------") or (index_string == "No."):
319                   continue
320
321                if len(index_string) > 0:
322                   index = eval(index_string)               
323
324                if lp_solution is True:
325                   state_string = line[20:22].strip()
326                   marginal_string = line[65:78].strip()
327                   if (activity_string != "< eps") and (len(activity_string) > 0):
328                      activity = eval(activity_string)
329                   else:
330                      activity = 0.0
331                   if (lower_bound_string != "< eps") and (len(lower_bound_string) > 0):
332                      lower_bound = eval(lower_bound_string)
333                   else:
334                      lower_bound = 0.0
335                   if state_string != "NS":                   
336                      if (upper_bound_string != "< eps") and (len(upper_bound_string) > 0):
337                         upper_bound = eval(upper_bound_string)
338                      else:
339                         upper_bound = 0.0
340                   if (marginal_string != "< eps") and (len(marginal_string) > 0):
341                      marginal = eval(marginal_string)
342                   else:
343                      marginal = 0.0
344
345                else:
346                    # no constraint-related attributes/values are extracted currently for MIPs.
347                    pass
348               
349                constraint_name = None
350                if len(active_constraint_name) > 0:
351                   # if there is an active constraint name, the identifier was
352                   # too long for everything to be on a single line; the second
353                   # line contains all of the value information.                   
354                   constraint_name = active_constraint_name
355                   active_constraint_name = ""
356                else:
357                   # everything is on a single line.
358                   constraint_name = name_string
359                   number_of_constraints_read = number_of_constraints_read + 1 
360                   # sanity check - the indices should be in sequence.
361                   if index != number_of_constraints_read:
362                      raise ValueError,"***ERROR: Unexpected constraint index encountered on line="+line+"; expected value="+str(number_of_constraints_read)+"; actual value="+str(index)
363
364                if lp_solution is True:
365                   # GLPK doesn't report slacks directly.
366                   constraint_dual = activity
367                   if state_string == "B":
368                      constraint_dual = 0.0
369                   elif (state_string == "NS") or (state_string == "NL") or (state_string == "NU"):
370                      constraint_dual = marginal
371                   else:
372                      raise ValueError, "Unknown status="+tokens[0]+" encountered for constraint="+active_constraint_name+" in line="+line+" of solution file="+self.soln_file
373
374                   soln.constraint[constraint_name].dual = constraint_dual
375                 
376                else:
377                   # there isn't anything interesting to do with constraints in the MIP case.
378                   pass
379
380                # if all of the constraints have been read, exit.
381                if number_of_constraints_read == results.problem.number_of_constraints:
382                   state = 2
383                     
384          elif state == 2:
385             #
386             # Process Variable Info
387             #
388
389             if (len(tokens) == 2) and (len(active_variable_name) == 0):
390                 
391                # in the case of name over-flow, there are only two tokens
392                # on the first of two lines for the variable entry.
393                number_of_variables_read = number_of_variables_read + 1
394                active_variable_name = tokens[1].strip()
395                index = eval(tokens[0].strip())
396
397                # sanity check - the indices should be in sequence.
398                if index != number_of_variables_read:
399                   raise ValueError,"***ERROR: Unexpected variable index encountered on line="+line+"; expected value="+str(number_of_variables_read)+"; actual value="+str(index)                   
400               
401             else:
402                 
403                index = None
404                activity = None
405                lower_bound = None
406                upper_bound = None
407                marginal = None
408
409                # extract the field names and process accordingly. there
410                # is some wasted processing w.r.t. single versus double-line
411                # entries, but it's not significant enough to worry about.
412
413                index_string = line[0:6].strip()
414                name_string = line[7:19].strip()
415                activity_string = line[23:36].strip()
416                lower_bound_string = line[37:50].strip()
417                upper_bound_string = line[51:64].strip()
418
419                state_string = None
420                marginal_string = None
421
422                # skip any headers
423                if (index_string == "------") or (index_string == "No."):
424                   continue
425
426                if len(index_string) > 0:
427                   index = eval(index_string)
428
429                if lp_solution is True:
430                   state_string = line[20:22].strip()
431                   marginal_string = line[65:78].strip()                               
432
433                   if (activity_string != "< eps") and (len(activity_string) > 0):
434                      activity = eval(activity_string)
435                   else:
436                      activity = 0.0
437                   if (lower_bound_string != "< eps") and (len(lower_bound_string) > 0):
438                      lower_bound = eval(lower_bound_string)
439                   else:
440                      lower_bound = 0.0
441                   if state_string != "NS":                   
442                      if (upper_bound_string != "< eps") and (len(upper_bound_string) > 0):
443                         upper_bound = eval(upper_bound_string)
444                      else:
445                         upper_bound = 0.0
446                   if (marginal_string != "< eps") and (len(marginal_string) > 0):
447                      marginal = eval(marginal_string)
448                   else:
449                      marginal = 0.0
450
451                else:
452
453                   if (activity_string != "< eps") and (len(activity_string) > 0):
454                      activity = eval(activity_string)
455                   else:
456                      activity = 0.0                   
457
458                variable_name = None
459                if len(active_variable_name) > 0:
460                   # if there is an active variable name, the identifier was
461                   # too long for everything to be on a single line; the second
462                   # line contains all of the value information.
463                   variable_name = active_variable_name
464                   active_variable_name = ""
465                else:
466                   # everything is on a single line.
467                   variable_name = name_string
468                   number_of_variables_read = number_of_variables_read + 1 
469                   # sanity check - the indices should be in sequence.
470                   if index != number_of_variables_read:
471                      raise ValueError,"***ERROR: Unexpected variable index encountered on line="+line+"; expected value="+str(number_of_variables_read)+"; actual value="+str(index)
472
473                if lp_solution is True:
474                   # the "activity" column always specifies the variable value.
475                   # embedding the if-then-else to validate the basis status.
476                   # we are currently ignoring all bound-related information.
477                   variable_value = None
478                   if state_string == "B":
479                      variable_value = activity
480                   elif (state_string == "NL") or (state_string == "NS") or (state_string == "NU"):
481                      variable_value = activity
482                   else:
483                      raise ValueError, "Unknown status="+state_string+" encountered for variable="+active_variable_name+" in line="+line+" of solution file="+self.soln_file
484               
485                   soln.variable[variable_name].value = variable_value
486                else:
487                   soln.variable[variable_name].value = activity
488               
489             # if all of the variables have been read, exit.
490             if number_of_variables_read == results.problem.number_of_variables:
491                state = -1
492             
493          if state==-1:
494             break
495         
496        INPUT.close()
497
498class MockGLPK(GLPK,mockmip.MockMIP):
499    """A Mock GLPK solver used for testing
500    """
501
502    def __init__(self, **kwds):
503        try:
504           GLPK.__init__(self, **kwds)
505        except pyutilib.common.ApplicationError: #pragma:nocover
506           pass                        #pragma:nocover
507        mockmip.MockMIP.__init__(self,"glpk")
508
509    def available(self, exception_flag=True):
510        return GLPK.available(self,exception_flag)
511
512    def create_command_line(self,executable,problem_files):
513        command = GLPK.create_command_line(self,executable,problem_files)
514        mockmip.MockMIP.create_command_line(self,executable,problem_files)
515        return command
516
517    def executable(self):
518        return mockmip.MockMIP.executable(self)
519
520    def _execute_command(self,cmd):
521        return mockmip.MockMIP._execute_command(self,cmd)
522
523    def _convert_problem(self,args,pformat,valid_pformats):
524        if pformat in [ProblemFormat.mps,ProblemFormat.cpxlp]:
525           return (args,pformat,None)
526        else:
527           return (args,ProblemFormat.cpxlp,None)
528
529
530pyutilib.services.register_executable(name="glpsol")
531SolverRegistration("glpk", GLPK)
532SolverRegistration("_mock_glpk", MockGLPK)
Note: See TracBrowser for help on using the repository browser.