Multiobjective Multidimensional Knapsack Optimization Algorithms

This repository contains an undergraduate algorithms project completed at the University of Toronto in Winter 2023 focused on solving the multi-objective, multidimensional 0-1 knapsack problem.

The project implements and evaluates multiple exact and heuristic search strategies for enumerating Pareto-optimal (nondominated) solutions, along with theoretical complexity analysis and empirical runtime benchmarking in Python.

---

Problem Setting

The multi-objective knapsack problem selects a subset of items to maximize several competing objectives subject to multiple capacity constraints.

Unlike the classical single-objective knapsack, the solution is a set of Pareto-optimal points forming a nondominated frontier rather than a single optimum.

---

Algorithms Implemented

Three core solution methods are implemented and compared:

• Brute-Force Enumeration

  • Exhaustively enumerates feasible solutions
  • Computes objective vectors and filters dominated points
  • Includes an improved variant that incrementally prunes dominated solutions

• Rectangle Division Method

  • Lexicographic optimization over recursively subdivided regions of objective space
  • Includes performance improvements based on region height and pruning logic

• Supernal Method

  • Weighted-sum approach for multi-objective optimization
  • Supports more than two objectives
  • Includes enhanced region selection and adaptive weighting strategies

---

Experimental Evaluation

Random problem instances were generated by varying:

• Number of items
• Number of constraints
• Number of objectives

The algorithms were benchmarked on runtime and scalability.

Key findings:

• Brute-force methods scale exponentially and become infeasible quickly
• Rectangle Division and Supernal methods are significantly faster in practice
• The Supernal method performs best for problems with more than two objectives
• Algorithmic refinements substantially reduce runtime even when worst-case complexity is unchanged

Detailed plots and analysis are included in the accompanying PDF report.

---

Repository Contents

• SolveKnapsackAlgorithms.py — Python implementations of all algorithms and improvements
• Input Files/ — Randomly generated test instances
• MMKP_Report.pdf — Full technical report with pseudocode, proofs, and experimental results
• README.md — Project overview

---

Techniques Demonstrated

• Multi-objective optimization
• Pareto frontier enumeration
• Integer programming formulations
• Algorithm design and pseudocode
• Runtime complexity analysis
• Empirical benchmarking
• Heuristic improvement strategies

---

Academic Context

Completed as part of an undergraduate optimization and algorithms course at the University of Toronto.