Example: The Knapsack Problem

Description

Let’s consider a classic optimization problem: the knapsack problem. In the knapsack problem, you have a set of items, each with a weight and a value, and you want to select a subset of items to maximize the total value while staying within a given weight limit. Let’s set up a simple knapsack problem and solve it using Qaekwy.

The problem is approached by defining variables to represent the selection of each item, constraints to ensure the weight limit is not exceeded, and an objective function to maximize the total value of the selected items.

Variables

In this model, integer variables are used to represent whether each item is selected or not. Each item corresponds to a variable, which can take value 0 or 1 to indicate whether the item is included in the knapsack or not.

Constraints

• Weight Constraint: The total weight of the selected items should not exceed the given weight limit of the knapsack. This constraint is implemented using a relational expression that sums up the weights of selected items and compares them to the weight limit.

• Item Selection Constraint: To ensure that at most one of each item is selected, a constraint is added for each item’s corresponding variable. These constraints limit the variable’s value to be at most 1, indicating that the item can be selected at most once.

Objectives

The objective of this Knapsack Problem is to maximize the total value of the selected items. This is achieved by creating a linear combination of the values of selected items using their corresponding variables. The m.maximize(total_value) method is used to set this objective, specifying that the optimization should be a maximization.

Code

This example showcases how to use qaekwy to formulate and solve combinatorial optimization problems using a clear and structured approach.

import qaekwy as qw


def solve_knap_sack(weights: list[int], values: list[int], weight_limit: int):

    # Instantiate the model
    m = qw.Model()

    num_items = len(weights)

    # Define the variables that will indicate
    # whether an item is selected or not
    selected_items = [
        m.integer_variable(
            name=f"item_{i}",
            domain=(0, 1),
            branch_val=qw.BranchIntegerVal.VAL_MIN
        )
        for i in range(num_items)
    ]

    # Total weight of selected items should be less than or equal
    # to the weight limit
    m.constraint(
        sum(weights[i] * selected_items[i] for i in range(num_items))
        <= weight_limit
    )

    # Defines how to compute the total
    total_value = m.integer_variable(
        name="total_value",
        expression=sum(values[i] * selected_items[i] for i in range(num_items)),
        branch_val=qw.BranchIntegerVal.VAL_MAX
    )

    # Objective: maximize the totat's value
    m.maximize(total_value)

    # Return the solution found using
    # Branch-and-bound searcher
    return m.solve_one(searcher="bab")


if __name__ == "__main__":


    # Define the items' weights, values, and knapsack weight limit
    weights = [2, 3, 4, 5]
    values = [3, 4, 5, 6]
    knapsack_weight_limit = 7

    solution = solve_knap_sack(weights, values, knapsack_weight_limit)

    for solution_item, solution_value in solution.items():
        if "item" in str(solution_item).lower():
            idx = int(solution_item.split("_")[1])
            item_weight, item_value = weights[idx], values[idx]
            print(
                f"Item {idx}: Weight = {item_weight}; Value = {item_value}; Packed = {solution_value}"
            )

    print(f"Total Value: {solution.total_value}")

Result

When you run the above code, it will output the selected items along with their weights and values, as well as the total value of the selected items. The output will look something like this:

Item 0: Weight = 2; Value = 3; Packed = 1
Item 1: Weight = 3; Value = 4; Packed = 0
Item 2: Weight = 4; Value = 5; Packed = 0
Item 3: Weight = 5; Value = 6; Packed = 1
Total Value: 9