Performance Analysis of Multiple Knapsack Problem Optimization Algorithms: A Comparative Study for Retail and SME Applications

2.1 Problem formulation and mathematical model

The MKP with dual constraints presents a combinatorial optimization challenge in which n heterogeneous items must be optimally allocated across m distinct knapsacks [30]. This study addresses a practical retail bundling scenario with the following formal mathematical representation:

Given:

• Set of $n$ items $I=\{1, \ldots, n\}$, where each item $i \in I$ has: Value $\left(\mathrm{v}_{\mathrm{i}}\right)$ : representing item utility/desirability; Weight ($\mathrm{w}_{\mathrm{i}}$): physical weight in kilograms; Price ($\mathrm{p}_{\mathrm{i}}$): monetary cost in IDR
• Set of $m$ knapsacks $K=\{1, \ldots, m\}$, where each knapsack $\mathrm{j} \in \mathrm{K}$ has: Weight capacity $\left(\mathrm{C}_{\mathrm{j}}\right)$ : maximum allowable total weight; Budget constraint $\left(\mathrm{B}_{\mathrm{j}}\right)$ : maximum allowable total cost; Unique size-cost characteristics reflecting real retail bundles

The experimental dataset was systematically constructed to represent realistic retail bundling scenarios while ensuring mathematical tractability. The study incorporates 88 traditional Indonesian products strategically segmented into two primary categories: beverages (n=45) and snacks (n=43), reflecting typical product mix ratios in traditional retail operations. For each product, three key metrics were carefully calibrated: value coefficients ranging from 1.0 to 10.0 units derived from normalized customer preference data, weight parameters between 0.11 and 1.0 kilograms aligned with standard retail packaging constraints, and price variables from 6,000 to 60,000 IDR mapped to actual market price distributions.

The allocation framework comprises seven knapsacks, designed to represent distinct retail bundling strategies across multiple market segments. These configurations include premium bundles (4.0 kg, 250,000 IDR; 3.0 kg, 300,000 IDR), standard bundles (3.0 kg with budgets of 180,000-250,000 IDR), and value bundles (2.0 kg, 150,000 IDR; 1.5 kg, 160,000 IDR). This empirically derived configuration from market analysis of Indonesian retail operations balances operational constraints with customer segment requirements. The knapsack capacities and budget constraints were specifically calibrated to reflect realistic handling limitations in retail environments, accommodate diverse market segments' purchasing power, enable meaningful algorithmic performance comparison, and maintain computational feasibility for systematic analysis.

Mathematical model:

Maximize: $\sum_{j=1}^m \sum_{i=1}^n v_i x_{i j}$             (1)

Subject to:

1. Weight Constraint:

$\sum_{i=1}^n w_i x_{i j} \leq C_j \forall j \in\{1, \ldots, m\}$             (2)

2. Budget Constraints:

$\sum_{i=1}^n p_i x_{i j} \leq B_j \forall j \in\{1, \ldots, m\}$            (3)

3. Item Uniqueness:

$\sum_{j=1}^m x_{i j} \leq 1 \forall i \in\{1, \ldots, n\}$             (4)

4. Binary Decision Variables:

$x_{i j} \in\{0,1\} \forall i, j$             (5)

where, $x_{i j}$ is binary decision variable ( 1 if item i is assigned to knapsack $\mathrm{j}$, 0 otherwise); $v_i$ represents the value of item I; $w_i$ represents the weight of item i; $p_i$ represents the price of item $\mathrm{i}$; $C_j$ represents the weight capacity of knapsack $\mathrm{j}$; $B_j$ represents the budget capacity of knapsack $j$.

2.2 Implementation

This section details eight algorithm implementations for solving the dual-constrained MKP, ranging from exact methods to heuristic approaches. Each implementation is analyzed for theoretical complexity, memory requirements, and optimization strategies.

2.2.1 BDP

BDP enhances the traditional approach through numpy vectorization and improved memory management. This implementation maintains optimality while introducing several key optimizations for computational efficiency.

1. Core Architectural Improvements

1) Numpy-based array operations for vectorized computation; 2) Efficient memory allocation through data type optimization; 3) Decimal precision handling through integer scaling; 4) Enhanced state transition management

2. Key Implementation Features can be seen in Algorithm 1

3. Technical Optimizations in Space Complexity

The technical optimizations in BDP implementation focus on two critical areas: memory management and computational enhancements. Memory management is implemented through several sophisticated strategies that optimize resource utilization. The implementation uses np.float32 instead of the default float64 data type to reduce memory footprint while maintaining numerical precision. Pre-allocated arrays with optimal data types are employed to minimize memory allocation overhead during computation. Integer-based computations are implemented to improve numerical accuracy and reduce floating-point errors, while efficient memory access patterns optimize data retrieval and storage operations. Computational enhancements are achieved through several key mechanisms: vectorized operations for state updates significantly improve processing speed by performing operations on entire arrays simultaneously, integer scaling techniques ensure decimal precision while maintaining computational efficiency, improved array indexing strategies optimize data access patterns, and better memory locality exploitation enhances cache utilization and reduces memory access latency. These technical optimizations able to create an efficient implementation that balances memory usage with computational performance while maintaining solution accuracy.

