What type of optimization problem is this? Ride sharing?

Question

I am given source containers $s_1,s_2, \dots, s_n$, products $p_1, p_2, \dots, p_m$ and an assignment of which container needs to be used to make a certain product, which I represent as follows

\begin{array} .&p_1&p_2&p_3&p_4&p_5\\ s_1&1&0&0&0&1\\ s_2&1&0&0&0&1\\ s_3&0&1&0&0&0\\ s_4&0&1&0&1&0\\ s_5&1&0&1&1&1\\ s_6&1&0&1&0&1\\ &&&\dots\\ \end{array}

where

• $1$ indicates it should be made.

• $0$ indicates it should not be made.

A source is not used up when making a product. The rules are:

• Sources that make the same products can be use in a single process to create the products.

• Only integer multiples of $k$, for sake of this example let's say $2$, sources can be used in the production process at the same time.

So in this example case, we could produce $p_1$ and $p_5$ in a single step for $s_1,s_2,s_5,s_6$ and then produce $p_3$ for $s_5,s_6$ in another or alternatively produce $p_1$ and $p_5$ in a single step for $s_1,s_2$ and then $p_1,p_3,p_5$ for $s_5,s_6$.

The goal is to have a low number of production steps. In a typical case,

• $k$ is $96$ or $384$ (not necessarily the same for every product).
• $n$ is around $1000$.
• $m$ is around $10$.

My questions are:

1. What type of problem is this? Can it maybe be modeled as a ride sharing problem? Some kind of matching problem? Bin packing?

2. What are sources to get started on this type of problem? I have done some discrete optimization (LP, genetic algorithms)

3. A heuristic approach that gives a local optimum would be fine.

4. Runtime constraints: shouldn't take longer than 5 minutes, absolute maximum 1 hour on a high end 2018 laptop (4 cores)

Answer 1

I assume that you need to produce multiple units of the various products (with specified demands). You might be able to get a good (but not necessarily optimal) solution by mimicking a one-dimensional cutting stock problem. In your case, your master problem would have a demand constraint for each product and a variable for each "pattern". (Each of your examples above, e.g. "produce $p_1$ and $p_5$ in a single step for $s_1$, $s_2$", would be a pattern.) Each pattern would contribute one per use to the objective function (number of production steps, to be minimized).

In addition to the master problem, you would need a subproblem to generate patterns that met the "multiple of $k$" criterion. The classic Gilmore-Gomory algorithm for the 1-d cutting stock problem used an LP to generate patterns, but I think your subproblem would need to be an integer program, which could make the one hour limit dicey (and the five minute target very dicey). I suppose you could try a heuristic (such as a genetic algorithm) for pattern generation, with a tight time limit, and just live with the possibility that it might miss some good patterns and lead you to terminate prematurely.