We consider the problem of laying out several objects in an equal number of pre-defined positions. Objects are allowed finitely many orientations, can overlap each other, and must be arranged contiguously. We are particularly interested in the case when the evaluation of the dimensions of the objects requires computational or physical effort. We develop a notion of an arrangement of objects that achieves these requirements. Then, we provide two optimization models that further determine particular notions of the arrangement. The first optimization model is an exact formulation, however it requires an exponentially many inputs. In the second model, we employ classical Boole-Bonferroni inequalities to approximate the lengths of objects. This model requires only quadratically many inputs. We explore the connection of our problem to other combinatoric problems, such as the traveling salesman problem and the bin-packing problem. Finally, we describe how our model generalizes a mathematical puzzle that was recently proposed in the literature.
Citation
under review
Article
View Boole-Bonferroni Inequalities to Approximately Determine Optimal Arrangements