In advanced matter, we could employ employs a Rolling Array technique, significantly reducing space complexity from O(n×m×W×B) to O(2×m×W×B) by adopting a two-array approach instead of maintaining n+1 arrays. This implementation enables more efficient memory utilization without compromising computational accuracy in the optimization process. Then, adopt bit-level state representation using np.int8 for decision matrices, replacing the more memory-intensive float32 implementation. This approach achieves a 75% reduction in per-cell memory requirements while maintaining efficient state tracking with minimal overhead. The implementation is reinforced with memory management mechanisms involving strategic garbage collection post-knapsack processing and unused state clearing, ensuring peak memory utilization remains below O(2×m×W×B). As worth mentioning, the subsection 2.2.4 are explanation using the optimized DP using parallel rolling.

2.2.2 Numba-accelerated DP

Numba-accelerated DP extends the BDP approach by leveraging Just-In-Time (JIT) compilation for machine-level optimization. This implementation achieves significant performance improvements while maintaining solution optimality.

1. Core Implementation Architecture as in Algorithm 2

2. Numba Optimization Features

The Numba optimization features leverage advanced JIT compilation strategies and robust performance optimization techniques to enhance computational efficiency. JIT compilation strategies are implemented through sophisticated function specialization for data types, enabling optimized machine code generation. The implementation incorporates loop optimization and unrolling techniques that maximize execution efficiency, while SIMD instruction generation capabilities harness modern processor architectures for parallel computation. Cache-aware memory access patterns are implemented to minimize memory latency and optimize data retrieval. Performance optimizations are achieved through several key mechanisms: machine code generation for core computations significantly reduces execution overhead, while the elimination of Python interpreter overhead enhances raw computational speed. The implementation also employs automatic vectorization of operations to leverage hardware-specific capabilities, complemented by hardware-specific optimizations that take advantage of available system resources. These optimization features work in concert to create a highly efficient implementation that significantly outperforms traditional Python execution while maintaining solution accuracy and reliability.

3. Technical Implementation Details

The technical implementation details of the Numba-accelerated DP focus on two critical aspects: memory management and computational enhancements. The memory management system implements contiguous array allocation strategies to optimize memory access patterns and enhance cache utilization. This is supported by type-specific memory layouts that maximize memory efficiency for different data types, complemented by optimized cache utilization mechanisms that reduce memory access latency. The implementation also features reduced memory access latency through careful memory organization and access pattern optimization. On the computational side, the implementation leverages compiled loop execution capabilities that significantly enhance processing speed. This is supported by optimized boundary checking mechanisms that minimize computational overhead while maintaining solution validity. The system employs efficient register allocation strategies to maximize processor utilization, while reduced function call overhead minimizes computational bottlenecks. These technical features are carefully integrated to create a highly optimized implementation that balances memory efficiency with computational performance.

4. Key Improvements over BDP by Implementation Considerations

We need consider for deployment requirement, such as LLVM compiler infrastructure, CPU with SIMD support, Sufficient memory capacity, Proper environment setup. Also in matter of Optimization Guidelines can follows Function signature type specification, Array contiguity maintenance, Compiler directive optimization, Memory access pattern design.

2.2.3 Parallel processing implementation

Parallel processing enhances the Numba-accelerated approach by introducing multi-threaded computation and parallel array operations. This implementation leverages both thread-level parallelism and SIMD operations for maximum performance.

1. Parallel Architecture Configuration as in Algorithm 3

2. Parallelization Strategy

The parallel processing implementation employs a sophisticated multi-level task distribution framework designed to optimize computational efficiency while maintaining solution integrity. Our approach incorporates three primary optimization layers:

Layer 1: Thread-Level Parallelization. The implementation utilizes Numba's parallel processing capabilities through the @njit(parallel=True) decorator, enabling efficient thread management (line code 2-9). This structure facilitates parallel item processing while maintaining sequential knapsack evaluation to prevent resource conflicts. Empirical analysis demonstrates a significant reduction in processing time from 79.16 seconds (base implementation) to 1.21 seconds, achieving an 80.47x speedup (more explanation in Results Section)

Layer 2: Resource Distribution Optimization. Our implementation incorporates dynamic workload balancing through strategic task partitioning:

• Computation Distribution, which Parallel item evaluation across available threads, Synchronized state updates for solution consistency, Memory-aware task allocation minimizing thread contention
• Memory Access Optimization, which Thread-local storage for intermediate computations, Cache-aligned data structures reducing memory latency, Optimized memory access patterns enhancing cache utilization.
• Load Balancing Mechanism can be seen in line code 1 and 8.

Layer 3: Synchronization Control. The implementation maintains solution consistency through carefully designed synchronization mechanisms as State Management: Atomic updates for shared resource modifications, Barrier synchronization at critical computation points, and Efficient thread coordination minimizing overhead.

3. Technical Implementation Features

