source: coopr.plugins/trunk/coopr/plugins/mip/CBC.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: 15.7 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 pyutilib.services
18import pyutilib.misc
19import pyutilib.common
20import pyutilib.component.core
21import mockmip
22
23class CBC(SystemCallSolver):
24    """The CBC LP/MIP solver
25    """
26
27    def __init__(self, **kwds):
28        #
29        # Call base constructor
30        #
31        kwds['type'] = 'cbc'
32        SystemCallSolver.__init__(self, **kwds)
33
34        #
35        # Set up valid problem formats and valid results for each problem format
36        #
37#        self._valid_problem_formats=[ProblemFormat.nl, ProblemFormat.cpxlp, ProblemFormat.mps]
38        self._valid_problem_formats=[ProblemFormat.cpxlp, ProblemFormat.nl, ProblemFormat.mps]       
39        self._valid_result_formats={}
40        self._valid_result_formats[ProblemFormat.cpxlp] = [ResultsFormat.soln]
41        self._valid_result_formats[ProblemFormat.nl] = [ResultsFormat.sol]       
42        self._valid_result_formats[ProblemFormat.mps] = [ResultsFormat.soln]
43
44    def _presolve(self, *args, **kwds):
45
46       # establish real "default" problem and results formats. these may be
47       # over-ridden in the base class solve (via keywords), but we should
48       # have real values by the time we're presolving.
49       if self._problem_format is None:
50
51          if self._valid_problem_formats[0] is ProblemFormat.nl:
52             self._problem_format = ProblemFormat.nl
53          else:
54             self._problem_format = ProblemFormat.cpxlp
55
56       # in CBC, the results format is defined by the problem format;
57       # you can't vary them independently.
58       if self._problem_format is ProblemFormat.nl:
59          self._results_format = ResultsFormat.sol
60       else:
61          # this really means "CBC-specific" format - not drawing from the
62          # log file itself (although additional information is contained there).
63          self._results_format = ResultsFormat.soln
64
65       # let the base class handle any remaining keywords/actions.
66       SystemCallSolver._presolve(self, *args, **kwds)       
67
68    def executable(self):
69        executable = pyutilib.services.registered_executable("cbc")
70        if executable is None:
71            pyutilib.component.core.PluginGlobals.env().log.error("Could not locate the 'cbc' executable, which is required for solver %s" % self.name)
72            self.enable = False
73            return None
74        return executable.get_path()
75
76    def create_command_line(self,executable,problem_files):
77        #
78        # Define the log file
79        #
80        if self.log_file is None:
81           self.log_file = pyutilib.services.TempfileManager.create_tempfile(suffix=".cbc.log")
82
83        #
84        # Define the solution file
85        #
86
87        # the prefix of the problem filename is required because CBC has a specific
88        # and automatic convention for generating the output solution filename.
89        # the extracted prefix is the same name as the input filename, e.g., minus
90        # the ".lp" extension.
91        problem_filename_prefix = problem_files[0]
92        if '.' in problem_filename_prefix:
93            tmp = problem_filename_prefix.split('.')
94            if len(tmp) > 2:
95                problem_filename_prefix = '.'.join(tmp[:-1])
96            else:
97                problem_filename_prefix = tmp[0]
98
99        if self._results_format is ResultsFormat.sol:
100           self.soln_file = problem_filename_prefix+".sol"
101        else:
102           self.soln_file = problem_filename_prefix+".soln"
103
104        #
105        # Define the results file
106        #
107        # results in CBC are split across the log file (solver statistics) and
108        # the solution file (solutions!)
109        self.results_file = self.soln_file
110       
111        #
112        # Define command line
113        #
114        if (self.mipgap is not None):
115           raise ValueError, "The mipgap parameter is currently not being processed by CBC solver plugin"
116       
117        if self._problem_format == ProblemFormat.nl:
118            if self._timelimit is not None and self._timelimit > 0.0:
119                timing = " sec="+str(self._timelimit)
120            else:
121                timing = ""
122            if "debug" in self.options:
123                opt = ""
124            else:
125                opt = " log=5"
126            for key in self.options:
127                if isinstance(self.options[key],basestring) and ' ' in self.options[key]:
128                    opt += " "+key+"=\""+str(self.options[key])+"\""
129                else:
130                    opt += " "+key+"="+str(self.options[key])
131            self._nl_options = " ".join(self.options) + timing+ " stat=1 "+opt+" printingOptions=all"
132            proc = self._timer + " " + executable + " " + problem_files[0] + " -AMPL "+self._nl_options
133        else:
134            if self._timelimit is not None and self._timelimit > 0.0:
135                timing = " -sec "+str(self._timelimit)+" "
136            else:
137                timing = ""
138            if "debug" in self.options:
139                opt = ""
140            else:
141                opt = " -log 5"
142            for key in self.options:
143                if isinstance(self.options[key],basestring) and ' ' in self.options[key]:
144                    opt += " -"+key+" \""+str(self.options[key])+"\""
145                else:
146                    opt += " -"+key+" "+str(self.options[key])
147            proc = self._timer + " " + executable + opt + " -printingOptions all "+timing+ " -import "+problem_files[0]+ " -import -stat 1 -solve -solu " + self.soln_file
148        return pyutilib.misc.Bunch(cmd=proc, log_file=self.log_file, env=None)
149
150    def process_logfile(self):
151        """
152        Process logfile
153        """
154        results = SolverResults()
155        #
156        # Initial values
157        #
158        #results.solver.statistics.branch_and_bound.number_of_created_subproblems=0
159        #results.solver.statistics.branch_and_bound.number_of_bounded_subproblems=0
160        soln = results.solution.add()
161        soln.objective['f'].value=float('inf')
162        #
163        # Process logfile
164        #
165        OUTPUT = open(self.log_file)
166        output = "".join(OUTPUT.readlines())
167        OUTPUT.close()
168        #
169        # Parse logfile lines
170        #
171        results.problem.sense = ProblemSense.minimize
172        sense=1
173        results.problem.name = None
174        for line in output.split("\n"):
175          tokens = re.split('[ \t]+',line.strip())
176          #print "LINE:", line
177          if len(tokens) == 10 and tokens[0] == "Current" and tokens[1] == "default" and tokens[2] == "(if" and results.problem.name is None:
178             results.problem.name = tokens[-1]
179             if '.' in results.problem.name:
180                parts = results.problem.name.split('.')
181                if len(parts) > 2:
182                    results.problem.name = '.'.join(parts[:-1])
183                else:
184                    results.problem.name = results.problem.name.split('.')[0]
185             if '/' in results.problem.name:
186                results.problem.name = results.problem.name.split('/')[-1]
187             if '\\' in results.problem.name:
188                results.problem.name = results.problem.name.split('\\')[-1]
189          if len(tokens) ==11 and tokens[0] == "Presolve" and tokens[3] == "rows,":
190             results.problem.number_of_variables = eval(tokens[4])-eval(tokens[5][1:-1])
191             results.problem.number_of_constraints = eval(tokens[1])-eval(tokens[2][1:-1])
192             results.problem.number_of_nonzeros = eval(tokens[8])-eval(tokens[9][1:-1])
193             results.problem.number_of_objectives = "1"
194          if len(tokens) >=9 and tokens[0] == "Problem" and tokens[2] == "has":
195             results.problem.number_of_variables = tokens[5]
196             results.problem.number_of_constraints = tokens[3]
197             results.problem.number_of_nonzeros = tokens[8]
198             results.problem.number_of_objectives = "1"
199          if len(tokens) == 5 and tokens[3] == "NAME":
200             results.problem.name = tokens[4]
201          if " ".join(tokens) == '### WARNING: CoinLpIO::readLp(): Maximization problem reformulated as minimization':
202             results.problem.sense = ProblemSense.maximize
203             sense = -1
204          if len(tokens) > 3 and tokens[0] == "Presolve" and tokens[6] == "infeasible":
205             soln.status = SolutionStatus.infeasible
206             soln.objective['f'].value=None
207          if len(tokens) > 3 and tokens[0] == "Optimal" and tokens[1] == "objective":
208             soln.status = SolutionStatus.optimal
209             soln.objective['f'].value=tokens[2]
210          if len(tokens) > 6 and tokens[4] == "best" and tokens[5] == "objective":
211             soln.objective['f'].value=tokens[6]
212          if len(tokens) > 9 and tokens[7] == "(best" and tokens[8] == "possible":
213             results.problem.lower_bound=tokens[9]
214             results.problem.lower_bound = results.problem.lower_bound.split(")")[0]
215          if len(tokens) > 12 and tokens[10] == "best" and tokens[11] == "possible":
216             results.problem.lower_bound=tokens[12]
217          if len(tokens) > 3 and tokens[0] == "Result" and tokens[2] == "Finished":
218             soln.status = SolutionStatus.optimal
219             soln.objective['f'].value=tokens[4]
220          if len(tokens) > 10 and tokens[4] == "time" and tokens[9] == "nodes":
221             results.solver.statistics.branch_and_bound.number_of_created_subproblems=tokens[8]
222             results.solver.statistics.branch_and_bound.number_of_bounded_subproblems=tokens[8]
223             if eval(results.solver.statistics.branch_and_bound.number_of_bounded_subproblems) > 0:
224                soln.objective['f'].value=tokens[6]
225          if len(tokens) == 5 and tokens[1] == "Exiting" and tokens[4] == "time":
226             soln.status = SolutionStatus.stoppedByLimit
227          if len(tokens) > 8 and tokens[7] == "nodes":
228             results.solver.statistics.branch_and_bound.number_of_created_subproblems=tokens[6]
229             results.solver.statistics.branch_and_bound.number_of_bounded_subproblems=tokens[6]
230          if len(tokens) == 2 and tokens[0] == "sys":
231             results.solver.system_time=tokens[1]
232          if len(tokens) == 2 and tokens[0] == "user":
233             results.solver.user_time=tokens[1]
234          results.solver.user_time=-1.0
235
236        if soln.objective['f'].value == "1e+50":
237           if sense == 1:
238              soln.objective['f'].value=float('inf')
239           else:
240              soln.objective['f'].value=float('-inf')
241        elif not soln.objective['f'].value is None:
242           soln.objective['f'].value = eval(soln.objective['f'].value)*sense
243        if soln.status is SolutionStatus.optimal:
244           soln.gap=0.0
245           if results.problem.sense == ProblemSense.minimize:
246                results.problem.lower_bound = soln.objective['f'].value
247                if "upper_bound" in dir(results.problem):
248                    del results.problem.upper_bound
249           else:
250                results.problem.upper_bound = soln.objective['f'].value
251                if "lower_bound" in dir(results.problem):
252                    del results.problem.lower_bound
253        if results.solver.status is SolverStatus.error:
254           results.solution.delete(0)
255        return results
256
257    def process_soln_file(self,results):
258
259        # the only suffixes that we extract from CBC are
260        # constraint duals and variable reduced-costs. scan
261        # through the solver suffix list and throw an
262        # exception if the user has specified any others.
263        extract_duals = False
264        extract_reduced_costs = False
265        for suffix in self.suffixes:
266           flag=False
267           if re.match(suffix, "dual"):
268              extract_duals = True
269              flag=True
270           if re.match(suffix, "rc"):
271              extract_reduced_costs = True
272              flag=True
273           if not flag:
274              raise RuntimeError,"***CBC solver plugin cannot extract solution suffix="+suffix
275
276        # if dealing with SOL format files, we've already read
277        # this via the base class reader functionality.
278        if self._results_format is ResultsFormat.sol:
279           return
280
281        # otherwise, go with the native CBC solution format.
282        solution = results.solution(0)
283        if solution.status is SolutionStatus.infeasible:
284            # NOTE: CBC _does_ print a solution file.  However, I'm not
285            # sure how to interpret it yet.
286            return
287        results.problem.number_of_objectives=1
288
289        processing_constraints=None # None means header, True means constraints, False means variables.
290        INPUT = open(self.soln_file,"r")
291        for line in INPUT:
292          tokens = re.split('[ \t]+',line.strip())
293          #print "LINE",line,len(tokens)
294          if tokens[0] in ("Optimal", "Status"):
295             # TBD - this logic isn't correct/complete. flush out as necessary.             
296             continue
297          if tokens[0] == "0": # indicates section start.
298             if processing_constraints is None:
299                processing_constraints = True
300             elif processing_constraints is True:
301                processing_constraints = False
302             else:
303                raise RuntimeError, "CBC encountered unexpected line=("+line.strip()+") in solution file="+self.soln_file+"; constraint and variable sections already processed!"
304
305          if (processing_constraints is True) and (extract_duals is True):
306             constraint = tokens[1]
307             constraint_ax = eval(tokens[2]) # CBC reports the constraint row times the solution vector - not the slack.
308             constraint_dual = eval(tokens[3])
309
310             solution.constraint[constraint].dual = constraint_dual
311
312          elif processing_constraints is False:
313             variable_name = tokens[1]
314             variable_value = eval(tokens[2])
315             solution.variable[variable_name].value = variable_value
316
317             if extract_reduced_costs is True:
318                variable_reduced_cost = eval(tokens[3]) # currently ignored.
319                solution.variable[variable_name].rc = variable_reduced_cost
320          else:
321             raise RuntimeError, "CBC encountered unexpected line=("+line.strip()+") in solution file="+self.soln_file+"; expecting header, but found data!"
322         
323        INPUT.close()
324
325
326class MockCBC(CBC,mockmip.MockMIP):
327    """A Mock CBC solver used for testing
328    """
329
330    def __init__(self, **kwds):
331        try:
332           CBC.__init__(self,**kwds)
333        except pyutilib.common.ApplicationError: #pragma:nocover
334           pass                        #pragma:nocover
335        mockmip.MockMIP.__init__(self,"cbc")
336
337    def available(self, exception_flag=True):
338        return CBC.available(self,exception_flag)
339
340    def create_command_line(self,executable,problem_files):
341        command = CBC.create_command_line(self,executable,problem_files)
342        mockmip.MockMIP.create_command_line(self,executable,problem_files)
343        return command
344
345    def executable(self):
346        return mockmip.MockMIP.executable(self)
347
348    def _execute_command(self,cmd):
349        return mockmip.MockMIP._execute_command(self,cmd)
350
351    def _convert_problem(self,args,pformat,valid_pformats):
352        if pformat in [ProblemFormat.mps, ProblemFormat.cpxlp, ProblemFormat.nl]:
353           return (args, pformat, None)
354        else:
355           return (args, ProblemFormat.mps, None)
356
357
358pyutilib.services.register_executable(name="cbc")
359SolverRegistration("cbc", CBC)
360SolverRegistration("_mock_cbc", MockCBC)
Note: See TracBrowser for help on using the repository browser.