Multi-criteria branch and bound: A vector maximization algorithm for Mixed 0-1 Multiple Objective Linear Programming

摘要

The paper describes the Multi-Criteria Branch and Bound (MCBB) algorithm, a vector maximization algorithm capable of deriving all efficient extreme points, for small- and medium-sized Mixed 0-1 Multiple Objective Linear Programming (Mixed 0-1 MOLP). Particular emphasis is given to computational aspects aiming principally at accelerating the solution procedure. For facilitating the decision maker’s search toward the most preferred efficient solution, the notion of efficient combinations of the binary variables is further exploited. It is also shown that the MCBB algorithm can be used in single objective problems (Mixed Integer LP problems) in order to determine all alternative optima, as well as in Mixed Integer MOLP problems and Pure 0-1 MOLP problems that frequently arise in practice. A computational experiment is included in the paper in order to illustrate the performance of the algorithm.