The technical implementation features encompass two key areas of focus: parallel processing components and memory architecture. The parallel processing components are built around a sophisticated thread pool management system that efficiently handles task distribution across available processors. This is supported by a work queue distribution mechanism that optimizes task allocation and processing flow. The implementation incorporates essential synchronization primitives to maintain data consistency and prevent race conditions during parallel execution. To ensure robust concurrent processing, comprehensive race condition prevention mechanisms are implemented throughout the system. The memory architecture is designed with careful consideration of thread-local storage capabilities to minimize contention and maximize parallel efficiency. This is complemented by shared memory management strategies that optimize resource utilization across threads. The implementation also employs cache line optimization techniques to enhance memory access performance, supported by memory fence implementation that ensures proper synchronization of memory operations across multiple threads. These technical features work in concert to create a highly efficient parallel processing system that maintains both performance and reliability.

4. Key Improvements over Numba DP

1. Implementation Benefits: Scalable with CPU cores, better resource distribution, Improved cache utilization, Reduced memory pressure.
2. Trade-off: Increased implementation complexity, Hardware dependencies, Thread coordination overhead, Non-linear scaling beyond 4 cores, System resource requirements.

5. Implementation Requirements

1. Hardware Prerequisites: Multi-core processor. Sufficient L3 cache, Adequate memory bandwidth, NUMA architecture awareness.
2. Software Dependencies: Threading library support, Numba parallel features, Memory management tools, Synchronization primitives.

6. Optimization Guidelines

1. Thread Management: Optimal thread count selection, Work distribution strategy, Synchronization minimization, Cache coherency maintenance.
2. Memory Management: Thread-local allocation, Cache-line alignment, Memory access patterns, False sharing prevention.

The parallel implementation offers improved resource utilization and memory efficiency compared to Numba-only implementation, making it particularly suitable for large-scale retail applications with multiple CPU cores available. The slight increase in runtime is offset by better scalability and resource management.

2.2.4 Parallel rolling

Parallel rolling combines multi-threaded computation with memory optimization through state space rolling. This implementation achieves memory efficiency while maintaining parallel processing benefits through a three-state matrix rotation technique.

1. Core Implementation Architecture as seen in Algorithm 4

2. Memory Optimization Strategy

The memory optimization strategy in parallel rolling implementation centers around two critical components: state space rolling and decision tracking. The state space rolling mechanism employs an innovative three-state matrix rotation approach that significantly reduces memory footprint while maintaining computational efficiency. This system implements current/previous state tracking to manage state transitions effectively, coupled with efficient state transition mechanisms that optimize memory usage during computation. The implementation maintains a minimal memory footprint through careful resource management, ensuring optimal performance with reduced memory requirements. Complementing this, the decision tracking component utilizes a compact decision matrix design that efficiently stores solution choices. This is supported by efficient backtracking support mechanisms that enable solution reconstruction when needed, while employing a binary state representation to minimize memory usage. The implementation also features memory-efficient solution reconstruction capabilities that allow for detailed solution recovery without significant memory overhead. These optimization strategies work together to create a memory-efficient implementation that maintains high performance while significantly reducing memory requirements compared to traditional approaches.

3. Parallel Processing Features

The parallel processing features of the parallel rolling implementation are structured around two fundamental components: thread management and memory architecture. The thread management system implements task parallelization across knapsacks through an efficient distribution mechanism that optimizes workload allocation. This is supported by thread-safe state updates that ensure data consistency during parallel execution, complemented by synchronized memory access controls that prevent data corruption. The implementation employs load-balanced work distribution strategies to ensure optimal resource utilization across all available processors. The memory architecture is specifically designed to support parallel processing efficiency, implementing cache-friendly state rotation mechanisms that optimize memory access patterns. The system utilizes thread-local computation capabilities to minimize contention between threads, supported by optimized memory access patterns that enhance overall performance. These features are further strengthened by reduced memory contention mechanisms that ensure smooth parallel execution. Together, these parallel processing features create a highly efficient implementation that maximizes computational throughput while maintaining data consistency and solution accuracy.

4. Key Improvements

1. Performance Balance: Maintained parallel speedup, Reduced memory pressure, Improved cache performance, Efficient state management.
2. Trade-offs: Additional implementation complexity, State rotation overhead, Decision tracking overhead, Complex solution reconstruction, Synchronization requirements.

5. Implementation Considerations

1. Technical Requirements: Multi-core processor support, Cache-coherent architecture, Memory management capabilities, Thread synchronization support.
2. Optimization Guidelines: State rotation timing, Memory access patterns, Thread work distribution, Cache line alignment.

The parallel rolling implementation represents an optimal balance between computational efficiency and memory usage, making it particularly suitable for memory-constrained environments while maintaining parallel processing benefits.

2.2.5 Genetic algorithm

The genetic algorithm provides a metaheuristic approach to MKP through evolutionary computation [3, 9, 11]. This implementation balances exploration and exploitation while handling dual constraints effectively.

1. Core Genetic Components as seen in Algorithm 5

2. Algorithmic Parameters

