source: coopr.plugins/trunk/coopr/plugins/mip/GUROBI.py @ 2447

Last change on this file since 2447 was 2447, checked in by wehart, 11 years ago

A draft GUROBI solver interface.

NOTE: I'm not sure if gurobi uses ILM. If not, then we'll
need to eliminate the dependence on the ILM solver class.

File size: 25.8 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 *
17from coopr.pyomo.base.var import *
18import mockmip
19import pyutilib.services
20import pyutilib.common
21import pyutilib.misc
22import pyutilib.component.core
23import string
24import re
25
26import xml.dom.minidom
27
28import time
29
30
31class GUROBI(ILMLicensedSystemCallSolver):
32    """The GUROBI LP/MIP solver
33    """
34
35    def __init__(self, **kwds):
36        #
37        # Call base class constructor
38        #
39        kwds['type'] = 'gurobi'
40        ILMLicensedSystemCallSolver.__init__(self, **kwds)
41
42        # We are currently invoking GUROBI via the command line, with input re-direction.
43        # Consequently, we need to define an attribute
44        # to retain the execution script name.
45        self.gurobi_script_file_name = None
46
47        # NOTE: eventually both of the following attributes should be migrated to a common base class.
48        # is the current solve warm-started? a transient data member to communicate state information
49        # across the _presolve, _apply_solver, and _postsolve methods.
50        self.warm_start_solve = False
51        # related to the above, the temporary name of the MST warm-start file (if any).
52        self.warm_start_file_name = None
53
54        #
55        # Define valid problem formats and associated results formats
56        #
57        self._valid_problem_formats=[ProblemFormat.cpxlp, ProblemFormat.mps]
58        self._valid_result_formats={}
59        self._valid_result_formats[ProblemFormat.cpxlp] = [ResultsFormat.soln]
60        self._valid_result_formats[ProblemFormat.mps] = [ResultsFormat.soln]
61
62    #
63    # ultimately, this utility should go elsewhere - perhaps on the PyomoModel itself.
64    # in the mean time, it is staying here.
65    #
66    def _hasIntegerVariables(self, instance):
67
68       import coopr.pyomo.base.var
69       from coopr.pyomo.base.set_types import IntegerSet, BooleanSet
70
71       for variable in instance.active_components(Var).values():
72
73           if (isinstance(variable.domain, IntegerSet) is True) or (isinstance(variable.domain, BooleanSet) is True):
74
75               return True
76
77       return False
78
79    #
80    # GUROBI has a simple, easy-to-use warm-start capability.
81    #
82    def warm_start_capable(self):
83       return True
84
85    #
86    # write a warm-start file in the GUROBI MST format.
87    #
88    def write_warmstart_file(self, instance):
89
90       import coopr.pyomo.base.var
91
92       self.warm_start_file_name = pyutilib.services.TempfileManager.create_tempfile(suffix = '.gurobi.mst')
93
94       doc = xml.dom.minidom.Document()
95       root_element = doc.createElement("GUROBISolution")
96       root_element.setAttribute("version","1.0")
97       doc.appendChild(root_element)
98
99       # currently not populated.
100       header_element = doc.createElement("header")
101       # currently not populated.       
102       quality_element = doc.createElement("quality")
103       # definitely populated!
104       variables_element = doc.createElement("variables")
105
106       root_element.appendChild(header_element)
107       root_element.appendChild(quality_element)
108       root_element.appendChild(variables_element)
109
110       # for each variable, add a child to the variables element.
111       # both continuous and discrete are accepted (and required,
112       # depending on other options), according to the GUROBI manual.
113       output_index = 0
114       for variable in instance.active_components(Var).values():
115
116           for index in variable._varval.keys():
117
118               if (variable[index].status != coopr.pyomo.base.var.VarStatus.unused) and (variable[index].value != None) and (variable[index].fixed == False):
119
120                   variable_element = doc.createElement("variable")
121                   name = variable[index].label
122                   name = name.replace('[','(')
123                   name = name.replace(']',')')
124                   variable_element.setAttribute("name", name)
125                   variable_element.setAttribute("index", str(output_index))
126                   variable_element.setAttribute("value", str(variable[index].value))
127
128                   variables_element.appendChild(variable_element)
129
130                   output_index = output_index + 1
131
132       mst_file = open(self.warm_start_file_name,'w')
133       doc.writexml(mst_file, indent="    ", newl="\n")
134       mst_file.close()
135
136    # over-ride presolve to extract the warm-start keyword, if specified.
137    def _presolve(self, *args, **kwds):
138
139       # if the first argument is a string (representing a filename),
140       # then we don't have an instance => the solver is being applied
141       # to a file.
142
143       self.warm_start_solve = False               
144       if "warmstart" in kwds:
145          self.warm_start_solve = kwds["warmstart"]
146          del kwds["warmstart"]
147
148       if (len(args) > 0) and (isinstance(args[0],basestring) is False):
149
150          # write the warm-start file - currently only supports MIPs.
151          # we only know how to deal with a single problem instance.       
152          if self.warm_start_solve is True:
153
154             if len(args) != 1:
155                raise ValueError, "GUROBI _presolve method can only handle a single problem instance - "+str(len(args))+" were supplied"                 
156
157             if self._hasIntegerVariables(args[0]) is True:
158                start_time = time.time()
159                self.write_warmstart_file(args[0])
160                end_time = time.time()
161                if self._report_timing is True:
162                   print "Warm start write time="+str(end_time-start_time)+" seconds"
163         
164       # let the base class handle any remaining keywords/actions.
165       ILMLicensedSystemCallSolver._presolve(self, *args, **kwds)
166
167    def executable(self):
168        executable = pyutilib.services.registered_executable("gurobi")
169        if executable is None:
170            pyutilib.component.core.PluginGlobals.env().log.error("Could not locate the 'gurobi' executable, which is required for solver %s" % self.name)
171            self.enable = False
172            return None
173        return executable.get_path()
174
175    def create_command_line(self,executable,problem_files):
176        #
177        # Define log file
178        # The log file in GUROBI contains the solution trace, but the solver status can be found in the solution file.
179        #
180        self.log_file = pyutilib.services.TempfileManager.create_tempfile(suffix = '.gurobi.log')
181
182        #
183        # Define solution file
184        # As indicated above, contains (in XML) both the solution and solver status.
185        #
186        self.soln_file = pyutilib.services.TempfileManager.create_tempfile(suffix = '.gurobi.sol')
187
188        #
189        # Define results file
190        #
191        if self._results_format is None or self._results_format == ResultsFormat.soln:
192           self.results_file = self.soln_file
193        elif self._results_format == ResultsFormat.sol:
194           self.results_file = self.sol_file
195
196        #
197        # Write the GUROBI execution script
198        #
199        self.gurobi_script_file_name = pyutilib.services.TempfileManager.create_tempfile(suffix = '.gurobi.script')
200        gurobi_script_file = open(self.gurobi_script_file_name,'w')
201        gurobi_script_file.write("set logfile "+self.log_file+"\n")
202        if self._timelimit is not None and self._timelimit > 0.0:
203            gurobi_script_file.write("set timelimit "+`self._timelimit`+"\n")
204        if (self.mipgap is not None) and (self.mipgap > 0.0):
205            gurobi_script_file.write("set mip tolerances mipgap "+`self.mipgap`+"\n")           
206        for key in self.options:
207                if key in ['relax_integrality']:
208                    pass
209                elif isinstance(self.options[key],basestring) and ' ' in self.options[key]:
210                    opt = " ".join(key.split('_'))+" "+str(self.options[key])
211                else:
212                    opt = " ".join(key.split('_'))+" "+str(self.options[key])
213                gurobi_script_file.write("set "+opt+"\n")
214        gurobi_script_file.write("read "+problem_files[0]+"\n")
215
216        # if we're dealing with an LP, the MST file will be empty.
217        if (self.warm_start_solve is True) and (self.warm_start_file_name is not None):
218            gurobi_script_file.write("read "+self.warm_start_file_name+"\n")
219
220        if 'relax_integrality' in self.options:
221            gurobi_script_file.write("change problem lp\n")
222           
223        gurobi_script_file.write("display problem stats\n")
224        gurobi_script_file.write("optimize\n")
225        gurobi_script_file.write("write " + self.soln_file+"\n")
226        gurobi_script_file.write("quit\n")
227        gurobi_script_file.close()
228
229        # dump the script and warm-start file names for the
230        # user if we're keeping files around.
231        if self.keepFiles:
232           print "Solver script file=" + self.gurobi_script_file_name
233           if (self.warm_start_solve is True) and (self.warm_start_file_name is not None):
234              print "Solver warm-start file=" + self.warm_start_file_name
235
236        #
237        # Define command line
238        #
239        if self._problem_format in [ProblemFormat.cpxlp, ProblemFormat.mps]:
240           proc = self._timer + " " + self.executable() + " < " + self.gurobi_script_file_name
241        return pyutilib.misc.Bunch(cmd=proc, log_file=self.log_file, env=None)
242
243    def process_logfile(self):
244        """
245        Process logfile
246        """
247        results = SolverResults()
248        results.problem.number_of_variables = None
249        results.problem.number_of_nonzeros = None
250        #
251        # Process logfile
252        #
253        OUTPUT = open(self.log_file)
254        output = "".join(OUTPUT.readlines())
255        OUTPUT.close()
256        #
257        # It is generally useful to know the GUROBI version number for logfile parsing.
258        #
259        gurobi_version = None
260       
261        #
262        # Parse logfile lines
263        #
264        for line in output.split("\n"):
265            tokens = re.split('[ \t]+',line.strip())
266            if len(tokens) > 3 and tokens[0] == "GUROBI" and tokens[1] == "Error":
267                # IMPT: See below - gurobi can generate an error line and then terminate fine, e.g., in GUROBI 12.1.
268                #       To handle these cases, we should be specifying some kind of termination criterion always
269                #       in the course of parsing a log file (we aren't doing so currently - just in some conditions).
270                results.solver.status=SolverStatus.error
271                results.solver.error = " ".join(tokens)
272            elif len(tokens) >= 3 and tokens[0] == "ILOG" and tokens[1] == "GUROBI":
273                gurobi_version = tokens[2].rstrip(',')
274            elif len(tokens) >= 3 and tokens[0] == "Variables":
275                if results.problem.number_of_variables is None: # GUROBI 11.2 and subsequent versions have two Variables sections in the log file output.
276                    results.problem.number_of_variables = tokens[2]
277            # In GUROBI 11 (and presumably before), there was only a single line output to
278            # indicate the constriant count, e.g., "Linear constraints : 16 [Less: 7, Greater: 6, Equal: 3]".
279            # In GUROBI 11.2 (or somewhere in between 11 and 11.2 - I haven't bothered to track it down
280            # in that detail), there is another instance of this line prefix in the min/max problem statistics
281            # block - which we don't care about. In this case, the line looks like: "Linear constraints :" and
282            # that's all.
283            elif len(tokens) >= 4 and tokens[0] == "Linear" and tokens[1] == "constraints":
284                results.problem.number_of_constraints = tokens[3]
285            elif len(tokens) >= 3 and tokens[0] == "Nonzeros":
286                if results.problem.number_of_nonzeros is None: # GUROBI 11.2 and subsequent has two Nonzeros sections.               
287                    results.problem.number_of_nonzeros = tokens[2]
288            elif len(tokens) >= 5 and tokens[4] == "MINIMIZE":
289                results.problem.sense = ProblemSense.minimize
290            elif len(tokens) >= 5 and tokens[4] == "MAXIMIZE":
291                results.problem.sense = ProblemSense.maximize
292            elif len(tokens) >= 4 and tokens[0] == "Solution" and tokens[1] == "time" and tokens[2] == "=":
293               # technically, I'm not sure if this is GUROBI user time or user+system - GUROBI doesn't appear
294               # to differentiate, and I'm not sure we can always provide a break-down.
295               results.solver.user_time = eval(tokens[3])
296            elif len(tokens) >= 4 and tokens[0] == "Dual" and tokens[1] == "simplex" and tokens[3] == "Optimal:":
297                results.solver.termination_condition = TerminationCondition.optimal
298                results.solver.termination_message = ' '.join(tokens)
299            elif len(tokens) >= 4 and tokens[0] == "MIP" and tokens[2] == "Integer" and tokens[3] == "infeasible.":
300                # if GUROBI has previously printed an error message, reduce it to a warning -
301                # there is a strong indication it recovered, but we can't be sure.
302                if results.solver.status == SolverStatus.error:
303                   results.solver.status = SolverStatus.warning
304                else:
305                   results.solver.status = SolverStatus.ok
306                results.solver.termination_condition = TerminationCondition.infeasible
307                results.solver.termination_message = ' '.join(tokens)
308            # for the case below, GUROBI sometimes reports "true" optimal (the first case)
309            # and other times within-tolerance optimal (the second case).
310            elif (len(tokens) >= 4 and tokens[0] == "MIP" and tokens[2] == "Integer" and tokens[3] == "optimal") or \
311                 (len(tokens) >= 4 and tokens[0] == "MIP" and tokens[2] == "Integer" and tokens[3] == "optimal,"):
312                # if GUROBI has previously printed an error message, reduce it to a warning -
313                # there is a strong indication it recovered, but we can't be sure.
314                if results.solver.status == SolverStatus.error:
315                   results.solver.status = SolverStatus.warning
316                else:
317                   results.solver.status = SolverStatus.ok               
318                results.solver.termination_condition = TerminationCondition.optimal
319                results.solver.termination_message = ' '.join(tokens)               
320            elif len(tokens) >= 3 and tokens[0] == "Presolve" and tokens[2] == "Infeasible.":
321                # if GUROBI has previously printed an error message, reduce it to a warning -
322                # there is a strong indication it recovered, but we can't be sure.
323                if results.solver.status == SolverStatus.error:
324                   results.solver.status = SolverStatus.warning
325                else:
326                   results.solver.status = SolverStatus.ok               
327                results.solver.termination_condition = TerminationCondition.infeasible
328                results.solver.termination_message = ' '.join(tokens)
329            elif len(tokens) >= 5 and tokens[0] == "Presolve" and tokens[2] == "Unbounded" and tokens[4] == "infeasible.":
330                # if GUROBI has previously printed an error message, reduce it to a warning -
331                # there is a strong indication it recovered, but we can't be sure.
332                if results.solver.status == SolverStatus.error:
333                   results.solver.status = SolverStatus.warning
334                else:
335                   results.solver.status = SolverStatus.ok               
336                # It isn't clear whether we can determine if the problem is unbounded from
337                # GUROBI's output.
338                results.solver.termination_condition = TerminationCondition.unbounded
339                results.solver.termination_message = ' '.join(tokens)
340        return results
341
342    def process_soln_file(self,results):
343
344        # the only suffixes that we extract from GUROBI are
345        # constraint duals, constraint slacks, and variable
346        # reduced-costs. scan through the solver suffix list
347        # and throw an exception if the user has specified
348        # any others.
349        extract_duals = False
350        extract_slacks = False
351        extract_reduced_costs = False
352        for suffix in self.suffixes:
353           flag=False
354           if re.match(suffix,"dual"):
355                extract_duals = True
356                flag=True
357           if re.match(suffix,"slack"):
358                extract_slacks = True             
359                flag=True
360           if re.match(suffix,"rc"):
361                extract_reduced_costs = True
362                flag=True
363           if not flag:
364              raise RuntimeError,"***GUROBI solver plugin cannot extract solution suffix="+suffix
365
366        lp_solution = False
367        if not os.path.exists(self.soln_file):
368           return
369
370        soln = Solution()
371        soln.objective['f'].value=None
372        INPUT = open(self.soln_file,"r")
373        results.problem.number_of_objectives=1
374        mip_problem=False
375        for line in INPUT:
376            line = line.strip()
377            line = line.lstrip('<?/')
378            line = line.rstrip('/>?')
379            tokens=line.split(' ')
380
381            if tokens[0] == "variable":
382                variable_name = None
383                variable_value = None
384                variable_reduced_cost = None
385                variable_status = None
386                for i in range(1,len(tokens)):
387                   field_name =  string.strip(tokens[i].split('=')[0])
388                   field_value = (string.strip(tokens[i].split('=')[1])).lstrip("\"").rstrip("\"")
389                   if field_name == "name":
390                      variable_name = field_value
391                   elif field_name == "value":
392                      variable_value = field_value
393                   elif (extract_reduced_costs is True) and (field_name == "reducedCost"):
394                      variable_reduced_cost = field_value
395                   elif (extract_reduced_costs is True) and (field_name == "status"):
396                      variable_status = field_value
397
398                # skip the "constant-one" variable, used to capture/retain objective offsets in the GUROBI LP format.
399                if variable_name != "ONE_VAR_CONSTANT":
400                   variable = None # cache the solution variable reference, as the getattr is expensive.
401                   try:
402                       variable = soln.variable[variable_name]
403                       variable.value = eval(variable_value)
404                   except:
405                       variable.value = variable_value
406                   if (variable_reduced_cost is not None) and (extract_reduced_costs is True):
407                        try:
408                            variable.rc = eval(variable_reduced_cost)
409                            if variable_status is not None:
410                               if variable_status == "LL":
411                                  variable.lrc = eval(variable_reduced_cost)
412                               else:
413                                  variable.lrc = 0.0
414                               if variable_status == "UL":
415                                  variable.urc = eval(variable_reduced_cost)
416                               else:
417                                  variable.urc = 0.0
418                        except:
419                            raise ValueError, "Unexpected reduced-cost value="+str(variable_reduced_cost)+" encountered for variable="+variable_name
420            elif (tokens[0] == "constraint") and ((extract_duals is True) or (extract_slacks is True)):
421                constraint_name = None
422                constraint_dual = None
423                constaint = None # cache the solution constraint reference, as the getattr is expensive.
424                for i in range(1,len(tokens)):
425                   field_name =  string.strip(tokens[i].split('=')[0])
426                   field_value = (string.strip(tokens[i].split('=')[1])).lstrip("\"").rstrip("\"")
427                   if field_name == "name":
428                      constraint_name = field_value
429                      constraint = soln.constraint[constraint_name]
430                   elif (extract_duals is True) and (field_name == "dual"): # for LPs
431                      # assumes the name field is first.
432                      if eval(field_value) != 0.0:
433                        constraint.dual = eval(field_value)
434                   elif (extract_slacks is True) and (field_name == "slack"): # for MIPs
435                      # assumes the name field is first.
436                      if eval(field_value) != 0.0:
437                        constraint.slack = eval(field_value)
438            elif tokens[0].startswith("problemName"):
439                filename = (string.strip(tokens[0].split('=')[1])).lstrip("\"").rstrip("\"")
440                #print "HERE",filename
441                results.problem.name = os.path.basename(filename)
442                if '.' in results.problem.name:
443                    results.problem.name = results.problem.name.split('.')[0]
444                tINPUT=open(filename,"r")
445                for tline in tINPUT:
446                    tline = tline.strip()
447                    if tline == "":
448                        continue
449                    tokens = re.split('[\t ]+',tline)
450                    if tokens[0][0] in ['\\', '*']:
451                        continue
452                    elif tokens[0] == "NAME":
453                        results.problem.name = tokens[1]
454                    else:
455                        sense = tokens[0].lower()
456                        if sense in ['max','maximize']:
457                            results.problem.sense = ProblemSense.maximize
458                        if sense in ['min','minimize']:
459                            results.problem.sense = ProblemSense.minimize
460                    break
461                tINPUT.close()
462               
463            elif tokens[0].startswith("objectiveValue"):
464                objective_value = (string.strip(tokens[0].split('=')[1])).lstrip("\"").rstrip("\"")
465                soln.objective['f'].value = objective_value
466            elif tokens[0].startswith("solutionStatusString"):
467                solution_status = (string.strip(" ".join(tokens).split('=')[1])).lstrip("\"").rstrip("\"")
468                if solution_status in ["optimal", "integer optimal solution", "integer optimal, tolerance"]:
469                    soln.status = SolutionStatus.optimal
470                    soln.gap = 0.0
471                    if results.problem.sense == ProblemSense.minimize:
472                        results.problem.lower_bound = soln.objective['f'].value
473                        if "upper_bound" in dir(results.problem):
474                            del results.problem.upper_bound
475                    else:
476                        results.problem.upper_bound = soln.objective['f'].value
477                        if "lower_bound" in dir(results.problem):
478                            del results.problem.lower_bound
479                    mip_problem=True
480            elif tokens[0].startswith("MIPNodes"):
481                if mip_problem:
482                    n = eval(string.strip(" ".join(tokens).split('=')[1])).lstrip("\"").rstrip("\"")
483                    results.solver.statistics.branch_and_bound.number_of_created_subproblems=n
484                    results.solver.statistics.branch_and_bound.number_of_bounded_subproblems=n
485
486               
487        if not results.solver.status is SolverStatus.error:
488            results.solution.insert(soln)
489        INPUT.close()
490
491    def _postsolve(self):
492
493        # take care of the annoying (and empty) GUROBI temporary files in the current directory.
494        # this approach doesn't seem overly efficient, but python os module functions don't
495        # accept regular expression directly.
496        filename_list = os.listdir(".")
497        for filename in filename_list:
498           # GUROBI temporary files come in two flavors - gurobi.log and clone*.log.
499           # the latter is the case for multi-processor environments.
500           # IMPT: trap the possible exception raised by the file not existing.
501           #       this can occur in pyro environments where > 1 workers are
502           #       running GUROBI, and were started from the same directory.
503           #       these logs don't matter anyway (we redirect everything),
504           #       and are largely an annoyance.
505           try:
506              if  re.match('gurobi\.log', filename) != None:
507                  os.remove(filename)
508              elif re.match('clone\d+\.log', filename) != None:
509                  os.remove(filename)
510           except OSError:
511              pass
512
513        # let the base class deal with returning results.
514        return ILMLicensedSystemCallSolver._postsolve(self)           
515
516
517class MockGUROBI(GUROBI,mockmip.MockMIP):
518    """A Mock GUROBI solver used for testing
519    """
520
521    def __init__(self, **kwds):
522        try:
523           GUROBI.__init__(self, **kwds)
524        except pyutilib.common.ApplicationError: #pragma:nocover
525           pass                        #pragma:nocover
526        mockmip.MockMIP.__init__(self,"gurobi")
527
528    def available(self, exception_flag=True):
529        return GUROBI.available(self,exception_flag)
530
531    def create_command_line(self,executable,problem_files):
532        command = GUROBI.create_command_line(self,executable,problem_files)
533        mockmip.MockMIP.create_command_line(self,executable,problem_files)
534        return command
535
536    def executable(self):
537        return mockmip.MockMIP.executable(self)
538
539    def _execute_command(self,cmd):
540        return mockmip.MockMIP._execute_command(self,cmd)
541
542
543pyutilib.services.register_executable(name="gurobi")
544SolverRegistration("gurobi", GUROBI)
545SolverRegistration("_mock_gurobi", MockGUROBI)
Note: See TracBrowser for help on using the repository browser.