1# * Copyright 2016, NICTA 2# * 3# * This software may be distributed and modified according to the terms 4# of 5# * the BSD 2-Clause license. Note that NO WARRANTY is provided. 6# * See "LICENSE_BSD2.txt" for details. 7# * 8# * @TAG(NICTA_BSD) 9#!/usr/bin/env python2 10import sys, subprocess, re, os 11 12 13unbounded = "unbounded" 14infeasible = "Integer infeasible." 15 16#this cplex footer ends a .ilp file and does 17cplex_end_command=''' 18End 19''' 20 21cplex_footer2=''' 22optimize 23display solution objective 24display solution variables - 25quit 26''' 27 28cplex_presolve_off=''' 29set 30preprocessing 31presolve 32n 33''' 34 35def rmSol(sol_file): 36 '''remove existing solution file if it exists''' 37 #stop rm from complaining without using the dangerous -f flag 38 p = subprocess.Popen(['test','-e',sol_file]) 39 p.communicate() 40 if p.returncode ==0: 41 p = subprocess.Popen(['rm',sol_file]) 42 p.communicate() 43 44 45def cplexSolve(ilp_file_name,silent=True,sol_file=None,expect_unbounded=False): 46 '''call cplex on the specified ilp file''' 47 cplex = 'cplex' 48 if sol_file == None: 49 #This is where Chronos stores the sol file by default, [:-4] removes the .ilp extension 50 sol_file = ilp_file_name[:-4] + ".sol" 51 rmSol(sol_file) 52 f_ilp = open(ilp_file_name, 'r') 53 p = subprocess.Popen(cplex,stdin=f_ilp,stdout=subprocess.PIPE,stderr=subprocess.PIPE) 54 print 'cplex called' 55 out,err = p.communicate() 56 if not silent: 57 print out 58 ret = p.returncode 59 print 'cplex terminated' 60 if not expect_unbounded and (ret or (infeasible in err or infeasible in out) or (unbounded in err or unbounded in out)): 61 print 'ilp solver FAILED \nout : %s \nerr: %s\n'%(out,err) 62 print 'note that infeasible/unbounded can mean the other, turn off the presolver to investiage which is the case' 63 return False 64 return parseSolFile(sol_file, expect_unbounded) 65 66def parseSolFile (sol_file, expect_unbounded): 67 objective_regex = r".*Objective\s*=\s*(?P<value>.*)\n" 68 f_out = open(sol_file,'r') 69 for line in f_out: 70 if re.search(unbounded,line) or re.search(infeasible, line): 71 if expect_unbounded: 72 return unbounded 73 assert False and "Infeasible/unbounded ilp !!!" 74 match = re.search(objective_regex,line) 75 if match: 76 f_out.close() 77 return match.group ('value') 78 assert match, "Failed to regex cplex output" 79 80def stripFooter(ilp_file): 81 '''strip the footer off the ilp file''' 82 f_ilp = open(ilp_file, 'r') 83 print "ilp_file %s" % ilp_file 84 stripped_name = ilp_file+'_nofooter' 85 stripped = open (stripped_name, 'w') 86 for line in f_ilp: 87 if re.search(r'^End',line): 88 #we are done 89 break 90 stripped.write(line) 91 stripped.close() 92 f_ilp.close() 93 print 'footer stripped, %s generated' % stripped_name 94 return stripped_name 95 96def endProblem(f_ilp,sol_file_name): 97 f_ilp.write(cplex_end_command) 98 f_ilp.write('set logfile %s\n' % sol_file_name) 99 100def solveProblem(f_ilp,presolve_off=False): 101 if presolve_off: 102 f_ilp.write(cplex_presolve_off) 103 f_ilp.write(cplex_footer2) 104 105def varsUnbounded(var_s,rest): 106 tmp_name = "./temp_ilp.ilp" 107 sol_name = tmp_name + ".sol" 108 tmp_f = open(tmp_name,'w') 109 tmp_f.write("enter Q\nMaximize\n") 110 for (i,var) in enumerate(var_s): 111 if i != 0: 112 tmp_f.write("+ ") 113 tmp_f.write("1 %s"% var) 114 for line in rest: 115 if "set logfile" in line: 116 tmp_f.write("set logfile " + sol_name + "\n") 117 else: 118 tmp_f.write(line) 119 tmp_f.flush() 120 ret_val = cplexSolve(tmp_name, silent=True, sol_file= sol_name, expect_unbounded=True) 121 #os.remove(tmp_name) 122 return ret_val == unbounded 123 124def findUnboundedVar(ilp_f_name): 125 lp_f = open(ilp_f_name) 126 lines = lp_f.readlines() 127 for (i,line) in enumerate(lines): 128 if 'Maximize' not in line: 129 continue 130 i = i+ 1 131 break 132 while lines[i].strip() == '': 133 i = i +1 134 print "found maximized term: " 135 rest_ilp = lines [i+1:] 136 137 line = lines[i] 138 terms = line.split('+') 139 var_s = [] 140 for term in terms: 141 x = term.strip() 142 x = x.split() 143 #discard the coeeficent 144 var_s.append(x[-1]) 145 print "there are %d variables" % len(var_s) 146 n = len(var_s) 147 while len(var_s) > 1: 148 print 'n= %d, 0: %d, %d: \n' % (n,n/2,n/2) 149 var_s_1= var_s[0:n/2] 150 var_s_2= var_s[n/2:] 151 print 'var_s_1 %d var_s_2 %d' % (len(var_s_1),len(var_s_2)) 152 if varsUnbounded (var_s_1,rest_ilp): 153 print "unbounded in bot half" 154 var_s = var_s_1 155 else: 156 if not varsUnbounded(var_s_2,rest_ilp): 157 print "what !?" 158 print "vars[0]: %s, [-1]: %s" % (var_s[0],var_s[-1]) 159 assert False 160 161 print "unbounded in top half" 162 var_s = var_s_2 163 n = len(var_s) 164 165 print "the unbounded variable is : %s" % str(var_s) 166 assert len(var_s) == 1 167 168def printUsage(): 169 print 'usage: <some ilp file> [OPTION]' 170 print 'options: --x: run cplex --f: strip footer' 171 172if __name__ == '__main__': 173 if len(sys.argv) != 3: 174 printUsage() 175 sys.exit(1) 176 ilp_f_name = sys.argv[1] 177 flag = sys.argv[2] 178 if flag == '--x': 179 ret = cplex(ilp_f_name) 180 print 'result : %f' % ret 181 elif flag == '--f': 182 stripFooter(ilp_f_name) 183 elif flag == '--u': 184 print 'finding unbounded variable' 185 findUnboundedVar(ilp_f_name) 186 else: 187 printUsage() 188 sys.exit(1) 189