Heuristic algorithms for solving a class of multiobjective zero-one programming problems

Abstract

This thesis is devoted to the design and development of heuristics for solving multiobjective zero-one integer linear programming problems. We present some useful concepts and propose some heuristic methods for finding the epsilon-nondominated solutions. The proposed method decomposes a multiobjective zero-one programming problem into a series of single objective problems. Efficient LP-based heuristics, which capitalize on the similarity between the optimal solution of a zero-one programming problem and that of its corresponding LP problem, are employed to solve these single objective problems. In particular, the proposed methods are applied to two classes of problems, i.e. the multiobjective zero-one knapsack problem and the multiobjective generalized assignment problem. Extensive computational experiments have demonstrated that the methods we proposed are very effective and efficient for solving these classes of problems. These methods can also be extended to other multiobjective zero-one programming problems, especially the other members from the family of the knapsack problems.