1
$\begingroup$

I'm trying to solve an optimization problem which can be described as follows.

  • There are four sets objects. For simplicity, let's call them :
    1. Apples
    2. Oranges
    3. Pears
    4. Lemons
  • The sets can contain unequal numbers of their respective objects
  • These objects must be organized into groups containing exactly one of each object
  • Each possible group can be evaluated by some merit function (ie: function of the difference between the masses of the constituent objects of the group, say)
  • The maximum number of groups with a merit function below some threshold must be formed with the objects in the input sets.
  • In the above set of groups, no object can be duplicated - it must belong uniquely to one group.

My question is not necessarily how to solve this problem - this is no doubt an extremely broad question. What I would like to know is whether or not this problem has, or is of a class of problem, with some formal name.

Primarily, I'm looking for search terms to help research similar problems (and the types of solutions that are known for it).

$\endgroup$
  • $\begingroup$ Seems like a complicated version of the knapsack problem. $\endgroup$ – André Souza Lemos May 11 '15 at 21:07
  • $\begingroup$ @AndréSouzaLemos That actually got me started down the right road, I think. This is perhaps closer to the Stable Marriage problem, albeit with a marriage of four genders rather than two. en.wikipedia.org/wiki/Stable_marriage_problem#Similar_problems $\endgroup$ – J... May 11 '15 at 21:25
  • 1
    $\begingroup$ The thing is, you are selecting a subset of the total number of possible matches, according to an decision function. That's what brings it closer to knapsack. Appearances deceive. $\endgroup$ – André Souza Lemos May 11 '15 at 21:29
  • $\begingroup$ @AndréSouzaLemos Yes, but with many knapsacks...the number of which is also a parameter to be optimized. I'll keep reading, this is a good start, thanks! $\endgroup$ – J... May 11 '15 at 21:41
3
$\begingroup$

It's called four-dimensional matching and it's NP-complete.

$\endgroup$
  • $\begingroup$ I was pretty certain from the formulation that it must be NP-complete. At best I'm hoping to find some workable approximations. I'll look this up! $\endgroup$ – J... May 11 '15 at 22:12
  • $\begingroup$ You might find more information on three-dimensional matching, which might still be helpful. $\endgroup$ – David Richerby May 11 '15 at 22:17
  • $\begingroup$ Indeed, reading up on it now... $\endgroup$ – J... May 11 '15 at 22:17
  • $\begingroup$ It seems that n-Dim matching assumes T (set of n-ples) is given as input. In my case this is not so - all I have are the initial disjoint sets. I suppose the problem would reduce to first a knapsack-type problem for the generation of the initial set of T, followed by a weighted form of maximum n-Dim matching to reduce T. $\endgroup$ – J... May 12 '15 at 9:10
  • $\begingroup$ In your case, $T$ is just the set $\mathrm{Apples}\times\mathrm{Oranges}\times\mathrm{Pears}\times\mathrm{Lemons}$. Worst case, you could generate this list; I don't know what algorithms for 4DM look like but it's possible that you could do something smarter than that and use the "implicit" representation for the set of tuples and their weights throughout your algorithm. $\endgroup$ – David Richerby May 12 '15 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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