Solving the Lexicographic Multi-Objective Mixed-Integer Linear Programming Problem using branch-and-bound and grossone methodology

Abstract In the previous work (see [1]) the authors have shown how to solve a Lexicographic Multi-Objective Linear Programming (LMOLP) problem using the Grossone methodology described in [2]. That algorithm, called GrossSimplex, was a generalization of the well-known simplex algorithm, able to deal numerically with infinitesimal/infinite quantities. The aim of this work is to provide an algorithm able to solve a similar problem, with the addition of the constraint that some of the decision variables have to be integer. We have called this problem LMOMILP (Lexicographic Multi-Objective Mixed-Integer Linear Programming). This new problem is solved by introducing the GrossBB algorithm, which is a generalization of the Branch-and-Bound (BB) algorithm. The new method is able to deal with lower-bound and upper-bound estimates which involve infinite and infinitesimal numbers (namely, Grossone-based numbers). After providing theoretical conditions for its correctness, it is shown how the new method can be coupled with the GrossSimplex algorithm described in [1], to solve the original LMOMILP problem. To illustrate how the proposed algorithm finds the optimal solution, a series of LMOMILP benchmarks having a known solution is introduced. In particular, it is shown that the GrossBB combined with the GrossSimplex is able solve the proposed LMOMILP test problems with up to 200 objectives.