Densest k-Subhypergraph formulation of the cocktail ingredients problem

dksh.py

import csv
import time

import pulp


def solve(cocktails, ingredients, K):
    """The cocktail ingredient problem is an instance of the Densest k-Subhypergraph problem,
    https://arxiv.org/abs/1605.04284"""

    cocktail_decisions = {
        name: pulp.LpVariable(f"cocktail_{name}", cat="Binary") for name in cocktails
    }
    ingredient_decisions = {
        ingredient: pulp.LpVariable(f"ingredient_{ingredient}", cat="Binary")
        for ingredient in ingredients
    }

    prob = pulp.LpProblem("dks", pulp.LpMaximize)
    prob += pulp.lpSum(cocktail_decisions.values())  # maximize cocktails covered
    prob += pulp.lpSum(ingredient_decisions.values()) <= K  # ingredient budget

    for name, cocktail_decision in cocktail_decisions.items():
        for ingredient in cocktails[name]:
            prob += (
                cocktail_decision <= ingredient_decisions[ingredient]
            )  # cocktail only covered only if all its ingredients chosen

    start_time = time.perf_counter()
    prob.solve(pulp.PULP_CBC_CMD(msg=False))
    solve_time = time.perf_counter() - start_time
    return int(pulp.value(prob.objective)), solve_time, pulp.LpStatus[prob.status]


if __name__ == "__main__":

    cocktails = {}
    with open("ingredients.csv") as f:
        reader = csv.reader(f)
        for cocktail_name, *cocktail_ingredients in reader:
            cocktails[cocktail_name] = set(cocktail_ingredients)

    ingredients = set.union(*cocktails.values())

    for K in range(1, 130):
        num_cocktails, solve_time, status = solve(cocktails, ingredients, K)
        print(
            f"K={K:2d}  cocktails={num_cocktails}  status={status}  time={solve_time:.3f}s"
        )

ingredient.csv

