3
$\begingroup$

Let me describe my problem: I've got around 1500 items, all of them described by 15 numeric (rational numbers, positive and negative) attributes.

As an minimalized example:

Item A: - value I: 34 - value II: 12335 - value III: -10 - value IV: 0 .... Item B: - value I: 500 - value II: -2332 - value III: 0 - value IV: 9 ...

No i have to combine them and find the best combination. There is space for about 70 items and each item can be used n times.

The performance of each combination can be determinated by a simple math formular using 3 of the attributes, while the other attributes has to match min or max requirements to determinate if a combination is valid or not.

because some items have good values for a single attribute, but negative for other attributes, other items have to be taken to compensate these negative aspects

Now I'm looking for an approach/algorithm/tooling to find the best combination or at least get near to it.

My approaches were to (in pseudocode)

//approach A while(true) var best = generateRandomCombination() var challenger = generateRandomCombination() best = betterPerformanceIndicator(best, challenger)

at some point i have to stop it and use the result. tried it, let it run for an hour and loggt every single improvement. horrific performance, to much randomness means repetition. and of course it does not came near to a result i'd produce on my own. 

//approach B var best = generateRandomCombination(); while(true) var challenger = replaceSingleItemWithRandomOne(best) while (!challenger.isBetter(best) && untestedItemsLeft()){ challenger = replaceWithOtherItem(best); } best = betterPerformanceIndicator(best, challenger)

This approach is some kind of approximation, but i think because of the needed compensations it won't be very efficient to change only one item.

So i see two possible ways to improve: - perhaps i should give the items some kind of weighting - replace more than on item

Do you have any suggestions to improve my approaches or replace it with better ones? Is this some kind of data-mining problem? What should i learn to deal with it?

(if my question is wrong in here, i'm sorry. would be nice if you would redirect me to the correct stack exchange section)

added information due to comments:

  • in the beginning i have to fix the container properties, to determinate if there is space for 70, 71 or an other amout of items. And to to determinate the multiplicator of each attribute. As an example: the containers multiplicator of "value I" would be 1,1 - adding Item A and Item B wour result in (34 + 500) * 1,1 = 587,4.
  • So you see, adding the items is simple math (addition and multiplication) Concerning speed, my first approaches were written in java using Lists, but i have not tracked the speed of these single operations.
  • the order of the item does not effect the outcome, so it's about building an unordered set, just like Neil asked.

  • The formula to compute the total value is:

    square root of ( (sum of all valueI) multiplied by (sum of all valueII and valueIII) )

  • min and max requiremants are just natural numbers, that the sum of all valueN should (not) reach at least
Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ I'm not sure if you will get the best answer here. You have a combinatorial optimisation problem, there's no tag for that on the site, although some search algorithms or ml approaches might work, depending on the nature of the data. How quickly can your code assess a completed set of 70 items, and how quickly can it assess an item swap? Does the order of items make any difference, or is the problem purely about building an unordered set? $\endgroup$ Commented Jul 24, 2017 at 15:40
  • $\begingroup$ thanks for your questions, i've tried to answer them at the end of my question $\endgroup$ Commented Jul 24, 2017 at 19:58
  • 1
    $\begingroup$ What is the nature of the formula for computing the total value of a combination, as a function of the attributes of the elements of the combination? What is the nature of the "min or max requirements" for something to count as a valid combination? This question probably isn't answerable without knowing something about those issues. $\endgroup$ Commented Jul 24, 2017 at 22:47
  • $\begingroup$ i've added a description of the formula for computing the total value and a small info about the min/max requirements. i hope it matches what you mean by "nature of the formula" $\endgroup$ Commented Jul 25, 2017 at 16:18
  • $\begingroup$ This sounds more of a computer science problem than machine learning. Do an exhaustive / grid search. how many possible combinations? $\endgroup$ Commented Aug 23, 2017 at 5:38

1 Answer 1

Reset to default
1
$\begingroup$

That sounds like a knapsack problem. Knapsack problem can be solved a variety of ways. Given your constraints, an approximate solution, like first-fit decreasing (FFD), would probably be acceptable.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.