/usr/share/pyshared/openopt/solvers/HongKongOpt/QPSparse.py is in python-openopt 0.34+svn1146-1build1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 | """
pname, e, Q, A=None, b=None, Aeq=None, beq=None, lb=None, ub=None, c0 = MPSparse(filename)
Reads the description of a QP problem from a file in the extended
MPS format (QPS) described by Istvan Maros and Csaba Meszaros at:
http://www.sztaki.hu/~meszaros/public_ftp/qpdata/qpdata.ps
Returns a tuple (pname, e, Q, Aeq, beq, lb, ub, c0)
name: string
all others: numpy arrays
QPS Format:
The QP problems are assumed to be in the following form:
min f(x) = e'x + 1/2 x' Q x, Q symmetric and positive semidefinite
subject to Aeq x = beq,
l <= x <= u.
After the BOUNDS section of MPS there is an new section introduced
by a QUADOBJ record followed by columnwise elements of Q; row and
columns are column names of A. Being the matrix symmetrical,
only lower triangular elements are listed.
---------------------------------------------------------------------
Field: 1 2 3 4 5 6
Columns: 2-3 5-12 15-22 25-36 40-47 50-61
0 1 2 3 4 5 6
1234567890123456789012345678901234567890123456789012345678901 << column
11 22222222 33333333 444444444444 55555555 666666666666 << field
---------------------------------------------------------------
NAME problem name
ROWS
type name
COLUMNS
column row value row value
name name name
RHS
rhs row value row value
name name name
RANGES
range row value row value
name name name
BOUNDS
type bound column value
name name
ENDATA
---------------------------------------------------------------------
---------------------------------------------------------------
NAME QP example
ROWS
N obj
G r1
L r2
COLUMNS
11 22222222 33333333 444444444444 55555555 666666666666 << field
c1 r1 2.0 r2 -1.0
c1 obj 1.5
c2 r1 1.0 r2 2.0
c2 obj -2.0
RHS
rhs1 r1 2.0 r2 6.0
BOUNDS
UP bnd1 c1 20.0
QUADOBJ
c1 c1 8.0
c1 c2 2.0
c2 c2 10.0
ENDATA
---------------------------------------------------------------
"""
from numpy import *
def QPSparse(filename):
pname = e = Q = A = b = Aeq = beq = lb = ub = None # defaults for ret. params
c0 = 0.
f = open(filename, 'r')
section = None
rowtype = {} # dict of row type corresponding to a given row name
colnum = {} # dict of col number corresponding to a given col name
colcnt = 0 # counter of columns
acnt = 0 # counter of inequalities (up to size of A matrix)
aeqcnt = 0 # counter of equalities (up to size of Aeq matrix)
aindx = {} # dict of row number in A matrix corresponding to a given row name
aeqindx = {} # dict of row number in Aeq matrix corresponding to a given row name
objcoef = {} # dict of coefficient in obj function corresponding to a given column name
RHSdic = {} # dict containing {row_name, RHSvalue}
RANGESdic = {} # dict containing {row_name, RANGEvalue}
ucnt = 0
qcnt = 0
lineno = 0
for line in f:
lineno += 1
line = line.upper().strip("\n\r")
f1 = line[1:3].strip()
f2 = line[4:12].strip()
f3 = line[14:22].strip()
f4 = line[24:36].strip().replace('D','E')
f4 = 0. if f4 == "" else float(f4)
f5 = line[39:47].strip()
f6 = line[49:61].strip().replace('D','E')
f6 = 0. if f6 == "" else float(f6)
if line[0] != ' ': # indicator record, switches current section
# see which section is being closed, and take appropriate action
if section == 'ROWS': # being closed
# we know how many rows we have. Allocate lists of lists for A, Aeq
# Alist[n][colname] contains coeff for row n and col name colname in Aeq
Alist = [{} for i in range(acnt)]
# Aeqlist[n][colname] contains coeff for row n and col name colname in Aeq
Aeqlist = [{} for i in range(aeqcnt)]
elif section == 'COLUMNS': # being closed
# we know how any columns we have (colcnt). So we can now build Q, ub and lb
Q = zeros((colcnt,colcnt))
ub = array([Inf]*colcnt)
lb = zeros(colcnt)
elif section == 'RHS': # being closed
pass # b, beq and c0 have been already set up
elif section == 'RANGES': # being closed
pass # TODO: add ranges
elif section == 'BOUNDS': # being closed
if ucnt == 0:
ub = None
elif section == 'QUADOBJ': # being closed
if qcnt == 0:
Q = None
# set the section indicator according to the new section
if f1 == 'AM':
section = 'NAME' # being opened
elif f1 == 'OW':
section = 'ROWS' # being opened
elif f1 == 'OL':
section = 'COLUMNS' # being opened
elif f1 == 'HS':
section = 'RHS' # being opened
elif f1 == 'AN':
section = 'RANGES' # being opened
elif f1 == 'OU':
section = 'BOUNDS' # being opened
elif f1 == 'UA':
section = 'QUADOBJ' # being opened
elif f1 == 'ND':
section = None
break;
else:
f.close()
raise(ValueError('invalid indicator record in line '+str(lineno)+': "'+line+'"'))
elif section == 'NAME':
pname = f3
elif section == 'ROWS':
rname = f2
if f1 == 'N':
rowtype[rname] = 'N'
obj = rname
elif f1 == 'G':
rowtype[rname] = 'G'
aindx[rname] = acnt
acnt += 1
elif f1 == 'L':
rowtype[rname] = 'L'
aindx[rname] = acnt
acnt += 1
elif f1 == 'E':
rowtype[rname] = 'E'
aeqindx[rname] = aeqcnt
aeqcnt += 1
else:
f.close()
raise(ValueError('invalid row type "'+f1+'" in line '+str(lineno)+': "'+line+'"'))
elif section == 'COLUMNS':
cname = f2
rnames = [0,0]
vals = [0,0]
if cname not in colnum:
colnum[cname] = colcnt # alocate a new column number
colcnt += 1
rnames[0] = f3
vals[0] = f4
rnames[1] = f5
vals[1] = f6
for i in (0,1): # both are possible
rn = rnames[i]
value = vals[i]
if rn == '':
break
if rn == obj: # then value is the coefficient of col cname in the obj function
objcoef[cname] = value
elif rowtype[rn] == 'L': #
Alist[aindx[rn]][cname] = value
elif rowtype[rn] == 'G': #
Alist[aindx[rn]][cname] = -value
elif rowtype[rn] == 'E': #
Aeqlist[aeqindx[rn]][cname] = value
elif section == 'RHS':
# What is the RHS name for????
rnames = [0,0]
vals = [0,0]
rnames[0] = f3
vals[0] = f4
rnames[1] = f5
vals[1] = f6
for i in (0,1): # both are possible
rname = rnames[i]
value = vals[i]
if rname == '':
break
RHSdic[rname] = value
elif section == 'RANGES':
# What is the RANGE name for????
rnames = [0,0]
vals = [0,0]
rnames[0] = f3
vals[0] = f4
rnames[1] = f5
vals[1] = f6
for i in (0,1): # both are possible
rname = rnames[i]
value = vals[i]
if rname == '':
break
RANGESdic[rname] = value
elif section == 'BOUNDS':
# by default, x >= 0
# what is the Bound name in f2 for???
# UP : x <= b, x >= 0
# LO : x >= b
# FX : x == b
# FR : (no bound: remove default >= 0)
# MI : x > -Inf
# BV : x in (0, 1) # NOT SUPPORTED
ic = colnum[f3]
val = f4
if f1 == 'UP':
ub[ic] = f4
ucnt += 1
elif f1 == 'LO':
lb[ic] = f4
elif f1 == 'FX':
# TODO add an equality constraint
raise(ValueError('fixed variable (FX) bound not supported in line '+str(lineno)+': "'+line+'"'))
elif f1 == 'FR':
lb[ic] = -Inf
ub[ic] = Inf
elif f1 == 'MI':
lb[ic] = -Inf
elif f1 == 'BV':
raise(ValueError('binary value (BV) bound not supported in line '+str(lineno)+': "'+line+'"'))
elif section == 'QUADOBJ':
ic1 = colnum[f2]
ic2 = colnum[f3]
val = f4
Q[ic1,ic2] = val
if ic1 != ic2: # if not on diagonal
Q[ic2,ic1] = val
qcnt += 1
f.close()
if section != None:
raise(EOFError('unexpected EOF while in section '+section))
# Now we have all necessary info and we can build A,b,Aeq and Beq
if acnt > 0:
A = zeros((acnt, colcnt))
b = zeros(acnt)
for rn in range(acnt):
for c in Alist[rn]:
A[rn, colnum[c]] = Alist[rn][c]
if aeqcnt > 0:
Aeq = zeros((aeqcnt, colcnt))
beq = zeros(aeqcnt)
for rn in range(aeqcnt):
for c in Aeqlist[rn]:
Aeq[rn, colnum[c]] = Aeqlist[rn][c]
# ########## process RHS
for rname in RHSdic:
value = RHSdic[rname]
rt = rowtype[rname]
if rt == 'L': #
b[aindx[rname]] = value # constant term in obj function
elif rt == 'G': #
b[aindx[rname]] = -value
elif rt == 'E': #
beq[aeqindx[rname]] = value
elif rt == 'N':
c0 = -value # constant term in obj function
# Handle RANGE lines. Each range causes a duplicate of a
# row in A and b, and a modification of original and new b.
"""
D. The RANGES section is for constraints of the form: h <= constraint <= u .
The range of the constraint is r = u - h . The value of r is specified
in the RANGES section, and the value of u or h is specified in the RHS
section. If b is the value entered in the RHS section, and r is the
value entered in the RANGES section, then u and h are thus defined:
row type sign of r h u
----------------------------------------------
L + or - b - |r| b
G + or - b b + |r|
E + b b + |r|
E - b - |r| b
"""
if A != None:
addA = zeros((len(RANGESdic),A.shape[1]))
addb = zeros(len(RANGESdic))
for rname in RANGESdic:
index = aindx[rname] # row index in A and index in b
value = RANGESdic[rname]
rt = rowtype[rname]
if rt == 'L': #
b1 = b[index] + abs(value) # sign???
elif rt == 'G': #
b1 = b[index] - abs(value) # sign???
elif rt == 'E': #
raise(ValueError('RANGES for rows of type E not yet supported in line '+str(lineno)+': "'+line+'"'))
#b1 = b[index] - value
addA[index,:] = -A[index,:] # append to A duplicate of index row, with sign changed
addb[index] = -b1 # append to b other extreme, with sign changed
A = vstack([A, addA])
b = concatenate([b, addb])
e = zeros(colcnt)
for c in objcoef:
e[colnum[c]] = objcoef[c]
# suppress redundant lb/ub
nvars = e.shape[0]
if lb != None and (lb == array([-Inf]*nvars)).all():
lb = None
if ub != None and (ub == array([Inf]*nvars)).all():
ub = None
return (pname, e, Q, A, b, Aeq, beq, lb, ub, c0)
|