Changeset 1981 for coopr.plugins


Ignore:
Timestamp:
Dec 12, 2009 1:04:10 AM (10 years ago)
Author:
jwatson
Message:

Major re-work to GLPK interface, which was failing to read pretty much all solutions correctly. In particular, if identifiers are longer than the "usual" GLPK field width, the index/name and various values/status elements are split across multiple lines. This wrecks unit tests, but those will have to be revisited anyway - we still don't handle MIPs correctly, as the formats between MIP and LP are radically different.

Plan is to commit the MIP fix first, and then we can revisit the unit tests.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • coopr.plugins/trunk/coopr/plugins/mip/GLPK.py

    r1939 r1981  
    209209
    210210    def process_soln_file(self,results):
    211         lp_solution=False
     211
     212        lp_solution = True
    212213        if not os.path.exists(self.soln_file):
    213214           return
    214215        soln = results.solution(0)
    215216        INPUT = open(self.soln_file,"r")
    216         state=0
    217         results.problem.number_of_objectives=1
     217       
     218        state = 0 # 0=initial header, 1=constraints, 2=variables, -1=done
     219       
     220        results.problem.number_of_objectives = 1
     221       
     222        number_of_constraints_read = 0 # for validation of the total count read and the order
     223        number_of_variables_read = 0
     224        active_constraint_name = "" # constraint names and their value/bounds can be split across multiple lines
     225        active_variable_name = "" # variable names and their value/bounds can be split across multiple lines
     226       
    218227        for line in INPUT:
    219228          tokens = re.split('[ \t]+',line.strip())
    220           ##print "LINE",line,len(tokens)
    221           ##print "TOKENS",tokens
    222           if state==0:
     229
     230          if (len(tokens) == 1) and (len(tokens[0]) == 0):
     231             pass
     232          elif state == 0:
    223233             #
    224234             # Processing initial header
    225235             #
    226236             if len(tokens) == 2 and tokens[0] == "Problem:":
     237                # the problem name may be absent, in which case the "Problem:" line will be skipped.
    227238                results.problem.name = tokens[1]
    228239             elif len(tokens) == 2 and tokens[0] == "Rows:":
    229                 results.problem.number_of_constraints = tokens[1]
     240                results.problem.number_of_constraints = eval(tokens[1])
    230241             elif len(tokens) >= 2 and tokens[0] == "Columns:":
    231                 results.problem.number_of_variables = tokens[1]
     242                results.problem.number_of_variables = eval(tokens[1])
    232243             elif len(tokens) == 2 and tokens[0] == "Non-zeros:":
    233                 results.problem.number_of_nonzeros = tokens[1]
     244                results.problem.number_of_nonzeros = eval(tokens[1])
    234245             elif len(tokens) >= 2 and tokens[0] == "Status:":
    235246                if tokens[1] == "OPTIMAL":
     
    258269                        if "lower_bound" in dir(results.problem):
    259270                            del results.problem.lower_bound
    260              elif len(tokens) > 1 and tokens[0] == "No.":
    261                 if tokens[1] == "Row":
    262                    state=1
    263                 else:
    264                    state=2
    265           elif state==1:
     271                # the objective is the last entry in the problem section - move on to constraints.
     272                state = 1
     273
     274          elif state == 1:
    266275             #
    267276             # Process Constraint Info
    268277             #
    269              if len(tokens) == 0:
    270                 continue
    271              if len(tokens) > 1 and tokens[0] == "No.":
    272                 state=2
    273                 if line[65:78].strip() == "Marginal":
    274                    lp_solution=True
     278             
     279             if (len(tokens) == 2) and (len(active_constraint_name) == 0):
     280
     281                number_of_constraints_read = number_of_constraints_read + 1
     282                active_constraint_name = tokens[1].strip()
     283                index = eval(tokens[0].strip())
     284
     285                # sanity check - the indices should be in sequence.
     286                if index != number_of_constraints_read:
     287                   raise ValueError,"***ERROR: Unexpected constraint index encountered on line="+line+"; expected value="+str(number_of_constraints_read)+"; actual value="+str(index)
     288
    275289             else:
    276                 tmp=line[0:6]
    277                 tmp = tmp.strip()
    278                 if tmp == "------":
    279                    continue
    280                 if tmp != "":
    281                    tmpname = tokens[1]
    282                    if len(tokens) == 2:
    283                       continue
    284                 tmp=line[65:78]
    285                 tmp=tmp.strip()
    286                 ##print "HERE",tmp
    287                 if tmp=="":
    288                    if lp_solution:
    289                       soln.dual.add( tmpname,0.0 )
    290                 else:
    291                    if tmp.strip() == "< eps":
    292                       soln.constraint[tmpname].dual = 0.0
     290
     291                index = None
     292                activity = None
     293                lower_bound = None
     294                upper_bound = None
     295                marginal = None
     296
     297                # extract the field names and process accordingly. there
     298                # is some wasted processing w.r.t. single versus double-line
     299                # entries, but it's not significant enough to worry about.               
     300                 
     301                index_string = line[0:6].strip()
     302                name_string = line[7:19].strip()               
     303                state_string = line[20:22].strip()
     304                activity_string = line[23:36].strip()
     305                lower_bound_string = line[37:50].strip()
     306                upper_bound_string = line[51:64].strip()
     307                marginal_string = line[65:78].strip()
     308
     309                # skip any headers
     310                if (index_string == "------") or (index_string == "No."):
     311                   continue                               
     312
     313                if len(index_string) > 0:
     314                   index = eval(index_string)
     315                if (activity_string != "< eps") and (len(activity_string) > 0):
     316                   activity = eval(activity_string)
     317                else:
     318                   activity = 0.0
     319                if (lower_bound_string != "< eps") and (len(lower_bound_string) > 0):
     320                   lower_bound = eval(lower_bound_string)
     321                else:
     322                   lower_bound = 0.0
     323                if state_string != "NS":                   
     324                   if (upper_bound_string != "< eps") and (len(upper_bound_string) > 0):
     325                      upper_bound = eval(upper_bound_string)
    293326                   else:
    294                       soln.constraint[tmpname].dual = eval(tmp)
    295           elif state==2:
     327                      upper_bound = 0.0
     328                if (marginal_string != "< eps") and (len(marginal_string) > 0):
     329                   marginal = eval(marginal_string)
     330                else:
     331                   marginal = 0.0
     332
     333                constraint_name = None
     334                if len(active_constraint_name) > 0:
     335                   # if there is an active constraint name, the identifier was
     336                   # too long for everything to be on a single line; the second
     337                   # line contains all of the value information.                   
     338                   constraint_name = active_constraint_name
     339                   active_constraint_name = ""
     340                else:
     341                   # everything is on a single line.
     342                   constraint_name = name_string
     343                   number_of_constraints_read = number_of_constraints_read + 1
     344                   # sanity check - the indices should be in sequence.
     345                   if index != number_of_constraints_read:
     346                      raise ValueError,"***ERROR: Unexpected constraint index encountered on line="+line+"; expected value="+str(number_of_constraints_read)+"; actual value="+str(index)
     347
     348                # GLPK doesn't report slacks directly.
     349                constraint_dual = activity
     350                if state_string == "B":
     351                   constraint_dual = 0.0
     352                elif (state_string == "NS") or (state_string == "NL") or (state_string == "NU"):
     353                   constraint_dual = marginal
     354                else:
     355                   raise ValueError, "Unknown status="+tokens[0]+" encountered for constraint="+active_constraint_name+" in line="+line+" of solution file="+self.soln_file
     356
     357                soln.constraint[constraint_name].dual = constraint_dual
     358
     359                # if all of the constraints have been read, exit.
     360                if number_of_constraints_read == results.problem.number_of_constraints:
     361                   state = 2
     362                     
     363          elif state == 2:
    296364             #
    297365             # Process Variable Info
    298366             #
    299              if len(tokens) == 1:
    300                 state=-1
    301                 continue
    302              if True:
    303                 tmp=line[0:6]
    304                 tmp = tmp.strip()
    305                 if tmp == "------":
    306                    continue
    307                 if tmp != "":
    308                    tmpname = tokens[1]
    309                    if len(tokens) == 2:
    310                       continue
    311                 tmp=line[23:36]
    312                 tmp=tmp.strip()
    313                 if tmp=="":
    314                    soln.variable[tmpname].value = 0.0
    315                 else:
    316                    soln.variable[tmpname].value = eval(tmp)
     367
     368             if (len(tokens) == 2) and (len(active_variable_name) == 0):
     369                 
     370                # in the case of name over-flow, there are only two tokens
     371                # on the first of two lines for the variable entry.
     372                number_of_variables_read = number_of_variables_read + 1
     373                active_variable_name = tokens[1].strip()
     374                index = eval(tokens[0].strip())
     375
     376                # sanity check - the indices should be in sequence.
     377                if index != number_of_variables_read:
     378                   raise ValueError,"***ERROR: Unexpected variable index encountered on line="+line+"; expected value="+str(number_of_variables_read)+"; actual value="+str(index)                   
     379               
     380             else:
     381                 
     382                index = None
     383                activity = None
     384                lower_bound = None
     385                upper_bound = None
     386                marginal = None
     387
     388                # extract the field names and process accordingly. there
     389                # is some wasted processing w.r.t. single versus double-line
     390                # entries, but it's not significant enough to worry about.
     391
     392                index_string = line[0:6].strip()
     393                name_string = line[7:19].strip()
     394                state_string = line[20:22].strip()
     395                activity_string = line[23:36].strip()
     396                lower_bound_string = line[37:50].strip()
     397                upper_bound_string = line[51:64].strip()
     398                marginal_string = line[65:78].strip()
     399
     400                # skip any headers
     401                if (index_string == "------") or (index_string == "No."):
     402                   continue               
     403
     404                if len(index_string) > 0:
     405                   index = eval(index_string)
     406                if (activity_string != "< eps") and (len(activity_string) > 0):
     407                   activity = eval(activity_string)
     408                else:
     409                   activity = 0.0
     410                if (lower_bound_string != "< eps") and (len(lower_bound_string) > 0):
     411                   lower_bound = eval(lower_bound_string)
     412                else:
     413                   lower_bound = 0.0
     414                if state_string != "NS":                   
     415                   if (upper_bound_string != "< eps") and (len(upper_bound_string) > 0):
     416                      upper_bound = eval(upper_bound_string)
     417                   else:
     418                      upper_bound = 0.0
     419                if (marginal_string != "< eps") and (len(marginal_string) > 0):
     420                   marginal = eval(marginal_string)
     421                else:
     422                   marginal = 0.0
     423
     424                variable_name = None
     425                if len(active_variable_name) > 0:
     426                   # if there is an active variable name, the identifier was
     427                   # too long for everything to be on a single line; the second
     428                   # line contains all of the value information.
     429                   variable_name = active_variable_name
     430                   active_variable_name = ""
     431                else:
     432                   # everything is on a single line.
     433                   variable_name = name_string
     434                   number_of_variables_read = number_of_variables_read + 1
     435                   # sanity check - the indices should be in sequence.
     436                   if index != number_of_variables_read:
     437                      raise ValueError,"***ERROR: Unexpected variable index encountered on line="+line+"; expected value="+str(number_of_variables_read)+"; actual value="+str(index)                                           
     438                   
     439                # the "activity" column always specifies the variable value.
     440                # embedding the if-then-else to validate the basis status.
     441                # we are currently ignoring all bound-related information.
     442                variable_value = None
     443                if state_string == "B":
     444                   variable_value = activity
     445                elif (state_string == "NL") or (state_string == "NS") or (state_string == "NU"):
     446                   variable_value = activity
     447                else:
     448                   raise ValueError, "Unknown status="+state_string+" encountered for variable="+active_variable_name+" in line="+line+" of solution file="+self.soln_file
     449               
     450                soln.variable[variable_name].value = variable_value
     451               
     452             # if all of the variables have been read, exit.
     453             if number_of_variables_read == results.problem.number_of_variables:
     454                state = -1
     455             
    317456          if state==-1:
    318457             break
     458         
    319459        INPUT.close()
    320 
    321 
    322460
    323461class MockGLPK(GLPK,mockmip.MockMIP):
Note: See TracChangeset for help on using the changeset viewer.