Dotted-board model – Optimization Online

A regular perspective on solving the irregular strip packing problem with the dotted-board model: a mosaic approach and a divide-and-conquer strategy

Published: 2026/10/10

Combinatorial Optimization, Integer Programming combinatorial optimization, computational experiments, Dotted-board model, integer linear programming, irregular strip packing

Since its introduction in 2013, the dotted-board model has been widely used by the cutting and packing research community to tackle irregular packing problems. However, despite its popularity, little research has aimed at improving its performance when solved via off-the-shelf integer programming solvers, beyond the known strategy of merging pairwise incompatibility constraints into clique constraints … Read more

Modeling Bloons Tower Defense as a temporal two-dimensional knapsack problem with irregular shapes and side constraints: integer programming-based approaches

Published: 2025/12/15, Updated: 2026/04/28

Maxence Delorme

Combinatorial Optimization, Integer Programming Dotted-board model, integer programming, Nesting problem, Tower defense, Two-dimensional knapsack problem

In Tower Defense (TD) games, the objective is to defend a specific point on the game map from mobile units by constructing towers with offensive capabilities. In this work, we focus on Bloons Tower Defense (Bloons TD), one of the earliest and most prominent TD games. We show that the problem of finding tower configurations … Read more