0
$\begingroup$

I am trying to understand which combinatorial problem best fits the one I have. I am mostly asking from the perspective of being pointed towards relevant literature. I will explain the problem with an example.

Consider the set $S = \lbrace{a^1, a^2, a^3, b^1, b^2, b^3, b^4, c^1, d^1, d^2, d^3, d^4 \rbrace}$. So note that $S$ is like a multi-set but elements of the same type can be distinguished. We are given a tuple of sets $U$ which specifies which elements of $S$ are needed and their quantity. Consider this example where $U = (\lbrace{2a, 1b, 1c \rbrace}, \lbrace{1a, 3d\rbrace}, \lbrace{2b, 3d\rbrace} )$, so the first order (set) of $U$ (i.e., $\lbrace{ 2a, 1b, 1c \rbrace}$) is asking for 2 elements of $a$, 1 element of $b$ and 1 element of $c$ respectively. We can get those 2 elements of $a$ by selecting any 2 from ${a^1, a^2, a^3, a^4}$, likewise we can choose anyone one from $b^1, b^2, b^3, b^4$ for $b$, and similarly for $c$. For example we may choose to satisfy the first order $\lbrace{2a, 1b, 1c \rbrace}$ by assigning it ${a^3, a^4, b^2, c^1}$, however by doing so these elements of $S$ are no longer available for satisfying subsequent orders of $U$. There are costs associated with how we choose to satisfy each order. For example, it can cost us differently had we chosen to satisfy $\lbrace{2a, 1b, 1c \rbrace}$ with say ${a^1, a^2, b^1, c^1}$ instead.

I know that I have not described much about the cost function, but just given the constraint set I am wondering which well-studied combinatorial problem is reminiscent or equivalent to mine. I am ultimately interested in either online algorithms or heuristics for satisfying the orders in $U$ with low cost. I am interested to explore literature related to this problem (if available) with different cost functions and under different assumptions (such as those typical in online settings) so please feel free to suggest if you think a certain problem, paper or application is related to the problem I described.

I am NOT interested in a Mixed Integer programming formulation for this problem.

$\endgroup$
2
  • $\begingroup$ Is the supply sufficient to satisfy all needs ? $\endgroup$
    – user16034
    Commented Sep 4, 2023 at 20:21
  • $\begingroup$ If nothing is known about the cost function, you can't spare an exhaustive search. $\endgroup$
    – user16034
    Commented Sep 4, 2023 at 20:22

1 Answer 1

0
$\begingroup$

This sounds like it can be framed as an instance of the assignment problem, assuming the costs are computed as a linear function of a cost for assigning each individual item to a particular order.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.