This project showcases different implementations of multiple generic optimization algorithms, applied to the problem of Rectangle Packing (also commonly called "Bin packing").
It consists of
- generic (problem-agnostic) algorithm implementations in the backend, plus components specific to Rectangle Packing,
- a UI allowing you to run different configurations of algorithms on instances of the problem,
- a benchmarking environment for running the algorithms against a number of generated problem instances to compare their scores and runtimes.
Given a set of rectangles and a size for the boxes, place those rectangles within a minimum number of square boxes (" bins") of that predefined size such that the number of boxes needed is minimized.
The two generic algorithm types implemented are Local-search and Greedy algorithms.
Local-search is the idea of 'walking' through the space of solutions - from one solution to a 'neighboring' one. The idea is to explore only the 'neighborhood' of a given solution instead of the entire search space.
Local-search is an umbrella term and includes Hill Climbing, Simulated Annealing, Taboo Search, and more.
When implementing a Local-search algorithm, we need to define:
- what is a 'neighborhood' (i.e. how do we find neighboring solutions)?
- which solution within a neighborhood do we move to?
These are problem-specific. The definitions implemented are:
- Geometry-based: neighbors are found by moving a single rectangle to a random feasible position in the same or in another box
- Rule-based: instead of finding neighbored solutions through geometric moves, we build a solution by placing rectangles from a permutation according to some rule and find neighbors by making small changes to that permutation. That rule is Next Fit placement (scan all possible positions in a box and choose the fist that fits, opening a new box if needed).
- Partial-overlaps: starts with everything crammed into a single box and gradually spreads rects out. A "cooling schedule" slowly tightens how much overlap is allowed, from 100% (any mess is fine) down to 0% (no overlaps at all). The OverlapPenaltyProblem penalizes any pair of rects whose overlap exceeds the current threshold, so as the threshold drops, the hill climber is forced to move rects apart, eventually opening new boxes.
The following variants are implemented:
- Steepest Ascent Hill-Climbing ("Best" strategy): Evaluates all neighbors and selects the best one.
- First Ascent Hill-Climbing ("First Improvement" strategy): Selects the first better neighbor encountered
- Stochastic Hill-Climbing ("Random improving" strategy): Randomly selects among better neighbors
These strategies, of course, rely on a way to compare the quality of solutions. In our case, a solution is assigned a
score by using
a problem-specific evaluate function. This can be as simple as the number of boxes used for the solution - which
aligns with the optimization goal of the problem. To achieve a better gradient for the optimization algorithms to
follow, we add a term to the score that describes the "wasted space" within each box. This is designed to penalize empty
space in fuller boxes more than the same empty space in more empty boxes. The result is a pressure towards moves that
don't immediately reduce the number of boxes needed but gets us there by packing boxes more fully.
The implementation of the generic Local-search (any neighbor selection strategy) is optimized by introducing a maximum number of plateau moves (moves that don't change the score). Plateau moves are taken to overcome small plateaus in the score landscape, which would otherwise prematurely stop the optimization.
Greedy is a term used to refer to types of algorithms that only ever choose the option that looks “most promising” at that moment. Greedy algorithms build a solution incrementally. More specifically, Greedy can also refer to a type of algorithm which we implement here: an algorithm that incrementally builds a solution
When implementing a Greedy algorithm, we need to define:
- in which order are the items processed? (implemented as
ItemOrdering) - how to process the item? In the case of our Rectangle Packing problem: which box to put the rectangle in, and where to place the rectangle within the box?
For the item order this project implements two variants:
- Rectangle area ordering: ordered by decreasing rectangle area
- Random ordering
- Squareness ordering: process the most square shapes first, and the most elongated rectangles last
Processing the item (the rectangle) is demonstrated using a strategy composed of two steps: selecting a box and placing the rectangle within that box.
Placing the rectangle can be done in various ways. This project implements two ways to select the box:
- best-fit box selection: chooses the box with the least remaining space after placing the rectangle in it
- first-fit box selection: chooses the first box the rectangle can be placed in to get a valid solution
For placing the rectangle within the selected box this project implements the following variant, but allows for more to be added:
- bottom-left placement: places a rectangle in the lowest and leftmost feasible position within the given box
- Use Java 25.
- Entry point to start UI:
com.optalgos.ui.Launcher - Use classpath of
optalgos-ui modulewith-cp optalgos-ui. - Optionally, add
--sun-misc-unsafe-memory-access=allowVM option to suppress a warning caused by a JavaFX bug ( see https://bugs.openjdk.org/browse/JDK-8346566).
In the UI, a problem instance is automatically generated at launch. Select your desired algorithm settings and click 'Solve' problem. You can now play or step through the steps taken by the algorithm.
You can change the algorithm settings to apply a different configuration on the same problem instance.
At any point,
you can generate a new problem instance: modify the problem parameters as desired, or leave them as is, and click
Generate New Problem. You will need to re-solve the new problem by again selecting your desired algorithm settings and
clicking Solve Prolbem.
To achieve a suitable, comparably low runtime for problems up to 1000 rectangles, some optimizations to the
implementation had to be made. Here's some problem areas that occurred and what helped:
Counting the number of used boxes: inevaluate()we were determining the number of boxes used for each generated
solution, which required iterating over all rect placements.
So instead we track the number of used boxes in the solution itself.
Feasibility check: the HillClimbing algorithm checks every neighbor for feasibility (all rects overlap-free &
within
box bounds). That was O(n²) for each generated solution.
So what we do instead is, when building a solution in a neighborhood, when the neighborhood can tell from the single
change that the generated solution is feasible, we mark this with a flag in the solution itself to skip the extra
check
in HillClimbing.
HashMap groupByBox -> array indexed by boxId: This lookup is used by the box selection strategies for the Greedy
algorithm. The problem: Box IDs are sequential integers 0..maxBoxId, so using a HashMap
leads to unnecessary overhead. Replacing it with aList<Placement>[]
array eliminates the object allocations once per placement during greedy rebuild..
Bottom-left placement scan — inline x-skip: Used in all neighborhoods and greedy. The inner position loop in
BottomLeftPlacementStrategypreviously
allocated a newPlacementobject at every candidate position just to test for overlap. For boxSize=10 that's up to
100 allocations perplaceInBoxcall. Replaced with an inline x-skip scan: pure arithmetic overlap check that skips
past occupants, allocating exactly one Placement when the valid position is found.
Delta evaluation for overlap penalty: The above counting-sort still ran the full O(pairs) walk once per evaluate,
and evaluate runs up to maxNeighbors (~1000) times per iteration. Since most neighbors differ by only one rect's
position, we compute the full pair walk once perneighbors()call to obtain the parent's total penalty and each
rect's individual contribution. Each generated neighbor then only computes its moved rect's contribution at the new
position — O(box size) instead of O(all pairs). The result is stamped on the neighbor solution;evaluate()reads it
and returns immediately. An identity cache on the neighborhood also catches HillClimbing's re-evaluation of the parent
solution afterneighbors()returns.
Building a solution in RuleBased neighborhood: solutions only change starting from the first rect that was changed in the permutation, all rects that came before it in the permutation end up in the same position. So we use partial rebuilds: calculate snapshots upfront, only apply the change of rectangles after the swap point.
Of course, being selective about the way we generate neighboring solutions and also limiting the number of neighbors generated per iteration are also ways that performance is optimized.