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.

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

1 Answer 1

Reset to default
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

Improve this answer
$\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$
    – sdgaw erzswer
    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$
    – falsePockets
    Sep 3, 2021 at 7:05

Your Answer

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

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