Knap Sack 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 set_objective 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.

from qaekwy.engine import DirectEngine
from qaekwy.model.constraint.relational import RelationalExpression
from qaekwy.model.specific import SpecificMaximum
from qaekwy.model.variable.branch import BranchIntegerVal
from qaekwy.model.variable.integer import IntegerVariable, IntegerExpressionVariable
from qaekwy.model.modeller import Modeller
from qaekwy.model.searcher import SearcherType

import json


class KnapsackProblem(Modeller):
    """
    KnapsackProblem
    """

    def __init__(self, weights, values, weight_limit):
        super().__init__()

        num_items = len(weights)
        selected_items = [
            IntegerVariable(
                var_name=f"item_{i}",
                domain_low=0,
                domain_high=1,
                branch_val=BranchIntegerVal.VAL_MIN,
            )
            for i in range(num_items)
        ]

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

        # Add variables and constraints to the problem
        for item_var in selected_items:
            self.add_variable(item_var)

        self.add_constraint(weight_constraint)

        # Maximize the total value
        total_value = IntegerExpressionVariable(
            var_name="total_value",
            expression=sum(values[i] * selected_items[i] for i in range(num_items)),
            branch_val=BranchIntegerVal.VAL_MIN,
        )

        self.add_variable(total_value)
        self.add_objective(SpecificMaximum(total_value))

        # Set the search strategy to Branch-and-bound Search (BAB)
        self.set_searcher(SearcherType.BAB)


if __name__ == "__main__":
    # Create a Qaekwy engine for direct interaction
    qaekwy_engine = DirectEngine()

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

    # Create the knapsack problem instance
    knapsack_problem = KnapsackProblem(weights, values, knapsack_weight_limit)

    # Request the Qaekwy engine to solve the knapsack problem
    response = qaekwy_engine.model(model=knapsack_problem)

    # Retrieve the list of solutions from the response
    list_of_solutions = response.get_solutions()

    solution = list_of_solutions[0]
    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}")