A Branch and Bound Algorithm for Precedence Constrained Knapsack Problem

スポンサーリンク

概要

• 論文の詳細を見る

• The 0-1 knapsack problem is one of the classic and fundamental problem in integer programming. In this study, we consider a constrained version of the problem called a precedence constrained knapsack problem. First, the problem is formulated as a 0-1 integer programming problem and its several applications are mentioned. Next, we proposed an algorithm solving a Lagrangean relaxation problelm to obtain an upper bound of the problem. Finally, a branch and bound algorithm for solving the precedence constrained knapsack problem is developed, and its effectiveness is discussed through some computational experiments.

• 東海大学の論文

著者

• Moriyama Hiroumi

  Department Of Management Engineering

• HADA Takeo

  Department of Management Engineering

関連論文

• Approximate Solutions for Assembly Process Formation Problem in Aggregative Production System
• A Planning Method of Optical Fiber Cable Routing Based on Integer Programming(ABSTRACTS OF PROCEEDINGS OF THE SCHOOL OF INFORMATION TECHNOLOGY AND ELECTRONICS SERIES J TOKAI UNIVERSITY -2003-2004-)
• A Near-Optimal Solution for the Vehicle Routing Problem with Multiple Use of Vehicles(Production and Logistics)
• Approximate Algorithm For Group Technology Line Formation Problem(ABSTRACTS OF PROCEEDINGS OF THE SCHOOL OF INFORMATION TECHNOLOGY AND ELECTRONICS SERIES J TOKAI UNIVERSITY -2003-2004-)
• A Branch and Bound Algorithm for Precedence Constrained Knapsack Problem

スポンサーリンク