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