3
$\begingroup$

I've been recently working with a combinatorial optimization problem defined as follows. Given two sets of items, A and B, select the best combination of these items given a scoring function $f(A,B) \rightarrow \mathbb{R}$. The goal is to maximize the output.

As I am new to this field, my initial impression was, to try and code up a stochastic optimizer, such as for example genetic algorithm to solve this. My question is, are there any libraries apart from $\textit{Deap}$, which offer such functionality.

Thank you.

$\endgroup$
1
  • $\begingroup$ I face the exact problem. Did you find a solution? $\endgroup$
    – lenhhoxung
    Dec 23, 2021 at 10:12

1 Answer 1

1
$\begingroup$

The problem you are trying to solve is a variant of the two-way partitioning problem (pg. 234/730 in the pdf http://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf) which is known to be NP hard.

What this means in layman terms is that if the size of A and B is large, the problem can basically not be solved exactly. At best, one can hope to get algorithms which say statements of the form "We are off by a factor of at most k".

In these cases, the details become important. I would recommend you not code up such algorithms yourself, because they will likely be very inefficient (and maybe even way off!).

The library is not the issue here; the functional form of $f$ can dramatically change the approach

$\endgroup$
3
  • $\begingroup$ Whether it is NP hard depends on the nature of f. For example if f is nonzero for exactly one partition, then the problem is trivial. $\endgroup$
    – Zach Boyd
    May 20, 2019 at 19:14
  • $\begingroup$ So, not coding it myself would imply I can use a libraray of some form? Which one has support for this? $\endgroup$ May 29, 2019 at 5:57
  • $\begingroup$ I'm trying to solve this problem for a small input. I don't care if it's NP hard. Is there a library which is easier to use than coding myself? $\endgroup$ Sep 3, 2021 at 7:05

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.