Solving the Multi-objective 2-Dimensional Vector Packing Problem Using ϵ-constraint Method

Document Type

Book Chapter

Source of Publication

Advances in Intelligent Systems and Computing

Publication Date



In this paper, an exact method is designed to solve the multi-objective 2-dimensional vector packing problem. The algorithm is an adapted version of an efficient ϵ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon $$\end{document}-constraint method which proves its efficiency in solving a large variety of multi-objective optimization problems. This method is based on a clever decomposition of the initial problem into sub-problems which are iteratively solved through mathematical programming. To accelerate the search process, we propose a new integer programming model for solving the multi-objective 2-dimensional vector packing problem based on the compact model for the bin packing problem with fragile objects. Instead of scanning all possible solutions, we consider the solutions while solving a Subset-Sum Problem. Hence, non-useful subproblems are avoided and thus the search space is reduced. An experimental study is performed based instances from the literature. A comparison between the exact method and a grounded metaheuristic which provides good results in solving the multi-objective 2-dimensional vector packing problem.



First Page


Last Page



Computer Sciences