Minimizing the number of bins

[xavierXV3]

Hi,
Here is a naive implementation of a vector (2D) bin packing solver.

class Bin:
  ...

@planning_entity
@dataclass
class TimeFoldItem:
    item: ItemInterface
    bin: Annotated[Bin, PlanningVariable] = field(default=None)

@planning_solution
@dataclass
class TimeFoldSolution:
    items: Annotated[List[TimeFoldItem], PlanningEntityCollectionProperty]
    bins: Annotated[List[Bin], ProblemFactCollectionProperty, ValueRangeProvider]
    score: Annotated[HardSoftScore, PlanningScore] = field(default=None)

@constraint_provider
def define_constraints(constraint_factory: ConstraintFactory):
    return [
        bin_capacity_0(constraint_factory),
        bin_capacity_1(constraint_factory),
        assignment(constraint_factory),
        minimize_bins(constraint_factory)
    ]

def bin_capacity_0(factory: ConstraintFactory):
    return (
        factory.for_each(TimeFoldItem)
        .group_by(
            lambda item: item.bin,
            ConstraintCollectors.sum(lambda item: item.item.sizes[0]),
        )
        .filter(lambda bin, total_size: total_size > bin.capacities[0])
        .penalize(
            HardSoftScore.ONE_HARD,
            lambda bin, total_size: total_size - bin.capacities[0]
            )
        .as_constraint("BIN_CAPACITY_0")
    )

def bin_capacity_1(factory: ConstraintFactory):
    return (
        factory.for_each(TimeFoldItem)
        .group_by(
            lambda item: item.bin,
            ConstraintCollectors.sum(lambda item: item.item.sizes[1]),
        )
        .filter(lambda bin, total_size: total_size > bin.capacities[1])
        .penalize(
            HardSoftScore.ONE_HARD,
            lambda bin, total_size: total_size - bin.capacities[1]
            )
        .as_constraint("BIN_CAPACITY_1")
    )

def assignment(factory: ConstraintFactory):
    return (
        factory.for_each(TimeFoldItem)
        .filter(lambda item: item.bin is None)
        .penalize(
            HardSoftScore.ONE_HARD
        )
        .as_constraint("ITEM_ASSIGNED")
    )

