Hungarian Algorithm



In [2]:

    
import opengm
import numpy


numObjects = 4
costs = numpy.random.rand(numObjects,numObjects)
print costs









    



[[ 0.12206616  0.16525182  0.39458393  0.34575197]
 [ 0.16809962  0.4718343   0.03370519  0.66328466]
 [ 0.19978097  0.26276099  0.28855966  0.65837158]
 [ 0.83885196  0.78894048  0.07254031  0.61332373]]

Soft Constraint GM



In [3]:

    
gm = opengm.gm([numObjects]*numObjects)

unaryIds = gm.addFunctions(costs)
gm.addFactors(unaryIds,numpy.arange(numObjects))

f1To1=opengm.pottsFunction([numObjects,numObjects],10000.0, 0.0)
f1To1Id=gm.addFunction(f1To1)

for x0 in range(numObjects):
    for x1 in range(x0+1,numObjects):
        gm.addFactor(f1To1Id,[x0,x1])

Inference with Lazy Flipper



In [4]:

    
Inf = opengm.inference.LazyFlipper
param = opengm.InfParam(maxSubgraphSize=1)
inf = Inf(gm=gm,parameter=param)
inf.infer()
arg = inf.arg()
print arg, gm.evaluate(arg)
print len(numpy.unique(arg))









    



[1 2 3 0] 1.69618053991
4



In [5]:

    
Inf = opengm.inference.LazyFlipper
param = opengm.InfParam(maxSubgraphSize=2)
inf = Inf(gm=gm,parameter=param)
# use warm start
inf.setStartingPoint(arg)
inf.infer()
arg = inf.arg()
print arg, gm.evaluate(arg)
print len(numpy.unique(arg))









    



[1 2 0 3] 1.01206170853
4



In [6]:

    
Inf = opengm.inference.LazyFlipper
param = opengm.InfParam(maxSubgraphSize=3)
inf = Inf(gm=gm,parameter=param)
inf.infer()
# use warm start
inf.setStartingPoint(arg)
arg = inf.arg()
print arg, gm.evaluate(arg)
print len(numpy.unique(arg))









    



[1 2 0 3] 1.01206170853
4

Hard Constraint GM



In [7]:

    
gmB = opengm.gm([numObjects]*numObjects)

unaryIds = gmB.addFunctions(costs)
gmB.addFactors(unaryIds,numpy.arange(numObjects))









    Out[7]:





3L

Inference with LpCplex



In [7]:

    
cplexParam = opengm.InfParam(integerConstraint=True)
lpCplex = opengm.inference.LpCplex(gm=gm,parameter=cplexParam)


for x0 in range(numObjects):
    for x1 in range(x0+1,numObjects):
        
        for label in range(numObjects):
            lpVarx0  = lpCplex.lpNodeVariableIndex(x0,label)
            lpVarx1  = lpCplex.lpNodeVariableIndex(x1,label)
            constraintVars  = [lpVarx0,lpVarx1]
            constraintCoeff = [1.0,1.0]
            lowerBound = 0.0
            upperBound = 1.0
            lpCplex.addConstraint(constraintVars,constraintCoeff,lowerBound,upperBound)
            
            
lpCplex.infer()
arg = lpCplex.arg()
print arg, gm.evaluate(arg)
print len(numpy.unique(arg))









    



[4 3 1 2 0] 1.2429384696
5