  We consider the bin packing problem with d different item sizes s_i and item
multiplicities a_i, where all numbers are given in binary encoding. This
problem formulation is also known as the 1-dimensional cutting stock problem.
  In this work, we provide an algorithm which, for constant d, solves bin
packing in polynomial time. This was an open problem for all d >= 3.
  In fact, for constant d our algorithm solves the following problem in
polynomial time: given two d-dimensional polytopes P and Q, find the smallest
number of integer points in P whose sum lies in Q.
  Our approach also applies to high multiplicity scheduling problems in which
the number of copies of each job type is given in binary encoding and each type
comes with certain parameters such as release dates, processing times and
deadlines. We show that a variety of high multiplicity scheduling problems can
be solved in polynomial time if the number of job types is constant.
