INSTITUTE OF INFORMATION TECHNOLOGIES - BAS

Cybernetics and Information Technologies
Volume 4, No 2. Sofia, 2004, Bulgarian Academy of Sciences


A Partition-Based Interactive Algorithm for Solving Multicriteria Linear Integer Programming Problems

Vassil Vassilev1 , Subhash Narula2 , Mariyana Vassileva2 , Krassimira Genova2

1 Institute of Information Technologies, 1113 Sofia
2 School of Business, Virginia Commonwealth University, Richmond, USA


Abstract: We propose a learning-oriented interactive algorithm for solving multicriteria linear integer programming (MCLIP) problems, considered as multicriteria decision making problems. At each iteration, the DM may partition the criteria set into at most seven classes, namely: improvement, improvement by a desired amount, deterioration, deterioration by at most a certain amount, non-deterioration, changes allowed within limits, and free changes. Based on the partition of the criteria set, two types of scalarizing problems are formulated - linear and mixed integer programming problems. One or more (weak) nondominated solutions of the continuous relaxation of MCLIP problem are computed at most of the iterations. A mixed-integer scalarizing problem is solved, only at some iterations, in order to find one or more (weak) nondominated or near (weak) nondominated solutions (close to the nondominated surface of the MCLIP problem). At some iteration, when the DM wants to see more than one solution, he/she may select the preferred solution based on nonformalized information about his/her preferences or may use a ranking procedure based on additional formal information. Based on the proposed algorithm, we have developed a research decision support system.

Keywords: decision support system; multicriteria decision making; ranking procedure; scalarizing problem.