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

In many applications of multiple objective network programming 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 algorithm is developed to find integer efficient solutions. The purpose of the branch-and-bound 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 branch-and-bound algorithm and performed on the spanning tree, is developed to construct feasible solutions from infeasible solutions and basic solutions from nonbasic solutions when bounds on branching variables change. The branch-and-bound algorithm finds either supported or 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 algorithm is very powerful.