Class RectanglesPlacement

java.lang.Object
topics.branchandbound.utils.BranchAndBound
topics.branchandbound.rectangles.RectanglesPlacement
public class RectanglesPlacement extends BranchAndBound

Optimal Placement of Rectangles

This class solves a 2D bin packing variant where a given set of rectangular pieces must be placed on an N × N grid. The objective is to minimize the bounding box area of the placed pieces. It utilizes a Branch and Bound algorithm to systematically evaluate positions and orientations while pruning sub-optimal configurations.

*

Complexity

  • Time Complexity: O((2 × N²)P) - Where N is the board dimension and P is the number of pieces. For each piece, the algorithm explores all grid cells in two orientations. Bounding heuristics heavily prune this theoretical worst-case.
  • Space Complexity: O(N²) per state node - Required for storing the 2D matrix representing the board configuration.
Author:
vicegd

  • Constructor Details

    • RectanglesPlacement

      public RectanglesPlacement(int boardSize, List<Piece> pieces)
      Initializes the problem solver and establishes the execution tree root.
      Parameters:
      boardSize - The dimension of the square board (N × N).
      pieces - The collection of rectangular pieces to be placed.