"""
mkp.py: model for the multi-constrained knapsack problem
    
Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2012
"""
from gurobipy import *

def mkp(I,J,v,a,b):
    """mkp -- model for solving the multi-constrained knapsack
    Parameters:
        - I: set of dimensions
        - J: set of items
        - v[j]: value of item j
        - a[i,j]: weight of item j on dimension i
        - b[i]: capacity of knapsack on dimension i
    Returns a model, ready to be solved.
    """
    model = Model("mkp")
    x = {}
    for j in J:
        x[j] = model.addVar(vtype="B", name="x(%s)"%j)
    model.update()
     
    for i in I:
        model.addConstr(quicksum(a[i,j]*x[j] for j in J) <= b[i], "Capacity(%s)"%i)

    model.setObjective(quicksum(v[j]*x[j] for j in J), GRB.MAXIMIZE)

    model.update()
    return model


def example():
    J,v = multidict({1:16, 2:19, 3:23, 4:28})
    a = {(1,1):2,    (1,2):3,    (1,3):4,    (1,4):5,
         (2,1):3000, (2,2):3500, (2,3):5100, (2,4):7200,
         }
    I,b = multidict({1:7, 2:10000})
    return I,J,v,a,b


if __name__ == "__main__":
    I,J,v,a,b = example()
    model = mkp(I,J,v,a,b)
    model.optimize()
    print "Optimal value=",model.ObjVal

    EPS = 1.e-6
    for v in model.getVars():
        if v.X > EPS:
            print v.VarName,v.X