Title: k-Set frameworks in multi-criteria combinatorial optimisation

Authors: Mark Sh. Levin

Addresses: Institute for Information Transmission Problems, Russian Academy of Sciences, 19 Bolshoj Karenty Lane, Moscow 127994, Russia

Abstract: This paper addresses frameworks for structuring/formulation and solving of complex discrete decision-making problems. Multi-criteria combinatorial optimisation problems based on k sets of elements (k = 1, 2, 3, 4) are examined. Firstly, for each set of elements, a multi-attribute description of elements and/or binary relation over elements is considered. Further, a combinatorial optimisation problem over a set of elements is analysed (e.g. ranking, selection, knapsack problem, ordering/scheduling, clustering, spanning trees and design of a hierarchy over elements). Secondly, binary relation over elements of two different sets can be considered (k > 1). As a result, combinatorial optimisation problems are examined, e.g. matching, assignment and allocation. Finally, generalised k-set frameworks for problem formulation are described for some application decision-making domains, e.g. |clustering-multiple choice problem|, |clustering-assignment|, |ranking-allocation|, |assignment-multiple choice problem|, |clustering-assignment-multiple choice problem|, |clustering-clique| (multi-partite clique) and |clustering-assignment-scheduling|. The generalised problem formulation frameworks are used at various stages of system life cycle and in many domains: system design, system improvement, system testing, system maintenance, marketing, information retrieval, multi-target assignment, multi-processor scheduling, timetabling, etc. The suggested k-set frameworks were for education.

Keywords: application domain structuring; multicriteria decision making; MCDM; combinatorial optimisation; problem structuring; problem solving; k-set frameworks; education.

DOI: 10.1504/IJTPM.2011.040303

International Journal of Technology, Policy and Management, 2011 Vol.11 No.1, pp.85 - 95

Published online: 31 Mar 2015 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article