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 , , ,

    Given a grid of active and inactive pixels, the weighted rectangles partitioning (WRP) problem is to find a maximum-weight partition of the active pixels into rectangles. WRP is formulated as an integer programming problem and instances with an integral relaxation polyhedron are characterized by a balanced problem matrix. A complete characterization of these balanced instances … Read more