"""
bpp.py:  use gurobi for solving the bin packing problem.

The instance of the bin packing problem is represented by the two
lists of n items of sizes and quantity s=(s_i).
The bin size is B.

We use Martello and Toth (1990) formulation, and suggest
extensions with tie-breaking and SOS constraints.

Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2012
"""

from gurobipy import *

def FFD(s,B):
    """First Fit Decreasing heuristics for the Bin Packing Problem.
    Parameters:
        - s: list with item widths
        - B: bin capacity
    Returns a list of lists with bin compositions.
    """    
    remain = [B]        # keep list of empty space per bin
    sol = [[]]          # a list ot items (i.e., sizes) on each used bin
    for item in sorted(s,reverse=True):
        for (j,free) in enumerate(remain):
            if free >= item:
                remain[j] -= item
                sol[j].append(item)
                break
        else: #does not fit in any bin
            sol.append([item])
            remain.append(B-item)
    return sol    


def bpp(s,B):
    """bpp: Martello and Toth's model to solve the bin packing problem.
    Parameters:
        - s: list with item widths
        - B: bin capacity
    Returns a model, ready to be solved.
    """
    n = len(s)
    U = len(FFD(s,B)) # upper bound of the number of bins
    model = Model("bpp")
    # setParam("MIPFocus",1)
    x,y = {},{}
    for i in range(n):
        for j in range(U):
            x[i,j] = model.addVar(vtype="B", name="x(%s,%s)"%(i,j))
    for j in range(U):
        y[j] = model.addVar(vtype="B", name="y(%s)"%j)    
    model.update()

    # assignment constraints
    for i in range(n):
        model.addConstr(quicksum(x[i,j] for j in range(U)) == 1, "Assign(%s)"%i)

    # bin capacity constraints
    for j in range(U):
        model.addConstr(quicksum(s[i]*x[i,j] for i in range(n)) <= B*y[j], "Capac(%s)"%j)

    # tighten assignment constraints
    for j in range(U):
        for i in range(n):
            model.addConstr(x[i,j] <= y[j], "Strong(%s,%s)"%(i,j))
        
##    # tie breaking constraints
##    for j in range(U-1):
##        model.addConstr(y[j] >= y[j+1),"TieBrk(%s)"%j)
##
##    # SOS constraints
##    for i in range(n):
##        model.addSOS(1,[x[i,j] for j in range(U)])

    model.setObjective(quicksum(y[j] for j in range(U)), GRB.MINIMIZE)

    model.update()
    model.__data = x,y
    return model


def solveBinPacking(s,B):
    """solveBinPacking: use an IP model to solve the in Packing Problem.
    
    Parameters:
        - s: list with item widths
        - B: bin capacity

    Returns a solution: list of lists, each of which with the items in a roll.
    """
    n = len(s)
    U = len(FFD(s,B)) # upper bound of the number of bins
    model = bpp(s,B)
    x,y = model.__data

    model.optimize()
    
    bins = [[] for i in range(U)]
    for (i,j) in x:
        if x[i,j].X > .5:
            bins[j].append(s[i])
    for i in range(bins.count([])):
        bins.remove([])
    for b in bins:
        b.sort()
    bins.sort()
    return bins


import random
def DiscreteUniform(n=10,LB=1,UB=99,B=100):
    """DiscreteUniform: create random, uniform instance for the bin packing problem."""
    B = 100
    s = [0]*n
    for i in range(n):
        s[i] = random.randint(LB,UB)
    return s,B


if __name__ == "__main__":
    random.seed(256)
    s,B = DiscreteUniform()
    print "items:",s
    print "bin size:",B
    
    ffd = FFD(s,B)
    print "\n\n\nSolution of FFD:"
    print ffd
    print len(ffd),"bins"
    
    print "\n\n\nBin packing problem:"
    bins = solveBinPacking(s,B)
    print len(bins),"bins:"
    print bins