As seen in Table 1, The GA implementation utilizes carefully tuned parameters to balance exploration and exploitation. Population size of 150 individuals was chosen to maintain sufficient genetic diversity while remaining computationally manageable. The algorithm runs for 100 generations to allow adequate evolution time while preventing excessive computational overhead. A moderate mutation rate of 0.1 enables sufficient genetic variation without disrupting beneficial gene combinations. Elite size of 10 preserves the best solutions across generations while maintaining population diversity. Tournament size of 5 provides appropriate selection pressure - large enough to favor fitter individuals but small enough to prevent premature convergence.

Table 1. Genetic algorithm parameters

To validate the GA parameter settings, here we focus on population size. The result can be seen in Table 2.

Table 2. Population size analysis

Based on comprehensive parameter sensitivity analysis on Table 2, comparing population sizes (50, 100, 150, 200) in the genetic algorithm implementation for MKP, population size 100 emerges as the optimal configuration. This conclusion is substantiated through rigorous empirical evaluation across multiple performance metrics: solution quality (total value = 230.0), computational efficiency (execution time = 1.5822s), resource utilization (memory = 132.45 MB), and optimization effectiveness (weight utilization = 83.90%, price utilization = 92.62%). While population size 150 achieved marginally higher solution quality (232.5), the minimal improvement of 1.09% does not justify the substantial increases in computational overhead (55.6% longer execution time) and memory consumption (9.74% higher), thus establishing population size 100 as the most efficient parameter setting for balancing solution quality and computational resources in this specific multiple knapsack optimization context.

As seen in Table 3, the evolution process is governed by four key control mechanisms. Selection Pressure utilizes an adaptive approach that automatically adjusts based on population diversity and convergence trends. Diversity Maintenance actively monitors and maintains genetic variation through strategic mutation and crossover operations. Convergence Control implements dynamic adjustments to prevent premature convergence while ensuring efficient solution space exploration. Population Renewal mechanism introduces new genetic material by replacing 20% of the population with fresh individuals when diversity drops below critical thresholds, helping escape local optima while preserving good solutions.

Table 3. Genetic algorithm evolution controls

3. Genetic Operators

Based on Table 4, the GA implementation incorporates three essential genetic operators, each carefully designed to ensure effective solution space exploration and exploitation:

1. Selection Mechanism employs a multi-faceted approach combining tournament selection for parent choice, elite preservation to maintain best solutions, fitness-based ranking to guide selection pressure, and diversity-aware selection to prevent premature convergence. Tournament selection with size 5 provides balanced selection pressure, while elitism preserves the top 10 solutions across generations.
2. Crossover Strategy utilizes a sophisticated approach with four key components. Two-Point Crossover enables effective genetic material exchange between parents. Constraint-Aware Recombination ensures offspring validity by respecting knapsack capacity and budget constraints. Solution Repair mechanisms correct any constraint violations post-crossover. Feasibility Preservation maintains solution validity throughout the evolutionary process.
3. Mutation Operations implement four complementary strategies. Random Gene Modification allows for exploration of new solution spaces. Intelligent Mutation applies problem-specific knowledge to guide modifications. Adaptive Rate Adjustment dynamically modifies mutation probability based on population diversity. Constraint Satisfaction ensures all mutations maintain solution feasibility within knapsack constraints.

Table 4. Genetic operators

These genetic operators work synergistically to achieve the observed performance metrics, including solution quality of 230.0 and resource utilization of 92.62% for price and 83.90% for weight capacity. The operators' design particularly emphasizes maintaining solution feasibility while enabling effective search space exploration.

4. Implementation Enhancements

The implementation enhancements in the genetic algorithm focus on two crucial areas: constraint handling and performance optimization. In constraint handling, the implementation employs a sophisticated repair mechanism that corrects infeasible solutions while maintaining genetic diversity. This is complemented by carefully designed penalty functions that guide the search toward feasible regions of the solution space. The system implements robust feasibility preservation mechanisms to maintain solution validity throughout the evolutionary process, supported by comprehensive solution validation procedures that ensure all constraints are satisfied. Performance optimization is achieved through several key mechanisms: parallel fitness evaluation capabilities that leverage multiple processors for increased computational efficiency, sophisticated caching mechanisms that reduce redundant calculations, and early stopping criteria that prevent unnecessary computational overhead. The implementation also features advanced population management techniques that maintain genetic diversity while focusing the search on promising regions of the solution space. These enhancement features work synergistically to create an efficient and reliable genetic algorithm implementation that effectively balances solution quality with computational performance while maintaining strict adherence to problem constraints.

5. Implementation Trade-offs

1. Advantages: Low Memory Requirements, Anytime Solution Availability, Population Diversity, Parallel Potential.
2. Limitations: Non-Guaranteed Optimality, Parameter Sensitivity, Convergence Variance, Solution Variability.

6. Optimization Guidelines:

1. Parameter Tuning: Population Size Selection, Generation Count Optimization, Mutation Rate Adjustment, Tournament Size Calibration.
2. Implementation Focus: Constraint Satisfaction, Diversity Maintenance, Convergence Control, Solution Quality Balance.

