HLPL / VerTeX Modelling Language Documentation

← examples

# 0/1 Knapsack Problem
# Choose which items to pack to maximise total value without exceeding the
# bag's capacity. The smallest complete model that loads its data from Python:
# a set and indexed constants from functions, plus a single-value constant.
#
# Runs as is: `node run.mjs knapsack.hlpl` with the interpreter from
# get_interpreter prints the packed items and writes ./results.

model knapsack
set I = getItems()                             # Items
const v = getValues(), forall i in I           # Value of item i
const w = getWeights(), forall i in I          # Weight of item i
const C = 12                                   # Capacity of the bag
bin x, forall i in I                           # 1 if item i is packed, 0 otherwise

max sum_{i in I}{v_{i} * x_{i}}                # Maximise the value packed
constr sum_{i in I}{w_{i} * x_{i}} <= C        # Stay within capacity
end

import elytica
import json

# Data functions: a set returns a list of integers, an indexed constant a dict
# keyed by index. Lambdas and defs both work.
ITEMS = {1: (10, 5), 2: (40, 4), 3: (30, 6), 4: (50, 3), 5: (35, 7)}  # item: (value, weight)

getItems = lambda: list(ITEMS)
getValues = lambda: {i: value for i, (value, _) in ITEMS.items()}

def getWeights():
    return {i: weight for i, (_, weight) in ITEMS.items()}

def main():
    elytica.init_model("knapsack")
    elytica.run_model("knapsack")

    packed = [i for i in ITEMS if elytica.get_variable_value("knapsack", f"x{i}") > 0.5]
    value = elytica.get_best_primal_bound("knapsack")

    print(f"Packed items {packed}, total value {value:g}")
    elytica.write_results(json.dumps({"packed": packed, "value": value}))
    return 0

Read this through MCP: read with path: "examples/knapsack", or resource hlpl://examples/knapsack.