def minimize_bins(factory: ConstraintFactory):
    return (
        factory.for_each(TimeFoldItem)
        .group_by(
            lambda item: item.bin
        ).penalize(
            HardSoftScore.ONE_SOFT
        )

The initial solution has one bin for each item (just to test).

solver_factory = SolverFactory.create(
      SolverConfig(
          solution_class=TimeFoldSolution,
          entity_class_list=[TimeFoldItem],
          score_director_factory_config=ScoreDirectorFactoryConfig(
              constraint_provider_function=define_constraints
          ),
          termination_config=TerminationConfig(
              spent_limit=Duration(seconds=time_limit)
          )
      )
)
initial_solution = TimeFoldSolution(items=items,bins=bins)
solver = solver_factory.build_solver()
solution = solver.solve(initial_solution)

The algorithm struggles to decrease the number of bins. I realized that the soft score doesn't provide much information about the progress toward a solution with one less bin.
How to model it properly with Timefold?

Kind regards

[xavierXV3]

Here is an example output :

2025-05-05 18:00:25,151 - timefold.solver - INFO - Solving started: time spent (899), best score (0hard/-223soft), environment mode (PHASE_ASSERT), move thread count (NONE), random (JDK with seed 0).
2025-05-05 18:00:25,151 - timefold.solver - INFO - Problem scale: entity count (223), variable count (223), approximate value count (223), approximate problem scale (4,698773 × 10^523).
2025-05-05 18:00:25,733 - timefold.solver - INFO - Construction Heuristic phase (0) ended: time spent (1482), best score (0hard/-223soft), move evaluation speed (0/sec), step total (0).
2025-05-05 18:05:25,120 - timefold.solver - INFO - Local Search phase (1) ended: time spent (300869), best score (0hard/-109soft), move evaluation speed (82/sec), step total (21901).
2025-05-05 18:05:25,128 - timefold.solver - INFO - Solving ended: time spent (300869), best score (0hard/-109soft), move evaluation speed (81/sec), phase total (2), environment mode (PHASE_ASSERT), move thread count (NONE).
Solving finished with score (0hard/-109soft).

First fit produces a solution with 26 bins.

[triceo]

Hello @xavierXV3, and welcome to the fold!

When you say "The algorithm struggles to decrease the number of bins." - what results would you prefer? I see in your log a decrease from 223 to 109, which is considerable. Although, not knowing your data set, you can probably see a better solution on your own, and are wondering how come the solver is not seeing it too.

Unfortunately, this is where the real problem comes in. Your move evaluation speed is 82, where we typically see numbers three orders of magnitude better. This means the solver barely explored any of the search space, and that also explains why it's not finding better solutions - it simply hasn't seen many solutions at all.

Why would it be so incredibly slow? Looking at your constraints, I don't think it's that. Which leaves me with another option - that you've run into some strange corner case where our Python wrapper around the Java solver just struggles. I don't have an answer for you why that would be at the moment, just that it is very likely on our side, not yours.

[xavierXV3]

Thanks for your response. I used VirtualBox and my company laptop which is not the fastest computer around. I will try tomorow on an EC2 instance. Kind regards

[xavierXV3]

Hello,
I just tryed on an EC2 instance and got a move evaluation speed of 84/sec.
Could it be related to the fact that I use a community edition ?
I saw that multi-threading is a feature of the enterprise edition.

[triceo]

Thanks for trying again!

While Enterprise Edition would have been faster, it wouldn't have helped much with this particular problem. It would have gotten you a speed bump on the order of magnitude of 10x, whereas you're struggling with an issue that's keeping you 1000x down.

The underlying issue is most likely on the boundary between Java and Python - as I said above, I expect this to be some pathological corner case, where our translation of Python to Java fails and it results in this abysmal performance. Nothing you can do about this now, I'm afraid - we'll have to look into it on the Python side, when we find the time.

[xavierXV3]

Thanks for your response.
I saw in the documentation evaluation speed starting at 1000/sec.
You speak about a 1000x factor, which would amount to nearly 80 000/sec.

We will try with Java.

[triceo]

For large datasets and large number of constraints, the move evaluation speed will naturally go down. In simple cases though, your speed should easily be in the five digits, and I have not yet seen anything in your use case that would make me think otherwise.

Seeing Java performance would certainly be interesting. If that is slow too, then we'll have to look for a bottleneck in your domain model. But as explained above, I would be really surprised if that were the case.

[xavierXV3]

I rewrote it with Java, it is much much faster indeed.

12:49:37.386 [main] INFO a.t.s.core.impl.solver.DefaultSolver - Solving started: time spent (65), best score (0hard/-258soft), environment mode (PHASE_ASSERT), move thread count (NONE), random (JDK with seed 0).
12:49:37.386 [main] INFO a.t.s.core.impl.solver.DefaultSolver - Solving started: time spent (65), best score (0hard/-258soft), environment mode (PHASE_ASSERT), move thread count (NONE), random (JDK with seed 0).
12:49:37.394 [main] INFO a.t.s.core.impl.solver.DefaultSolver - Problem scale: entity count (258), variable count (258), approximate value count (258), approximate problem scale (1,57719 × 10^622).
12:49:37.394 [main] INFO a.t.s.core.impl.solver.DefaultSolver - Problem scale: entity count (258), variable count (258), approximate value count (258), approximate problem scale (1,57719 × 10^622).
12:49:37.417 [main] INFO a.t.s.c.i.c.DefaultConstructionHeuristicPhase - Construction Heuristic phase (0) ended: time spent (96), best score (0hard/-258soft), move evaluation speed (0/sec), step total (0).
12:49:37.417 [main] INFO a.t.s.c.i.c.DefaultConstructionHeuristicPhase - Construction Heuristic phase (0) ended: time spent (96), best score (0hard/-258soft), move evaluation speed (0/sec), step total (0).
12:54:37.325 [main] INFO a.t.s.c.i.l.DefaultLocalSearchPhase - Local Search phase (1) ended: time spent (300004), best score (0hard/-109soft), move evaluation speed (512183/sec), step total (115817850).
12:54:37.325 [main] INFO a.t.s.c.i.l.DefaultLocalSearchPhase - Local Search phase (1) ended: time spent (300004), best score (0hard/-109soft), move evaluation speed (512183/sec), step total (115817850).
12:54:37.329 [main] INFO a.t.s.core.impl.solver.DefaultSolver - Solving ended: time spent (300005), best score (0hard/-109soft), move evaluation speed (511994/sec), phase total (2), environment mode (PHASE_ASSERT), move thread count (NONE).
12:54:37.329 [main] INFO a.t.s.core.impl.solver.DefaultSolver - Solving ended: time spent (300005), best score (0hard/-109soft), move evaluation speed (511994/sec), phase total (2), environment mode (PHASE_ASSERT), move thread count (NONE).
Initial number of bins used: 258
Solution score: 0hard/-109soft
Number of bins used: 109

But the solution at the end is not very good. A simple heuristic (first fit) obtains a solution with 34 bins.

[triceo]

Now that we know that performance is not an issue, we can focus on behavior of the model. If I were a betting man, I'd say you're spot on:

I realized that the soft score doesn't provide much information about the progress toward a solution with one less bin.

Maybe some softer score that shows how much space remains in the bins? That would be a number that would decrease gradually in small increments, and could help.

Also, you may want to increase the move diversity - enabling pillar moves, for example, could help. Seeing how much performance you have (500k/sec is great), you can afford to spend quite a lot of time in move selection without losses in solution quality.

[triceo]

@xavierXV3 Due to some UI mistake which I don't understand, I managed to overwrite your comment with my response to it, and can't restore it anymore. So I ended up deleting it, as it is less confusing. Apologies! My answer to your comment (which no longer exists) follow.

Additionally, it would be great if the Python implementation could be optimized for better performance.

The Python solver is generally slower than the Java solver on account of all the translation that's happening, but this is the first time we're seeing something so extreme. 1000x clearly means something's gone wrong somewhere - we'll look into it when time permits, thanks for reporting!

[xavierXV3]

We are also looking on our side if there is an issue in our code.

[xavierXV3]

Regarding the model, I added a soft constraint penalizing bins with low filling, and enabled pillar moves, and the quality of the solution is much much better. It comes closer to the one of simple state-of-the-art heuristics. I will make a benchmark next week.

[maDesmarescaux]

Hi,

It's possible that the use of NumPy in certain parts of the constraint logic may interfere with Timefold's internal optimizations. Specifically, relying on NumPy structures might prevent some performance enhancements, such as Java-level inlining or native constraint stream acceleration.

I tried using more "native" Python structures (like plain lists), and it improved performance, allowing Timefold to better leverage its execution engine.

[triceo]

I filed a tracking issue:
#1596

Thank you for bringing this to our attention!