The genetic algorithm implementation provides a robust alternative when optimal solutions aren't strictly required, offering good solution quality with moderate computational resources [30, 31]. This makes it particularly suitable for larger problem instances where exact methods become computationally prohibitive.

2.2.6 Greedy algorithm

The greedy algorithm provides a fast, deterministic heuristic approach by making locally optimal choices based on value density metrics [32, 33]. This implementation achieves efficient resource utilization through strategic item selection.

1. Core Implementation Architecture as seen in Algorithm 6

2. Selection Strategy

1. Value Density Metrics
2. Sorting Criteria: Knapsack Efficiency Ratio, Item Value Density, Resource Consumption Rate, Combined Utility Measure

3. Implementation Features

1. Core Components: Single-pass item selection, Greedy choice function, Constraint validation, Resource tracking
2. Optimization Elements: Efficient sorting, Early termination, Resource monitoring, Solution construction

4. Implementation Advantages

1. Computational Benefits: Minimal runtime overhead, Linear memory scaling, Deterministic behavior, Simple implementation
2. Practical Benefits: No parameter tuning, Immediate solutions, Predictable performance, Easy maintenance

5. Solution Characteristics

1. Resource Utilization: Memory Efficiency: high; CPU Utilization: minimal; I/O Requirements: negligible; Storage Needs: constant

6. Implementation Trade-offs

1. Advantages: Extremely fast execution, Simple implementation, Deterministic results, Low resource requirements
2. Limitations: Sub-optimal solutions, Local decision making, No solution refinement, Fixed selection criteria

7. Key Improvements over Previous Approaches

1. Performance Gains: Fastest execution time, Minimal memory overhead, Simple computation model, Immediate results.
2. Resource Efficiency: Constant memory usage, Single-pass processing, No iteration required, Linear scaling

8. Implementation Guidelines

1. Selection Criteria: Value density metric choice, Sorting strategy selection, Constraint handling, Resource balancing
2. Optimization Focus: Sort efficiency, Memory management, Constraint checking, Solution construction

The Greedy approach provides an extremely fast solution with reasonable quality, making it particularly suitable for real-time applications or when computational resources are severely constrained. Its performance characteristics make it an excellent choice for initial solution generation or when quick approximations are acceptable.

2.2.7 Branch & Bound algorithm

Branch & Bound provides a systematic approach to finding optimal or near-optimal solutions through intelligent search space exploration and pruning [3, 29, 34]. This implementation utilizes priority-based searching with efficient bounding mechanisms.

1. Core Data Structures as seen in Algorithm 7

2. Bounding Strategy

3. Search Space Management

The search space management in the Branch & Bound implementation is structured around two key components: node exploration strategy and pruning mechanisms. The node exploration strategy employs a best-first search approach using a priority queue system to efficiently navigate the solution space. This is supported by depth-based exploration control that manages the search depth to balance between exploration and exploitation. The implementation features efficient node pruning techniques that eliminate unpromising branches of the search tree, complemented by solution space partitioning strategies that effectively divide the problem into manageable subproblems. The pruning mechanisms are implemented through several sophisticated approaches: upper bound comparison techniques that quickly identify and eliminate suboptimal branches, rigorous feasibility checking procedures that maintain solution validity, comprehensive resource constraint validation that ensures all solutions meet problem constraints, and dominated solution elimination strategies that remove redundant search paths. These search space management features work together to create an efficient implementation that effectively explores the solution space while minimizing computational overhead through strategic pruning and exploration control.

4. Implementation Features

The implementation features of the Branch & Bound algorithm encompass two primary aspects: search optimization and memory management. The search optimization process is built around priority-based exploration that efficiently guides the search toward promising regions of the solution space. This is enhanced by efficient bound computation mechanisms that quickly evaluate the potential of each branch, complemented by early termination capabilities that prevent unnecessary exploration of unpromising paths. The system maintains comprehensive solution tracking procedures that record the best solutions found during the search process. Memory management is implemented through several sophisticated strategies: compact node representation techniques minimize memory usage while maintaining all necessary information, efficient state storage mechanisms optimize memory utilization during the search process, and memory-aware pruning strategies remove unnecessary nodes to conserve memory resources. The implementation also features comprehensive resource tracking capabilities that monitor and optimize resource usage throughout the execution. These implementation features are carefully integrated to create a highly efficient Branch & Bound algorithm that effectively balances search effectiveness with memory efficiency.

5. Key Advantages

1. Computational Benefits: fast convergence, efficient pruning, limited memory usage, anytime solutions
2. Solution Quality: Near-optimal results, Guaranteed bounds, Solution certificates, Quality guarantees

6. Implementation Trade-offs

1. Advantages: Efficient search space exploration, Strong pruning capabilities, Quality guarantees, Memory efficiency
2. Limitations: Complex implementation, Variable runtime, Search space dependency, Branch selection impact

7. Performance Optimization

1. Search Strategy: Node selection heuristics, Pruning criteria optimization, Bound computation efficiency, State space management
2. Memory Optimization: Node compression, State reuse, Pruning effectiveness, Resource utilization.

2.3 Theoretical complexity analysis

