partition problem

The Overflowing Bin Packing Problem: Theoretical Results and a New Flow Formulation

  • John Martinovic
  • Nico Strasdat
    • Categories (Mixed) Integer Linear Programming Tags , , , ,

    We consider a recently proposed one-dimensional packing problem, called the overflowing bin packing problem (OBPP). In this scenario, we are given a set of items (of known sizes) and a set of bins (of known capacities). Roughly speaking, the task is to assign the items to the bins in such a way that the total … Read more

    Recognizing Integrality of Weighted Rectangles Partitions

  • Paul Deuker
  • Ulf Friedrich
    • Categories (Mixed) Integer Linear Programming Tags , ,

    The weighted rectangles partitioning (WRP) problem is defined on a set of active and inactive pixels. The problem is to find a partition of the active pixels into weighted rectangles, such that the sum of their weights is maximal. The problem is formulated as an integer programming problem and instances with an integral relaxation polyhedron … Read more