Back to search

Georgia Institute of Technology

Coupled Oscillator Based Potts Machine to Solve Combinatorial Optimization Problems

Abstract

dc:description.abstract

Combinatorial Optimization Problems (COP) represent a class of NP-Hard problems with diverse practical applications. These problems involve the partitioning of sets into discrete subsets while adhering to specific constraints. Among COPs, the max-3-cut problem stands out, presenting a scenario where a set is partitioned into three subsets with the objective of maximizing inter-set edge connections. Traditional approaches to address max-3-cut problems often resort to algorithms based on heuristic methods, simulated annealing, etc. to be run on conventional computers. However, these methods are plagued by extended computation times and substantial energy consumption. In response, physics-based solutions have been extensively explored, particularly Ising machines, which leverage Ising models. Although Ising machines offer notable energy and time savings, their hardware requirements introduce significant performance overheads when applied to max-3-cut problems. A more direct and energy-efficient alternative involves leveraging a hardware solver based on the Potts model. This research introduces a novel architecture for a coupled oscillator-based Potts machine (OPM) tailored to tackle max-3-cut problems. It also outlines the considerable advantages of employing an OPM over an oscillator Ising machine (OIM) for max-3-cut problem resolution. Finally, the study conducts a comparative analysis between the OPM and a state-of-the-art heuristic algorithm (MOH) for solving max-3-cut problems on large Gset networks, revealing a {10}^7x reduction in runtime while maintaining solution quality above 90%.

Degree

thesis:*
Level thesis:degree_level
Masters
Department dc:contributor.department
Electrical and Computer Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Babu, Nithin
Advisor dc:contributor.advisor
  • Datta, Suman
Committee members dc:contributor.committeemember
  • Mukhopadhyay, Saibal
  • Khan, Asif Islam

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/77748

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Babu, Nithin. Coupled Oscillator Based Potts Machine to Solve Combinatorial Optimization Problems. Masters thesis, Georgia Institute of Technology, 2024. https://hdl.handle.net/1853/77748