A Branch-and-Bound Algorithm for Representative Integer Efficient Solutions in Multiple Objective Network Programming Problems

作者：Sun Minghe^*

来源：Networks, 2013, 62(1): 56-71.

DOI：10.1002/net.21493

• network flow algorithms
• multiple objective programming
• multiple criteria decision making
• integer programming
• branch-and-bound
• network flow problems with side constraints

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-8