Difference between NChooseKConstraint and LinearConstraint on Binary Variables.

[Aschwins]

Really glad I came across this repo, because I'm learning a lot of new things! I have a question and would like to discuss some ideas.

I have a product development problem which we solve using Bayesian Optimization, but we have a tricky constraint. We have a bunch of ingredients as explanatory variables which we can use to create products. These products have properties which we predict and want to optimize. The tricky constraint is that we can only use 5 ingredients of a set of around 30 total, this really sounds like the NChooseKConstraint which I found a discussion about here by @jduerholt , which led me to this repo.

Really interesting idea and I think exactly what I'm looking for. I was trying to solve this by introducing binary decision variables $b_0, b_i,...$ where $b_i$ is 1 if $x_i > 0$ and 0 otherwise. Then add a linear constraint $\sum(b_i) < 6$. Have you thought about this as well? What would be the difference? Any problems I'm overlooking with ipopt maybe?

Would love to hear your thoughts!

Best,
Aschwin

[Osburg]

Hi @Aschwins , if you want to use IPOPT this could be problematic, because IPOPT only supports continuous variables. So I guess in the most general case any constraint relying on binary decision variables is not so easy to realize. I think there have been approaches to overcome this limitation (e.g. #243 ), but @dlinzner-bcs probably knows more about that. I think pyomo offers a solver for MINLP https://pyomo.readthedocs.io/en/stable/contributed_packages/mindtpy.html, so maybe this is an option for you if you want to realize the NChooseK constraint via binary variables.

Cheers,
Aaron :)

[jduerholt]

Hi @Aschwins,

I fully agree to @Osburg, we use IPOPT for the DoEStrategy in BoFire. For bayesian optimization, SLSQP or BFGS are used for acqusition function optimization, with these gradient based optimizers, you will have the same problems as with IPOPT and binary decision variables. Furthermore, it would be a bit more complicated to setup as the binary helper variables should only enter optimizer but not the surrogate model (GP).

Have you tried our implementation of the NChooseKs based on the nonlinear inequality constraints within BO in BoFire?

Best,

Johannes

[jduerholt]

You can also have a look at this tutorial: https://github.com/experimental-design/bofire/blob/main/tutorials/benchmarks/005-Hartmann_with_nchoosek.ipynb

[Aschwins]

Hiya @jduerholt , @Osburg ,

Thanks a lot for the replies and good suggestions, I'm new to all these concepts so still exploring all the methods and the api.

I realise now my initial question was a bit incorrect and I'm more looking for a Sampler which takes into account NChooseK constraints. I checked out the PolytopeSampler, but it wasn't able to produce any candidates when I introduced overlapping NChooseK constraints.

I narrowed it down to the product that's being calculated here. I really like how you create the combinations for each constraint, but for me calculating the product of these combinations is actually incorrect. Let me explain.

I have NChooseK constraints which overlap in features. So I can only choose 5 ingredients from the total 15 features ($x_0,...x_{14}$). But I also have to choose one ingredient from group A ($x_0, x_1, x_2$) and one ingredient from group B ($x_3, x_4, x_5, ...$). But this is probably not how NChooseK is intended at the moment. I think it also means I could calculate all the combinations of the first ("total") constraint and then slice away all the combinations which don't abide to the other constraints. Its actually more of set intersection of all the NChooseK constraints.

Have you encountered something like this before?

I'm trying to extend now by building my own SamplerStrategy called GridSampler, which just creates a grid of all possible combinations and spreads them out a bit between the bounds. Problem is the SamplerStrategy runs the Domain.get_nchoosek_combinations method when .ask() is called. So not sure how to continue here.

Would love to hear you ideas/suggestions!

Best,
Aschwin

[Osburg]

If I got you right you could do the following:

Add 1 NChooseKConstraint on all 15 features with max_count=5
Add the LinearInequalityConstraint x_1 + x_2 + x_3 >= c > 0 to ensure at least one feature from the first group is nonzero
Add the LinearInequalityConstraint x_3 + ... + x_15 >= c > 0 to ensure at least one feature from the second group is nonzero

This roughly follows the procedure described in #145 in case you are interested in more details, I hope this helps.
Maybe also have a look into the open issue #314 .

Cheers
Aaron :)

[Aschwins]

Ha Aaron,

Wauw, touché, that also works, good catch! We also have a maximum on the first group, which is not enforced this way, but I don't really care about that one to be honest. Thanks a lot, this is extremely helpful, I will read up on the issues you mentioned, looks interesting for our use case as well.

Found some minor improvements which could be made to the get_n_choosek_combinations method, since the drop duplicates code seems to be inefficient. (see attached image for 15 choose 5 = 174407 combinations) There is already a "TODO: tidy this up", so this is already on the radar I think, but I could not find a PR open or anything.

I would propose the following to get rid of the duplicate combinations. I can maybe help clean up this method if you want.

used_features_tuples = [tuple(v) for v in used_features_list_sorted]

# option 1 - use set(): Ends up scrambling the values
used_features_list_no_dup = set(used_features_tuples)

# option 2 - use dict(): Does not scramble
used_features_list_no_dup = list(dict.fromkeys(used_features_tuples))

used_features_list_no_dup = [list(v) for v in used_features_list_no_dup]

Thanks,
Aschwin

[jduerholt]

Hi @Aschwins,

very nice that you could find a way to solve your problem.

Regarding the get_n_choosek_combinations method, this is indeed very old code which stems from the ancestors of BoFire, and it definitely need some refactoring and improvement, for this reason, I marked it already a long time ago with the TODO but did not find the time to do so. For this reason, you did not find any PR. So if you have already some ideas for improvement, we are happy to receive a pull request ;)

Best,

Johannes