(186c) GoNDEF: A New Exact Method to Generate All Non-Dominated Points of Multi-Objective Mixed-Integer Linear Programs

Most real-life decision problems involve more than a single criterion that are often conflicting with each other. This category of problems are called multi-criteria/multi-objective optimization problems (MCOP/MOOP). One of the most important tasks for MOOPs is finding the non-dominated (ND) points in the objective space or efficient solutions in the decision space. A ND point results in objective function values that cannot be improved without worsening another objective function. In this paper, we present a novel method to generate the set of entire ND points for a multi-objective mixed-integer linear program (MOMILP). The Generator of ND and Efficient Frontier for MOMILPs (GoNDEF) finds the ND points represented as points, line segments, and facets consisting of all types of the ND points. First, GoNDEF finds integer values for integer variables that generate the ND points. Then, our method fixes integer variables to specific values. The resulting problem is a multi-objective linear program (MOLP). This MOLP has its own set of ND points. A subset of this set establishes a subset of the ND points set of the MOMILP. We present an extensive theoretical analysis of the GoNDEF and illustrate its effectiveness on a set of instance problems.