1
$\begingroup$

My goal is to find the best combination, or good approximation, of weighted elements with different constraints / relations, for example:

  • B can only be there after A
  • B have to be there after A
  • B have a different weight if present after A
  • B have a different weight if present in the N next elements after A
  • B can only be there every N elements
  • B have a weight but does not cost an element
  • etc...

An elements can have more than one constraint at the same time.

The numbers of different elements available is 10-15, and the best combination should give a list of 60 elements, repeating this cycle of 60 elements should also follow the rules, like "A can only be done every N elements".

Following these rules, what would be the best way to find the best combination of elements?

I thought about Genetic algorithm, but during the crossover/mutation, we will have to verify if the rules are respected - 'ABAC' and 'ACAB' could be legal, but not necessarily the crossover 'ACAC'. Same for bruteforce, where going through 'AAAA', 'AAAB', etc will mostly give illegal combinations.

Maybe generating a graph out of it could help, but it seems to big and complicated to generate.

$\endgroup$
4
  • $\begingroup$ Have you looked at integer linear programming? I suggest you spend some time studying it, and try applying it -- looks like a good candidate for your situation. $\endgroup$
    – D.W.
    Jan 7, 2016 at 5:00
  • $\begingroup$ i dont know if this would help you (i can expand it as an answer if needed). i would take two approaches, 1) a grammar/template approach where the contraints are modeled by a grammar and then produce the string/combination based on actual values (this would produce exact and/or approximate combinations). 2) use a backtrack search procedure $\endgroup$
    – Nikos M.
    Jan 8, 2016 at 11:05
  • $\begingroup$ thanks D.W., I start reading about it, I'll continue this way $\endgroup$
    – Raphaël
    Jan 8, 2016 at 23:53
  • $\begingroup$ Nikos M., if I get correctly, in the first approach, the goal would be to generate every combinations respecting the rules of this grammar and pick the best one? - for the method 2), I'm not sure to see the interest of the backtracking here, is it in the same purpose, to generate every possible combinations then compare them? in both case, won't it be really slow, computation wise? it might depends of the contraints set, but say there is no constraints at all, it would be something like 15^60 possible combinations with 15 unique actions for example? $\endgroup$
    – Raphaël
    Jan 8, 2016 at 23:57

0

Your Answer

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

Browse other questions tagged or ask your own question.