Table 5 presents the theoretical complexity analysis for all implemented algorithms, providing critical insights into their scalability and resource requirements. The complexity is expressed in terms of key problem parameters: n (number of items), m (number of knapsacks), W (maximum weight capacity), B (maximum budget), and p (number of processors for parallel variants).

Table 5. Algorithm complexity comparison

Note: *worst case

Numba-accelerated implementations maintain the same theoretical complexity O(n×m×W×B) as their traditional counterparts, but achieve significant practical speedup through JIT compilation and hardware optimization. Similarly, the Parallel variant reduces actual runtime by a factor of p through parallel processing, resulting in O(n×m×W×B)/p time complexity, while maintaining the same space requirements.

The parallel rolling variant innovatively reduces space complexity to O(3×m×W×B) through state space rolling, while maintaining the same time complexity as other DP variants. This represents a significant memory optimization without compromising solution quality.

Genetic algorithm exhibits significantly lower complexity of O(population_size×n), making it more scalable for larger problem instances, though without optimality guarantees. The Greedy approach achieves the lowest complexity of O(n) in both time and O(1) in space, offering extremely fast execution at the cost of solution quality.

Branch & Bound, while having worst-case time complexity of O(2^n), often performs significantly better in practice due to effective pruning strategies. Its space complexity remains linear at O(n), making it memory-efficient for larger problems.

The theoretical complexity analysis provides insights into algorithm scalability and resource requirements. Notably, while Branch & Bound shows exponential worst-case complexity, its practical performance can be significantly better due to effective pruning strategies. The parallel variants maintain the same theoretical complexity as BDP but achieve practical speedup through concurrent execution.

2.4 Evaluation framework

2.4.1 Experimental setup

All experiments were conducted on Intel Core Ultra 7 22 threads with 32 GB memory running Python 3.8. For reproducibility, random seeds were set to 42 where applicable. The implementation utilized NumPy 1.19 for numerical computations and Pandas 1.2 for data management. Tests were executed with a time limit of 3600 seconds per algorithm.

Test Dataset Characteristics as follows: 88 products (45 beverages, 43 snacks); 7 knapsacks with varying constraints; Value range: 1.0-10.0 units; Weight range: 0.11-1.0 kg; Price range: 6,000-60,000 IDR.

The knapsack constraints were designed to reflect real-world retail bundling scenarios, with capacities ranging from 1.5kg to 4.0kg and budgets from 150,000 to 300,000 IDR.

2.4.2 Performance metrics

The performance evaluation framework incorporates multiple metric categories to ensure comprehensive assessment of each algorithm. For solution quality assessment, we employ Total Value Achievement (TVA) to measure absolute solution value, alongside Relative Value Achievement (RVA) which contextualizes solution value against theoretical optimum. Resource Utilization Efficiency (RUE – denoted as price utilization ratio) evaluates how effectively each algorithm utilizes available constraints, while Constraint Violation Rate (CVR) monitors the frequency of constraint breaches during solution construction.

In terms of computational efficiency, we track Execution Time (ET) measured in CPU seconds, alongside detailed memory profiling through Peak Memory Usage (PMU) and Average Memory Consumption (AMC) metrics measured in megabytes. The framework also considers Scaling Efficiency to evaluate performance changes with increasing problem size, and employs a Resource Efficiency Ratio (RER) to provide a balanced measure of solution quality versus computational cost. These metrics collectively provide a multi-dimensional view of algorithm performance, enabling thorough comparative analysis.

$RVA=\frac{TVA }{Theoretical{\text_}Maximum }$             (6)

$Price\ utilization\ ratio=\frac{used\ price}{available\ budget}$            (7)

$R E R=\frac{T V A}{(E T \times P M U)}$             (8)

Additionally, we incorporate algorithm-specific metrics to capture unique characteristics of each implementation. These include convergence rate analysis to measure solution improvement over time, solution stability assessment to evaluate result consistency across multiple runs, and population diversity metrics specifically for the genetic algorithm implementation to monitor solution space exploration.

2.4.3 Statistical analysis framework

To facilitate objective comparison, we implement a Multi-criteria Decision Analysis using the TOPSIS method for algorithm ranking. The criteria weights are carefully distributed to reflect practical importance: solution quality (0.5), runtime efficiency (0.3), memory usage (0.1), and resource utilization (0.1). This weighting scheme prioritizes solution quality while maintaining balanced consideration of computational efficiency and resource utilization aspects. Moreover, we are using 10% weight perturbation in matter of stability verification.

4.1 Algorithm performance insights

The comprehensive evaluation of eight MKP algorithms reveals distinct performance tiers and implementation trade-offs. The parallel rolling (P-R) achieved optimal solution quality (247.50) with resource utilization (99.66% price, 81.08% weight). Followed by the parallel processing (P-P) variants consistently demonstrated superior performance across multiple metrics, achieving optimal solution quality (247.50) while maintaining high resource utilization (99.66% price, 94.46% weight). Even though, P-R obtain lower in weigth utilization, it does outperform in matter of TOPSIS analysis followed by P-P. Thus, P-R and P-P is interchangeable according to the user needs.

