.png){kind=icon}
.png){kind=icon}
Return
Solving the Lexicographic Multi-Objective Mixed-Integer Linear Programming Problem using branch-and-bound and grossone methodology
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cnsns.2020.105177.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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. (C) 2020 Elsevier B.V. All rights reserved.
Keywords:
Multi-objective optimization
Lexicographic optimization
Mixed-integer linear programming
Numerical infinitesimals
Grossone methodology
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
3.8
Papers:
9.2K
Citations:
1.8W