New ϵ−constraint methods for multi-objective integer linear programming: A Pareto front representation approach

Dealing with multi-objective problems by using generation methods has some interesting advantages since it provides the decision-maker with the complete information about the set of non-dominated criterion vectors (Pareto front) and a clear overview of the different trade-offs of the problem. However, providing many solutions to the decision-maker may also be overwhelming. As an alternative approach, showing a representative set of the Pareto front may be advantageous. Choosing such a representative set is by itself also a multi-objective problem that must consider the number of alternatives to present, the uniformity, and/or the coverage of the representation, to guarantee its quality. This paper proposes three algorithms for the representation problem for multi-objective integer linear programming problems with two or more objective functions, each one of them dealing with each dimension of the problem (cardinality, coverage, and uniformity). Such algorithms are all based on the ϵ-constraint approach. In addition, the paper also presents strategies to overcome poor estimations of the Pareto front bounds. The algorithms were tested on the ability to efficiently generate the whole Pareto front or a representation of it. The uniformity and cardinality algorithms proved to be very efficient both on binary and on integer problems, being amongst the best in the literature. Both coverage and uniformity algorithms provide good quality representations on their targeted objective, while the cardinality algorithm appears to be the most flexible, privileging uniformity for lower cardinality representations and coverage on higher cardinality.