maxcut.py

def solve_sparse(C):
    """Solve using the low level interface

    """

    if not scipy.sparse.isspmatrix_coo(C):
        raise ValueError("needs COO input")

    n, _ = C.shape

    def streamprinter(text):
        sys.stdout.write(text)
        sys.stdout.flush()

    # MOSEK's API is absolutely horrible

    # Make mosek environment
    env = mosek.Env()

    # Create a task object and attach log stream printer
    task = env.Task(0,0)
    task.set_Stream(mosek.streamtype.log, streamprinter)

    # lower triangle of laplacian
    barci, barcj, barcval = [], [], []
    for v, (i, j) in zip(C.data, zip(C.row, C.col)):
        if j > i:
            continue
        barci.append(i)
        barcj.append(j)
        barcval.append(v)

    task.appendcons(n)
    task.appendbarvars([n])

    for i in xrange(n):
        task.putconbound(i, mosek.boundkey.fx, 1.0, 1.0)

    symc = task.appendsparsesymmat(n, barci, barcj, barcval)
    task.putbarcj(0, [symc], [1.0])

    for i in xrange(n):
        syma = task.appendsparsesymmat(n, [i], [i], [1.])
        task.putbaraij(i, 0, [syma], [1.0])

    task.putobjsense(mosek.objsense.maximize)
    task.writedata('maxcut.task')

    print "calling optimize()"
    start = time.time()
    task.optimize()
    end = time.time()
    task.solutionsummary(mosek.streamtype.msg)

    prosta = task.getprosta(mosek.soltype.itr)
    solsta = task.getsolsta(mosek.soltype.itr)

    if solsta not in (mosek.solsta.optimal, mosek.solsta.near_optimal):
        raise ValueError("did not converge")

    return task.getprimalobj(mosek.soltype.itr), (end - start)