Class RectanglesPlacementThreads

java.lang.Object
topics.branchandbound.utils.threads.BranchAndBoundThreads
topics.branchandbound.rectangles.RectanglesPlacementThreads
public class RectanglesPlacementThreads extends BranchAndBoundThreads

Optimal Placement of Rectangles (Concurrent Execution)

This class solves the 2D bin packing variant where a given set of rectangular pieces must be placed on an N × N grid to minimize the bounding box area. It extends the multithreaded Branch and Bound framework to evaluate multiple branches of the state space tree simultaneously, leveraging parallel execution for performance gains on multi-core architectures.

*

Complexity

  • Time Complexity: O((2 × N²)P) - The theoretical worst-case remains exponential relative to the grid size N and pieces P. However, concurrent evaluation accelerates the discovery of tight upper bounds, triggering earlier and more aggressive global pruning across parallel threads.
  • Space Complexity: O(T × N²) - Where T is the number of concurrent worker threads. Each thread requires isolated memory allocation to track its specific subset of board configurations during traversal.
Author:
vicegd

  • Constructor Details

    • RectanglesPlacementThreads

      public RectanglesPlacementThreads(int boardSize, List<Piece> pieces)
      Initializes the concurrent 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 optimally placed.