1 Matrix into 4 Matrices and Optimizing Sum of Columns

46 Views Asked by At

I have one $n \times m$ matrix, where $n$ is the number of customers and $m$ is the number of bread varieties I can sell. Each customer can subscribe for a full month to any number of each variety, and I deliver the bread once per week. Therefore, a customer will receive at most 4 deliveries each month.

Also, assume a customer eats 1 loaf of bread per day. Therefore, if the customer orders $\le 7$ loaves, they receive 1 delivery in the month. If they order between 8-14, they receive 2 deliveries in the month. And so on. I deliver only integer quantities of each bread variant, so 1 or 2 or 3 loaves, but not 1/3 loaf.

How can I take my single $n \times m$ matrix to create four $n \times m$ matrices (called A, B, C, and D) -- 1 for each weekly delivery -- such that the varieties I deliver each week are concentrated for that week? Also, A+B+C+D should equal the initial $n \times m$ matrix. More specifically, if I have a whole wheat loaf, I want to make sure the highest concentration of whole wheat is delivered in one given week. At the core of this problem, I want to make sure I'm optimizing my weekly delivery of each bread variety.

Is this even programmatically possible?

1

There are 1 best solutions below

2
On

This seems to be a scheduling problem over natural numbers. The monthly orders of $n$ customers, spread along $m$ varieties, have to be scheduled over $4$ delivery days.

For a customer $i$ in a first step, the number of deliveries $d_i$ is determined, then one tries to come up with a schedule where the deliveries might have roughly the same size (number of breads within the delivery), staying close to an arithmetic mean.

For the bread varieties over all customers, one prefers larger deviations from the mean.

A scoring function which would score different schedulings is already a bit vague, and there still seems to be much freedom in the problem.

Small instances might be solved by brute-force exhaustive search, but I guess in general some optimization heuristic has to be applied.