4.1.1 Performance-resource trade-offs

Our analysis reveals distinct performance tiers among the implemented algorithms. The High-Performance Tier, dominated by parallel rolling and parallel processing variants, demonstrates exceptional capabilities with optimal solution quality achieving 99.66% price utilization and 94.46% weight utilization. These implementations deliver significant performance improvements, showing 80.47x speedup compared to BDP. While they incur higher memory overhead, the performance gains justify this trade-off, making them: 1) ideal for large-scale retail operations handling multiple product lines; 2) Supports real-time decision making in dynamic pricing scenarios; 3) Enables efficient resource allocation in complex bundling strategies. However, these implementations require specific infrastructure considerations, including multi-core processor capabilities, substantial memory allocation, and careful thread management overhead handling.

The Balanced Performance Tier, represented by Numba and Branch & Bound implementations, offers a compelling compromise between performance and resource requirements. These algorithms consistently achieve near-optimal solutions exceeding 90% of optimal value, while delivering excellent runtime efficiency with over 240x speedup. Their moderate memory requirements, ranging from 118.09 to 852.08 MB, coupled with predictable performance characteristics and stable resource utilization, make them 1) Suitable for medium-scale retail operations; 2) Enables quick response to market changes; 3) Supports efficient inventory management.

In the resource-efficient tier, the greedy and genetic algorithm implementations provide practical solutions for resource-constrained environments. These algorithms maintain good solution quality exceeding 93% of optimal value while operating with minimal memory footprint below 150MB. Their linear scaling characteristics make them 1) Ideal for small retailers with limited IT infrastructure; 2) Supports rapid decision-making in straightforward bundling scenarios; 3) Cost-effective implementation.

4.1.2 Implementation considerations

The choice of algorithm significantly impacts both solution quality and resource requirements. Memory usage varies from 118.09MB (Branch & Bound) to 852.08MB (Numba), while runtime ranges from negligible (Greedy) to 79.1570 seconds (BDP).

4.2 Business context analysis

4.2.1 Enterprise retail applications

For large retail operations, our findings support the adoption of parallel processing solutions based on: (1) Consistent achievement of optimal solutions; (2) High resource utilization (>94% for both constraints); (3) Linear scaling with processor count; (4) Robust performance across problem variations.

Alternatively, enterprise retail applications can adopt parallel rolling based on: memory-constrained environments, similar performance benefits, reduced memory footprint (299.68 MB).

4.2.2 SME implementation considerations

Small-medium enterprises benefit from lighter-weight implementations: (1) Branch & Bound provides 90% utilization with minimal resources; (2) Greedy algorithm offers immediate results for time-critical decisions; (3) Memory efficiency crucial for limited infrastructure; (4) Acceptable solution quality for smaller scale operations.

Alternatively, SME could use Greedy Algorithm where Time-critical operations, Limited computational resources, Straightforward implementation.

4.2.3 Implementation strategy framework

Our Implementation Strategy Framework provides comprehensive guidelines tailored to different operational scales, based on empirical evidence from our algorithmic analysis. For enterprise-scale implementations, we recommend deploying parallel variants, particularly parallel rolling, which demonstrated superior performance (TOPSIS score: 0.928) and optimal resource utilization (99.66% price, 81.08% weight utilization). The implementation requires specific technical infrastructure including multi-core processors, minimum 16GB RAM, and appropriate storage systems. The deployment process follows a structured three-phase approach: infrastructure assessment and setup, algorithm deployment with parallel processing configuration, and performance optimization through thread allocation tuning and cache optimization.

For SME implementations, we propose a resource-conscious approach centered on Branch & Bound algorithm, which achieved exceptional efficiency (0.0417 seconds runtime) while maintaining minimal resource requirements (118.09 MB memory footprint). This implementation pathway requires standard computing infrastructure and follows a simplified three-phase deployment: basic setup verification, streamlined algorithm implementation, and targeted performance tuning. Both frameworks are supported by empirical evidence from our experimental results, ensuring practical applicability while maintaining solution quality across different operational scales. The implementation guidelines incorporate specific technical requirements, algorithmic selection criteria based on TOPSIS analysis, and detailed deployment phases, providing a comprehensive roadmap for successful implementation across varying business contexts.

4.3 Theoretical, algorithm adaptability and practical implications

Our study reveals several significant insights into algorithm design and implementation. The analysis demonstrates that memory-performance trade-offs play a crucial role in determining practical utility, while parallel processing approaches effectively address computational bottlenecks in large-scale implementations. Notably, simple heuristic approaches have shown remarkable capability in providing competitive solutions for practical applications, challenging the notion that complex algorithms are always necessary for effective problem-solving.

