Efficient salami placement

Question

Given $S$ and a set of $n$ slices of salami ${C_1, C_2, ..., C_n}$, what is the most efficient way to place the slices of salami on $S$ such that the total area of $S$ covered by the slices of salami is maximized?

Efforts in solving the problem:

One possible approach to solving this problem is to use optimization techniques to maximize the total area covered by the slices of salami on the slice of sandwich. One possible optimization problem formulation is:

$$\max_{x_1, x_2, ..., x_n} \sum_{i=1}^{n} x_i A_i$$ subject to $$\sum_{i=1}^{n} x_i = 1$$ where $x_i$ is a binary variable indicating whether slice $C_i$ is placed on the sandwich, $A_i$ is the area of slice $C_i$, and the constraint ensures that exactly one slice of salami is placed on the sandwich.

This is a MILP problem and can be solved using various optimization solvers. However, this formulation assumes that the slices of salami are non-overlapping, which may not be the case in practice.

What would be a more realistic and practical optimization problem formulation for the placement of sliced salami on a slice of sandwich, taking into account the possibility of overlapping slices? How can we efficiently solve this problem?

place the slices back to back, then cut the slices to fill in the gaps — David P, Mar 21 '23 at 11:12
@DavidP We would still like to explore a more general and rigorous optimization problem formulation that takes into account overlapping slices :) — rumathe, Mar 21 '23 at 11:16
@JeanMarie yep, also I think we need a solution that minimizes amount of disks required to fill in the gaps, I think slicing disk should be constraint only by one straight cut which sounds more realistic — rumathe, Mar 21 '23 at 12:31
@JeanMarie Yes, but let's put some kind of limit on, for example, the area of the resulting slice — rumathe, Mar 21 '23 at 13:21
Constraining to exactly one slice makes the question very easy, doesn't it? — aschepler, Mar 21 '23 at 21:21

score 1 · Answer 1 · answered Mar 21 '23 at 21:15

$$\max_{x_{ij}, p_i, q_i} \sum_{i=1}^{n} \sum_{j=1}^{m} x_{ij} A_{ij}$$ subject to $$\sum_{j=1}^{m} x_{ij} \leq 1 \quad \forall i$$ $$\sum_{i=1}^{n} \sum_{j=1}^{m} x_{ij} A_{ij} \leq A_S$$ $$A_{ij} \leq A_{C_i} \cdot x_{ij} \quad \forall i, j$$ $$0 \leq p_i \leq 1 \quad \forall i$$ $$0 \leq q_i \leq 1 \quad \forall i$$

where:

$x_{ij}$ is a binary variable indicating whether slice $C_i$ is placed on the sandwich with configuration $j$,
$p_i$ and $q_i$ represent the proportion of the maximum single straight cut allowed on slice $C_i$,
$A_{ij}$ is the area of slice $C_i$ in configuration $j$,
$A_S$ is the area of the slice of sandwich $S$,
$n$ is the number of slices of salami, and
$m$ is the number of possible configurations for each slice.

Can be solved efficiently using Branch-and-Bound method or the Outer Approximation algorithm.

There are a finite number of ways to place a slice of salami? — aschepler, Mar 21 '23 at 21:20
@aschepler Yes, assuming that we are considering a finite number of possible configurations for each slice — rumathe, Mar 21 '23 at 21:25

Efficient salami placement

1 Answers1