Multi-Objective Integer Programming Problems

Abstract

The present thesis aims to develop algorithms for solving various multi-objective integer programming problems that arise in multi-criteria decision-making situations. The thesis consists of seven chapters, each addressing different aspects of the multi-objective integer programming problem. Chapter 1 is introductory, which provides an overview of multi-objective integer program- ming problems. An extensive literature survey related to multi-objective integer program- ming problems is conducted in this section. Further, the motivation for optimizing a function over the efficient set of multi-objective integer programming problem is discussed in this chapter. A brief summary of the thesis is also presented in this chapter. In Chapter 2, a method for solving the bi-objective integer linear programming problem is discussed. The main focus of this chapter is to effectively implement the ε-constraint technique to produce a complete set of non-dominated points. The convergence of the algorithm has been established theoretically. Further, a comparative study of some existing algorithms has also been made. In Chapter 3, an algorithm for finding all efficient solutions to a multi-objective integer quadratic programming problem is presented. The proposed algorithm is based on the aspect that efficient solutions of a multi-objective integer quadratic programming problem can be obtained by enumerating ranked solutions of an integer quadratic programming problem. For determining ranked solutions of an integer quadratic programming problem, we have constructed a related integer linear programming problem. Theoretically, we have shown that the developed method generates the set of all efficient solutions in a finite number of steps. Numerically, we have elaborated the working of our algorithm and compared our results with existing algorithms. Further, we have analyzed that the developed method is efficient for solving a multi-objective integer quadratic programming problem with a large number of constraints, variables and objectives. In Chapter 4, we have discussed that a simplex like algorithm to solve an indefinite quadratic fractional programming problem proposed in [102] fails to find its optimal solu- tion and so it may not generate the actual set of efficient solutions of the corresponding multi-objective integer indefinite quadratic fractional programs. A counter example in sup- port of this argument is also given. Further, a novel method for solving a multi-objective integer quadratic fractional programming problem is also discussed. To tackle this problem, we have utilized a linear fractional function (or linear function), which provides a lower bound to one of the objective functions of the multi-objective integer quadratic fractional programming problem. In the developed method, we have used successive optimization of integer linear fractional programming problem (or integer linear programming problem) for finding efficient solutions. Theoretically, we have shown that the proposed method gen- erates the complete set of all efficient solutions in finite iterations. Numerical examples are also included in this chapter to elaborate working of the proposed algorithm. Further, we have compared the proposed method with existing methods using numerical examples. We have also incorporated computational results to analyze the performance of the developed algorithm for many variables, constraints, and objectives. In Chapter 5, we have proposed two algorithms for optimizing a linear function over the efficient set. The optimization of a function over the efficient set is an interesting approach in decision-making situations. It helps a decision-maker to discriminate among efficient solutions and choose his preferred solution. In the first algorithm, ranked solutions of an integer linear programming problem are utilized for optimizing a linear function over the efficient set of a multi-objective integer linear programming problem. For enumerating ranked solutions of an integer linear programming problem, successive optimization of an integer linear programming problem is used. The second algorithm follow a two way procedure. From one side it finds ranked solution and from the other side efficient solutions are generated and a lower bound is calculated. This lower bound keeps on shrinking at each stage and provides an estimate on the number of ranked solutions to be calculated. The algorithm stops after calculating ranked solutions upto this lower bound. Theoretically, we have shown that the proposed algorithms optimize a linear function over the efficient set of a multi-objective integer linear programming problem in a finite number of iterations. Further, we have compared the working of proposed algorithms with existing algorithms using numerical examples taken from the literature. We have also included a comparison with existing methods based on computational experiments using large number of variables and objectives. In Chapter 6, a novel approach to optimize a general quadratic function over the efficient set of a multi-objective integer linear programming problem is presented. The proposed algorithm obtains a globally optimal solution by systematically scanning ranked solutions of an integer quadratic programming problem until the efficiency condition is satisfied. The associated quadratic programming problem is solved by approximating its solutions from a related integer linear programming problem. The convergence of our algorithm is established theoretically. Numerical examples and computational results are also included in the chapter to elaborate on the working of the developed algorithm. In Chapter 7, we have proposed a scheme for solving an integer quadratic fractional programming problem over the efficient set of a multi-objective integer linear programming problem without computing all the elements of the efficient set. The proposed methodol- ogy combines a criteria space search algorithm, a ranking approach, and efficiency tests to solve the problem efficiently within a finite number of iterations. The algorithm iteratively optimizes an integer quadratic fractional programming problem by utilizing ranked solu- tions from a related integer linear fractional programming problem (or linear programming problem). The integration of a criteria space search algorithm, a ranking approach, and efficiency tests avoids the enumeration of all ranked solutions of the integer quadratic frac- tional programming problem and all efficient solutions of the multi-objective integer linear programming problem, which reduces the computational complexity. Theoretical analysis establishes the convergence of the proposed algorithm, while numerical and computational experiments validate its effectiveness.