Exact and Heuristic Algorithms for the q-mode Problem

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

Kulkarni, Girish ; Stephen Roberts, Committee Member,Shu-Cherng Fang, Committee Member,Carla Savage, Committee Member,Yahya Fathi, Committee Chair,Kulkarni, Girish ; Stephen Roberts ; Committee Member ; Shu-Cherng Fang ; Committee Member ; Carla Savage ; Committee Member ; Yahya Fathi ; Committee Chair

University:North Carolina State University

关键词: clustering categorical data;    combinatorial optimisation;    mixed integer programming;    neighborhood search;    very large scale neighborhood;   

Others  :  https://repository.lib.ncsu.edu/bitstream/handle/1840.16/3416/etd.pdf?sequence=1&isAllowed=y

美国|英语

来源: null

【 摘 要 】

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.