The Problem

You're hosting a party and want to maximize the number of different cocktails you can make within your budget. Each cocktail requires specific ingredients, and ingredients can be shared across cocktails. This sounds simple, but it's actually a computationally hard problem.

The approach of "buy the cheapest cocktail first, then the next cheapest" doesn't work because ingredient sharing creates dependencies. A slightly more expensive ingredient might unlock three additional cocktails, making it a better choice than a cheaper one that only enables one.

Formal Problem Definition

This optimization problem is a variant of the Budgeted Maximum Coverage Problem with dependency constraints. It combines elements of the 0/1 Knapsack Problem with Set Cover.

Given:

A set of ingredients \(I = \{i_1, i_2, \ldots, i_n\}\) with costs \(c(i)\)
A set of cocktails \(C = \{c_1, c_2, \ldots, c_m\}\)
A mapping function \(R(c) \rightarrow \{i\}\) returning required ingredients for cocktail \(c\)
A budget constraint \(B\)

Find:

A subset of ingredients \(I' \subseteq I\) to purchase
A subset of cocktails \(C' \subseteq C\) that can be made

Such that:

Total cost does not exceed budget: \(\sum_{i \in I'} c(i) \leq B\)
All required ingredients are purchased: For each \(c \in C'\), \(R(c) \subseteq I'\)
The number of makeable cocktails is maximized: \(\max |C'|\)

Computational Complexity

This problem is NP-hard because it generalizes the 0/1 Knapsack Problem (known to be NP-complete). The dependency constraints make it at least as hard as Knapsack. The decision version ("Can we make at least \(k\) cocktails with budget \(B\)?") is in NP.

Despite being NP-hard, modern constraint programming solvers can efficiently solve instances of this size (~30 cocktails, ~40 ingredients) using constraint propagation, branch and bound, conflict-driven clause learning, and linear programming relaxations.

Implementation with CP-SAT

We use Google's OR-Tools CP-SAT solver [2]. The implementation is surprisingly concise. First, we define binary decision variables:

# Boolean variable for each ingredient (1 = buy, 0 = don't buy)
ingredient_vars[ing] = model.NewBoolVar(f"buy_{ing}")

# Boolean variable for each cocktail 
# (1 = can make, 0 = cannot make)
cocktail_vars[cocktail] = model.NewBoolVar(f"make_{cocktail}")

Dependency Constraints

A cocktail can only be made if all its required ingredients are purchased. This can be expressed as an inequality constraint:

for cocktail in cocktails:
    required = get_required_ingredients(cocktail)
    for ingredient in required:
        model.Add(
            cocktail_vars[cocktail] <= ingredient_vars[ingredient]
        )

The constraint cocktail <= ingredient ensures:

If cocktail = 1, then ingredient must be 1
If ingredient = 0, then cocktail must be 0

Budget Constraint

The total cost of purchased ingredients must not exceed the budget:

total_cost = sum(
    ingredient_vars[ing] * cost[ing]
    for ing in all_ingredients
)
model.Add(total_cost <= budget)

Objective Function

We simply maximize the number of cocktails:

model.Maximize(sum(cocktail_vars.values()))

The Pareto Frontier

Rather than solving for a single budget, we can sweep through all possible budgets and find the threshold points where the number of makeable cocktails increases. This creates a Pareto frontier showing the optimal tradeoff between budget and cocktail variety.

results = []
prev_count = 0
for budget in range(0, 350):
    result = optimize(budget)
    if result.cocktail_count > prev_count:
        results.append(result)
        prev_count = result.cocktail_count

This precomputation allows the interactive demo above to instantly look up the optimal solution for any budget without re-running the solver.

Click to expand the complete optimization code

from ortools.sat.python import cp_model

def optimize_cocktail_selection(budget: float,
                                 cocktail_data: dict,
                                 ingredient_data: dict):
    """
    Optimize cocktail ingredient selection to maximize the number
    of different cocktails that can be made within a fixed budget.
    """
    model = cp_model.CpModel()

    # Get all unique ingredients
    all_ingredients = list(ingredient_data.keys())

    # Create binary variables for each ingredient (buy or not)
    ingredient_vars = {}
    for ingredient in all_ingredients:
        ingredient_vars[ingredient] = model.NewBoolVar(f'buy_{ingredient}')

    # Create binary variables for each cocktail (can make or not)
    cocktail_vars = {}
    for cocktail_name in cocktail_data.keys():
        cocktail_vars[cocktail_name] = model.NewBoolVar(f'make_{cocktail_name}')

    # Constraint: A cocktail can only be made if ALL its
    # required ingredients are purchased
    for cocktail_name, ingredients_list in cocktail_data.items():
        required = [item['ingredient'] for item in ingredients_list]
        for ingredient in required:
            model.Add(cocktail_vars[cocktail_name] <= ingredient_vars[ingredient])

    # Constraint: Total cost of purchased ingredients <= budget
    ingredient_costs = {}
    for ingredient, options in ingredient_data.items():
        # Convert to cents to avoid floating point issues in CP-SAT
        ingredient_costs[ingredient] = int(options[0]['cost'] * 100)

    total_cost = sum(
        ingredient_vars[ingredient] * ingredient_costs[ingredient]
        for ingredient in all_ingredients
    )
    model.Add(total_cost <= int(budget * 100))

    # Objective: Maximize the number of cocktails that can be made
    model.Maximize(sum(cocktail_vars.values()))

    # Solve the model
    solver = cp_model.CpSolver()
    status = solver.Solve(model)

    # Collect results
    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        cocktails_made = [
            name for name, var in cocktail_vars.items()
            if solver.Value(var)
        ]
        ingredients_to_buy = [
            ing for ing, var in ingredient_vars.items()
            if solver.Value(var)
        ]
        return {
            'cocktails': sorted(cocktails_made),
            'ingredients': ingredients_to_buy,
            'total_cost': sum(
                ingredient_data[ing][0]['cost']
                for ing in ingredients_to_buy
            )
        }
    return None


# Generate Pareto frontier of solutions
def generate_all_solutions(max_budget=350):
    results = []
    prev_count = 0
    for budget in range(max_budget):
        result = optimize_cocktail_selection(budget, cocktails, ingredients)
        if result and len(result['cocktails']) > prev_count:
            results.append(result)
            prev_count = len(result['cocktails'])
    return results