A branch‐and‐bound algorithm for representative integer efficient solutions in multiple objective network programming problems. Issue 1 (7th January 2013)

• Record Type: Journal Article
• Authors: Sun, Minghe
• Is Part Of: Networks. Volume 62:Issue 1(2013:Aug.)
• Page Start: 56
• Page End: 71
• Publication Date: 2013-01-07
• Subjects: Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21493
• Languages: English
• ISSNs: 0028-3045

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>In many applications of multiple objective network programming (MONP) problems, only integer solutions are acceptable as the final optimal solution. Representative efficient solutions are usually obtained by sampling the efficient set through the solution of augmented weighted Tchebycheff network programs. Because such efficient solutions are usually not integer solutions, a branch‐and‐bound (BB) algorithm is developed to find integer efficient solutions. The purpose of the BB algorithm is to support interactive procedures by generating representative integer efficient solutions. To be computationally efficient, the algorithm takes advantage of the network structure as much as possible. An algorithm, used in the BB algorithm and performed on the key tree, is developed to construct feasible solutions from infeasible solutions and basic solutions from nonbasic solutions when bounds on branching variables change. The BB algorithm finds basic and nonbasic or supported and unsupported integer efficient solutions as long as they are optimal. Details of the algorithm are presented, an example is provided and computational results are reported. Computational results show that the BB algorithm performs well. Although the BB algorithm is developed for the purpose of generating integer efficient solutions for MONP problems, it can also solve more general integer network flow problems with linear side constraints. © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2013</p> </abstract>