[pymprog] Integer Linear Program Formulation

[Jens H. <jen...@tu...>]

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