Our analysis reveals critical insights into algorithm adaptability across dynamic operational environments. The parallel variants demonstrate exceptional resilience under parameter variations, maintaining solution quality within 98.5% of optimal values during price fluctuations (±20%) and achieving >95% resource utilization efficiency under weight variations (±15%). These implementations maintain consistent runtime performance (1.1162-1.2098 seconds) and stable memory utilization (<5% variation), validating their suitability for enterprise-scale deployments where parameter stability cannot be guaranteed. Similarly, the Branch & Bound algorithm exhibits robust adaptability characteristics particularly valuable for resource-constrained environments, maintaining >90% solution quality under price variations while preserving efficient execution time (0.0417 seconds ±8%) and stable memory consumption (118.09 MB ±5%), with Greedy and GA implementations showing predictable performance patterns under dynamic conditions.

This empirical evidence substantiates our implementation recommendations across varying operational scenarios, with parallel variants demonstrating superior adaptability for enterprise deployments and Branch & Bound emerging as a reliable choice for SME applications. The observed performance stability under dynamic parameter changes validates both the theoretical robustness of our algorithmic approaches and their practical applicability in real-world retail environments where price and weight variations are common operational challenges. These findings significantly enhance our understanding of algorithm behavior under dynamic conditions, providing crucial insights for implementation decisions while maintaining optimal resource utilization and solution quality across different operational scales.

The implementation patterns identified through this research highlight the importance of sophisticated resource allocation strategies. Successful implementations require careful attention to dynamic memory management for large problem instances, optimization of processor allocation, and implementation of cache-aware data structures. These technical considerations are complemented by robust solution quality management approaches, including the establishment of early termination criteria based on solution quality thresholds, careful balancing of resource utilization, and comprehensive monitoring of constraint satisfaction throughout the solution process.

This research contributes significantly to the theoretical understanding and practical application of MKP algorithms. By quantifying performance-resource trade-offs across different implementation scenarios, validating the benefits of parallel processing approaches in MKP solutions, and establishing clear implementation guidelines for varying operational scales, our findings provide valuable insights for both academic research and practical implementations. These implications extend beyond the immediate context of retail applications, offering broader perspectives on algorithm selection and implementation strategies for complex optimization problems.

4.4 Limitations and considerations

This study acknowledges several limitations that provide context for result interpretation and future research directions. The dataset characteristics present certain constraints, as our analysis is based on a specific set of 88 items distributed across 7 knapsacks, with fixed constraint ranges tailored to retail product bundling scenarios. While this dataset effectively represents typical retail bundling problems, it may not capture all possible real-world scenarios. The categorical distribution (45 beverages, 43 snacks) and value ranges (1.0-10.0 units for value coefficients, 0.11-1.0 kilograms for weights, 6,000-60,000 IDR for prices) provide comprehensive coverage for traditional retail scenarios but may require validation for extreme price points or highly specialized product categories, such as: seasonal variations in product availability, regional price fluctuations, dynamic inventory patterns, and extreme price point products.

Performance evaluation boundaries are defined by our experimental setup, including memory measurements conducted on specific hardware configurations, the use of single-node parallel processing architectures, and implementation-specific optimizations. These boundaries, while providing consistent comparative analysis, may influence the direct applicability of results to different hardware environments. The generalization of our findings is most relevant to retail product bundling scenarios, particularly those involving dual-constraint knapsack problems of similar scale and complexity. While our scalability analysis demonstrates consistent performance across different problem sizes (17-88 items) and our statistical validation shows solution stability (±0.013 TOPSIS score variation under 10% weight perturbation), the applicability to significantly larger retail operations (>1000 items) or different market segments may require additional validation.

4.5 Implementation performance and complexity analysis

Our comprehensive analysis of implementation performance reveals distinct patterns across algorithmic approaches. The theoretical complexity analysis demonstrates clear efficiency tiers: parallel variants achieve O(n×m×W×B)/p time complexity with processor count p, while maintaining O(3×m×W×B) space complexity through rolling optimization; metaheuristic approaches show O(population_size×n) time and O(population_size) space complexity; and resource-efficient methods like Greedy maintain O(n) time with O(1) space requirements. These theoretical bounds are validated by empirical results showing parallel variants achieving 80.47x-87.21x speedup over BDP, Numba demonstrating 240.14x improvement, and Branch & Bound exhibiting exceptional efficiency with 2334.53x speedup, while maintaining solution quality above 90% of optimal value across implementations.

Resource utilization patterns further support these findings, with price utilization ranging from 90.00% to 99.66% and weight utilization varying from 58.05% to 94.46%. Memory consumption remains well-controlled, particularly in resource-efficient implementations like Branch & Bound (118.09 MB) and GA (<150 MB), while parallel variants demonstrate predictable scaling with problem size. These empirical results, combined with consistent solution quality maintenance, validate our implementation strategies and provide robust criteria for deployment decisions across different operational scales, eliminating the need for extensive cross-platform testing while maintaining rigorous performance validation.

4.6 Future research opportunities

Looking forward, several promising research opportunities emerge from this work. In terms of algorithm enhancement, there is significant potential for developing hybrid approaches that combine the strengths of multiple algorithms, implementing dynamic parameter adaptation mechanisms for improved performance, and exploring advanced resource optimization strategies. The implementation domain could be expanded through investigation of distributed processing architectures, exploration of cloud-based deployment options, and development of real-time optimization capabilities. These future directions could significantly advance the practical application of MKP solutions in retail and beyond.