The Big-M method with the numerical infinite M
- PDF / 536,140 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 42 Downloads / 231 Views
The Big-M method with the numerical infinite M Marco Cococcioni1
· Lorenzo Fiaschi1
Received: 30 March 2020 / Accepted: 8 September 2020 © The Author(s) 2020
Abstract Linear programming is a very well known and deeply applied field of optimization theory. One of its most famous and used algorithms is the so called Simplex algorithm, independently proposed by Kantoroviˇc and Dantzig, between the end of the 30s and the end of the 40s. Even if extremely powerful, the Simplex algorithm suffers of one initialization issue: its starting point must be a feasible basic solution of the problem to solve. To overcome it, two approaches may be used: the two-phases method and the Big-M method, both presenting positive and negative aspects. In this work we aim to propose a non-Archimedean and non-parametric variant of the Big-M method, able to overcome the drawbacks of its classical counterpart (mainly, the difficulty in setting the right value for the constant M). We realized such extension by means of the novel computational methodology proposed by Sergeyev, known as Grossone Methodology. We have validated the new algorithm by testing it on three linear programming problems. Keywords Big-M method · Grossone methodology · Infinity computer · Linear programming · Non-Archimedean numerical computing
1 Introduction Linear Programming (LP) is a branch of optimization theory which studies the minimization (or maximization) of a linear objective function, subject to linear equality and/or linear inequality constraints. LP has found a lot of successful applications both in theoretical and real world contexts, especially in countless engineering applications. Most of the algorithms developed so far to solve LP problems fall in one of the two following categories: basis exchange methods [19] and interior point methods [27].
B
Lorenzo Fiaschi [email protected] Marco Cococcioni [email protected]
1
Department of Information Engineering, University of Pisa, Pisa, Italy
123
M. Cococcioni, L. Fiaschi
Researchers argued a lot about the pros and the cons of these approaches, ending up asserting the equal dignity of both. The best choice depends on the characteristics of the problem at hand [16]. Concerning this work, we decided to focus on the class of basis exchange methods and, in particular, on its probably most famous member: the Simplex algorithm, firstly proposed in 1939 by Kantoroviˇc [17] and independently rediscovered by Dantzig during the forties [8–10]. This algorithm needs a feasible basic solution to start from, an input which is not trivial to generate for complex real-world problems. The main ways to overcome this difficulty are: the two-phases approach [10] and the Big-M method [2,8,26]. The former splits the optimization in two-phases, and in each it runs the Simplex algorithm on a phase-specific problem. In the first one, the problem is a simple task for which a feasible starting point is known, and whose optimum is a valid basic solution for the original problem. The second one is the original p
Data Loading...