Vodka martini,Vodka,Dry vermouth,Lemon,Olive
Mimosa,Champagne,Orange juice,Orange
Martini,Gin,Dry vermouth,Lemon
Margarita,Tequila,Triple sec,Lime juice,Salt
Grasshopper,White crème de cacao,Green crème de menthe,Cream,Mint
Ve.n.to,Grappa,Lemon juice,Honey syrup,Chamomile syrup,Honey syrup,Egg white,Lemon,White grape
Boulevardier,Bourbon whiskey,Sweet red vermouth,Campari,Orange,Lemon
Bee’s nees,London dry gin,Honey syrup,Lemon juice,Orange juice,Orange
Southside,London dry gin,Lemon juice,Simple syrup,Mint,Egg white
Whiskey sour,Bourbon whiskey,Lemon juice,Simple syrup,Egg white,Cherry,Orange
Champagne cocktail,Champagne,Cognac,Angostura bitters,Sugar,Grand Marnier,Orange,Cherry
Suffering bastard,Brandy,Gin,Lime juice,Angostura bitters,Ginger beer,Mint,Orange
Illegal,Mezcal,Overproof white rum,Lime juice,Falernum,Simple syrup,Maraschino,Egg white
Toronto,Canadian whiskey,Fernet Branca,Sugar,Angostura bitters,Orange
French 75,Gin,Simple syrup,Lemon juice,Champagne
Cuba Libre,Cola,White rum,Lime juice,Lime
Moscow mule,Vodka,Ginger beer,Lime juice,Lime
Bellini,Prosecco,Peach purée
Black russian,Vodka,Coffee liqueur
Caipirinha,Cachaça,Lime,Cane sugar
Mojito,White rum,Lime juice,Mint,Cane sugar,Lemon,Soda water
Dark ’n’ Stormy,Dark rum,Ginger beer,Lime
Bramble,Gin,Lemon juice,Simple syrup,Crème de mure,Lemon,Blackberry
French martini,Vodka,Raspberry liqueur,Pineapple juice,Lemon
Kamikaze,Vodka,Triple sec,Lime juice,Lime
Lemon drop martini,Vodka,Triple sec,Lemon juice,Sugar,Lime
Vesper,Gin,Vodka,Lillet blanc,Lemon
Alexander,Cognac,Brown crème de cacao,Light cream,Nutmeg
Americano,Campari,Sweet red vermouth,Soda water,Orange,Lemon
Angel face,Gin,Apricot brandy,Calvados
Aviation,Gin,Lemon juice,Maraschino,Crème de violette,Cherry
Bacardi cocktail,White rum,Lime juice,Grenadine
Between the sheets,White rum,Cognac,Triple sec,Lemon juice
Casino,Old tom gin,Maraschino,Orange bitters,Lemon juice,Lemon,Cherry
Clover club,Gin,Lemon juice,Raspberry syrup,Egg white,Raspberry
Daiquiri,White rum,Lemon juice,Simple syrup
Derby,Gin,Peach bitters,Mint
Dry martini,Gin,Dry vermouth,Lemon,Olive
Gin fizz,Gin,Lemon juice,Simple syrup,Soda water,Lemon
John collins,Gin,Lemon juice,Simple syrup,Soda water,Angostura bitters,Lemon,Cherry
Manhattan,Rye whiskey,Sweet red vermouth,Angostura bitters,Cherry
Mary pickford,White rum,Pineapple juice,Grenadine,Maraschino
Monkey gland,Gin,Orange juice,Absinthe,Grenadine
Negroni,Gin,Sweet red vermouth,Campari,Orange
Old fashioned,Whiskey,Angostura bitters,Sugar,Water,Orange,Cherry
Paradise,Gin,Apricot brandy,Orange juice
Planter’s punch,Dark rum,Orange juice,Pineapple juice,Lemon juice,Grenadine,Simple syrup,Angostura bitters,Cherry,Pineapple
Porto flip,Brandy,Port,Egg yolk,Nutmeg
Ramos fizz,Gin,Cream,Simple syrup,Lime juice,Lemon juice,Egg white,Orange flower water,Vanilla extract,Soda water
Rusty nail,Scotch whiskey,Drambuie,Lemon
Sazerac,Cognac,Absinthe,Sugar,Peychaud’s bitters,Lemon
Screwdriver,Vodka,Orange juice,Orange
Sidecar,Cognac,Triple sec,Lemon juice
Stinger,Cognac,White crème de menthe
Tuxedo,Old tom gin,Dry vermouth,Maraschino,Absinthe,Orange bitters,Cherry,Lemon
White lady,Gin,Triple sec,Lemon juice
French connection,Cognac,Amaretto
Mint julep,Bourbon whiskey,Mint,Water,Powdered sugar
White russian,Vodka,Coffee liqueur,Cream
Bloody Mary,Vodka,Tomato juice,Lemon juice,Worcestershire sauce,Tabasco,Celery salt,Pepper,Celery,Lemon
Kir,Dry white wine,Crème de cassis
Kir royal,Champagne,Crème de cassis
Long island iced tea,Vodka,Tequila,White rum,Gin,Cointreau,Lemon juice,Simple syrup,Cola,Lemon
Mai-tai,White rum,Dark rum,Curaçao,Orgeat (almond) syrup,Lime juice,Simple syrup,Pineapple,Mint,Lime
Tommy’s margarita,Tequila,Lime juice,Agave nectar
B52,Coffee liqueur,Triple sec,Irish cream liqueur
Barracuda,Gold rum,Galliano,Pineapple juice,Lime juice,Prosecco
Corpse reviver #2,Gin,Cointreau,Lillet blanc,Lemon juice,Absinthe,Orange
Cosmopolitan,Vodka,Cointreau,Lime juice,Cranberry juice,Lemon
Dirty martini,Vodka,Dry vermouth,Olive juice,Olive
Espresso martini,Vodka,Coffee liqueur,Simple syrup,Espresso
Golden dream,Triple sec,Galliano,Orange juice,Cream
Hemingway special,White rum,Grapefruit juice,Maraschino,Lime juice
Horse’s neck,Cognac,Ginger ale,Angostura bitters,Lemon
Irish coffee,Irish whiskey,Coffee,Cream,Sugar
Tom collins,Old tom gin,Lemon juice,Simple syrup,Soda water,Angostura bitters,Lemon,Cherry
Pina Colada,White rum,Coconut cream,Pineapple juice,Pineapple,Cherry
Pisco Sour,Pisco,Simple syrup,Lemon juice,Egg white,Angostura bitters
Russian spring punch,Vodka,Lemon juice,Crème de cassis,Simple syrup,Sparkling wine,Lemon,Blackberry
Sea breeze,Vodka,Cranberry juice,Grapefruit juice,Orange,Cherry
Sex on the beach,Vodka,Peach schnapps,Orange juice,Cranberry juice,Grapefruit juice,Orange
Singapore sling,Gin,Cherry liqueur,Cointreau,DOM Bénédictine,Pineapple juice,Lime juice,Grenadine,Angostura bitters,Cherry,Pineapple
Tequila sunrise,Tequila,Orange juice,Grenadine,Orange
Yellow bird,White rum,Galliano,Triple sec,Lime juice
Zombie,Dark rum,Gold rum,Demerara rum,Lime juice,Falernum,Grapefruit juice,Cinnamon syrup,Grenadine,Angostura bitters,Absinthe,Mint
Brandy crusta,Brandy,Lemon juice,Maraschino,Curaçao,Simple syrup,Aromatic bitters,Orange,Powdered sugar
Hanky panky,London dry gin,Sweet red vermouth,Fernet Branca,Orange
Last word,Gin,Green Chartreuse,Maraschino,Lime juice
Martinez,London dry gin,Sweet red vermouth,Maraschino,Orange bitters,Lemon
Vieux carré,Rye whiskey,Cognac,Sweet red vermouth,DOM Bénédictine,Peychaud’s bitters,Orange,Cherry
Cachanchara,Cuban aguardiente,Lemon juice,Honey,Water,Lime
Fernandito,Fernet Branca,Cola
Old cuban,Rum,Sparkling wine,Lime juice,Simple syrup,Angostura bitters,Mint
Paloma,Tequila,Grapefruit soda,Lime juice,Salt,Lime
Paper plane,Bourbon whiskey,Amaro Nonino,Aperol,Lemon juice
Penicillin,Blended Scotch whiskey,Islay Single Malt Scotch whiskey,Lemon juice,Honey syrup,Ginger,Candied ginger
Spicy fifty,Vodka,Elderflower syrup,Lemon juice,Honey syrup,Vanilla extract,Red chili pepper
Tipperary,Irish whiskey,Sweet red vermouth,Green Chartreuse,Angostura bitters,Orange
Trinidad sour,Angostura bitters,Orgeat (almond) syrup,Lemon juice,Rye whiskey
Naked and famous,Mezcal,Yellow Chartreuse,Aperol,Lime juice
New York sour,Rye whiskey,Lemon juice,Egg white,Simple syrup,Red wine,Lemon,Cherry
Spritz,Prosecco,Aperol,Soda water,Orange
Gimlet,Lime juice,Simple syrup,Gin
20th century,Gin,Lemon juice,White crème de cacao,Kina lillet,Lemon