Title page for ETD etd-05122005-171458

Type of Document

Dissertation

Author

Kulkarni, Girish ,

URN

etd-05122005-171458

Title

Exact and Heuristic Algorithms for the q-mode Problem

Degree

PhD

Graduate Program

Operations Research

Advisory Committee

Advisor Name	Title
Yahya Fathi	Committee Chair
Carla Savage	Committee Member
Shu-Cherng Fang	Committee Member
Stephen Roberts	Committee Member

Keywords

clustering categorical data
combinatorial optimisation
mixed integer programming
neighborhood search
very large scale neighborhood

Date of Defense

2005-05-06

Availability

unrestricted

Abstract

In this dissertation we focus on the development of exact and inexact (i.e., heuristic) algorithms for the q-mode problem. The exact algorithms are based on integer programming models for the q-mode problem. We discuss the theoretical properties of an existing IP model and propose several enhancements. We also propose a new IP model for the problem and investigate these models through a comprehensive computational experiment. The experiment reveals that, in practice, the IP models are more effective for instances with strong natural clusters but less effective for instances containing weak natural clusters. We also propose exact algorithms based on the Benders decomposition for one of the IP models.

The heuristic algorithm that we propose for the q-mode problem is a local improvement algorithm that is based on a very large scale neighborhood structure. We evaluate the algorithm through a computational experiment and empirically demonstrate its effectiveness.

Files

Filename		Size	Approximate Download Time (Hours:Minutes:Seconds)
Filename		Size	28.8 Modem	56K Modem	ISDN (64 Kb)	ISDN (128 Kb)	Higher-speed Access
	etd.pdf	1.42 Mb	00:06:35	00:03:23	00:02:57	00:01:28	00:00:07