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