Knapsack Problem

The most classic variant where each item can either be taken entirely or left behind—no fractional selection is allowed. This binary constraint makes the problem NP-complete, meaning no known polynomial-time algorithm solves all instances optimally. The decision version asks: can a value of at least V be achieved without exceeding capacity W?

• Dynamic Programming solves it in pseudo-polynomial time O(nW), where n is the number of items and W is the capacity.
• Branch and Bound prunes the search tree using an upper bound derived from the fractional relaxation.
• Real-world example: selecting which capital projects to fund under a fixed annual budget.

Unlike the 0/1 variant, the fractional knapsack problem permits taking portions of items. This relaxation is solvable in O(n log n) time using a greedy algorithm: sort items by their value-to-weight ratio in descending order, then take as much of each item as capacity allows.

• The greedy approach is provably optimal for the fractional variant.
• Serves as the upper bound for branch-and-bound algorithms solving the 0/1 version.
• Models scenarios where goods are divisible, such as allocating a liquid commodity or blending raw materials.

The Multiple Knapsack Problem (MKP) generalizes the problem to m knapsacks, each with its own capacity. Each item can be assigned to at most one knapsack. This maps directly to bin packing with value maximization.

• Applications include load balancing across servers, assigning jobs to machines with limited memory, and allocating advertisements to time slots.
• Solved via Mixed-Integer Linear Programming (MILP) or specialized heuristics like the MTHM algorithm.
• The problem is strongly NP-hard, making exact solutions intractable for large instances.

For the 0/1 knapsack, dynamic programming constructs a table dp[i][w] representing the maximum value achievable using the first i items with capacity w. The recurrence relation is:

dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight_i] + value_i)

• Time complexity: O(nW), which is exponential in the input size of W but practical for moderate capacities.
• Space optimization: Can be reduced to O(W) using a 1D array iterated in reverse.
• For large W, meet-in-the-middle techniques split items into two sets, enumerate all subsets, and combine results.

The value density (value / weight) of each item is the single most important metric for knapsack heuristics. While the pure greedy approach fails for the 0/1 case, it provides:

• A tight upper bound when the fractional relaxation is solved.
• A warm start for metaheuristics like genetic algorithms and simulated annealing.
• A sorting criterion that dramatically improves branch-and-bound pruning efficiency.

Example: An item weighing 3kg worth $300 has a density of $100/kg, ranking higher than a 10kg item worth $500 ($50/kg).

The knapsack problem models numerous prescriptive analytics scenarios in autonomous supply chains:

• Cargo loading: Maximizing the value of goods packed into a container with weight and volume constraints.
• Inventory assortment: Selecting which SKUs to stock in limited warehouse shelf space.
• Bandwidth allocation: Assigning data packets to a fixed-capacity channel to maximize throughput.
• Budget allocation: Choosing which marketing campaigns to fund under a quarterly budget cap.

In each case, the constraint is hard (cannot exceed capacity), and the objective is maximization of total value.

A method for solving complex problems by breaking them down into simpler overlapping subproblems and storing their solutions to avoid redundant computation. For the 0/1 Knapsack Problem, a classic dynamic programming approach builds a table of size n × W (items × capacity) to compute the maximum value in pseudo-polynomial time. This technique is foundational for Bellman optimality and is widely used in supply chain inventory staging and multi-echelon optimization where subproblems recur.

An exact algorithm design paradigm that systematically enumerates candidate solutions by partitioning the search space and using upper and lower bounds to discard suboptimal regions. In the context of the Knapsack Problem, the Dantzig bound (linear programming relaxation) is often used to prune branches. This method guarantees an optimal solution without exhaustive enumeration and is critical for solving large-scale Mixed-Integer Linear Programming (MILP) models in supply chain network design.

A heuristic that builds a solution piece by piece, always choosing the next piece that offers the most immediate benefit without regard for future consequences. For the Fractional Knapsack Problem, a greedy strategy that selects items by descending value-to-weight ratio is provably optimal. For the 0/1 variant, it is not optimal but provides a fast, approximate solution. This approach is often used in real-time order promising logic and dynamic slot allocation where speed trumps precision.

A metaheuristic inspired by natural selection that evolves a population of candidate solutions using operators like crossover, mutation, and selection. For the Knapsack Problem, a binary chromosome naturally represents the inclusion or exclusion of items. Genetic algorithms excel at escaping local optima in highly constrained, non-linear problems and are applied in supply chain vehicle routing with capacity constraints and complex multi-objective procurement auctions.

A declarative paradigm where relations between variables are stated as constraints, and a solver finds feasible or optimal solutions without specifying a step-by-step algorithm. For multi-dimensional knapsack variants with side constraints (e.g., weight, volume, and budget limits), constraint programming offers highly expressive modeling. It is a core technology in job shop scheduling and complex supply chain configuration problems where feasibility is as critical as optimality.

An optimization framework where multiple conflicting objectives must be balanced, generating a Pareto Frontier of non-dominated solutions. The multi-dimensional knapsack problem naturally extends to this domain when maximizing value must be traded off against minimizing risk or carbon footprint. In autonomous supply chains, this is essential for carbon footprint optimization where cost, speed, and emissions are simultaneously considered, and no single solution dominates all criteria.