Ways to implement a decision making process involving complex rules
It sounds to me like the techniques here are not a matter of science (e.g., clever algorithms) so much as engineering (e.g., program structuring).

The approach I would suggest is to have a list of validators.  Each validator is a function or object that, when passed a shopping cart, checks whether the cart satisfies a particular criterion.  You have one validator per criterion in your business rules.  Then, to check whether a shopping cart is valid, you can simply iterate over all the registered validator.

This lets you structure the program logic in a cleaner way.  Each criterion is separated out into its own function or subclass.  Thus, while you still might have hundreds of lines of code in general, this way there is some structure, and if you're lucky, most or all validators can be written in a fairly concise way, as each one deals with only a single concern/criterion.