Hello,
as a new user of the PyMathProg library I'm trying to come up with an integer linear program formulation for
an assignment problem similar to your example at
http://pymprog.sourceforge.net/advanced.html
but with additional constraints.
My problem is that, even though I declared my variables boolean and using the integer solver,
I end up with a solution that does not seem to be an integer, but a relaxed solution to my problem.
I would very much appreciate if you could give me some advice on whether I'm using the solver correctly.
A minimal example of the code I'm running is as follows, while a more reader friendly formulation can be found
in the attachment.
def example(c, l, m, n):
'''
m = number of agents
n = number of tasks
nxn cost matrix filled with positive real values
c = costmatrix
nxn linking constraint matrix filled with boolean values
diagonal values are all zero
l = linking matrix
'''
from numpy import reshape, array
## transpose linking matrix
l = array(l).T
l = l.tolist()
n = len(c[0])
m = len(c)
N = range(n)
M = range(m)
print 'Minimize:'
print ' sum_{i=1}^{n}sum_{i=1}^{n} c_{ij}x_{ij}'
print 'Subject to:'
print '(1) sum_{j=1}^{n} x_{ij} = 1, for all i in {1,2,...,n}'
print ' \"Every SeqPos can have max. one assigned Residue.\"'
print '(2) sum_{i=1}^{n} x_{ij} = 1, for all j in {1,2,...,n}'
print ' \"Every Residue can be assigned to max one SeqPos.\"'
print '(3) x_{ij+1} <= (L^TX)_{ij},'
print ' for all i in {1,2,...,n} and for all j in {1,2,...,n-1}'
print ' \"Assignment has to be consistent with linking, s.t.'
print ' IF residue k is assigned to sequence position j,'
print ' THEN position j+1 can only be assigned to a residue k\''
print ' that is a valid successor of residue k, that is'
print ' when L[k][k\'] = 1\"'
print
beginModel("assign")
verbose(True) #Turn on this for model output
A = iprod(M, N) #combine index
#declare variables
x = var(A, 'x', kind=bool) #assignment decision vars
#declare parameters:
tc = par(c, 'C') ## cost matrix
lt = par(l, 'L') ## linking matrix (transposed)
minimize(sum(tc[i][j] * x[i, j] for i, j in A), 'totalcost') ## objective
st([sum(x[k, j] for j in N) == 1 for k in M], 'residue')
st([sum(x[i, k] for i in M) == 1 for k in N], 'sequence pos')
st([x[i, j + 1] <= sum(lt[i][k] * x[k, j] for k in N) for i, j in A if j < (n - 1)], 'linking')
solve('int') ## integer solver
assign = [(i, j) for i in M for j in N if x[i, j].primal > .5]
endModel()
X = reshape([x[i, j].primal for i in range(n) for j in range(n)], (n, n))
return assign, X
if __name__ == "__main__":
m = 4 # residues
n = 4 # sequence positions
c = [[.0, .1, .1, .1],
[.1, .0, .1, .1],
[.1, .1, .0, .1],
[.1, .1, .1, .0]]
l = [[0, 1, 0, 1],
[0, 0, 1, 1],
[0, 0, 0, 1],
[1, 1, 1, 0]]
assign, X = example(c, l, m, n)
print 'X= '
print X
---------------------------
Jens Hooge
AG Bernhard Schölkopf
Department: Machine Learning
Max Planck Institute for Intelligent Systems
Spemannstr. 38
72076 Tübingen
Phone: +49-7071-601557
http://www.kyb.tuebingen.mpg.de/nc/employee/details/jhooge.html
|
