Premium
A branch‐and‐bound algorithm for representative integer efficient solutions in multiple objective network programming problems
Author(s) -
Sun Minghe
Publication year - 2013
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21493
Subject(s) - integer programming , algorithm , integer (computer science) , branch and bound , mathematical optimization , mathematics , branch and price , set (abstract data type) , computer science , branch and cut , linear programming , flow network , tree (set theory) , mathematical analysis , programming language
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