On the Principle of Lagrange in Optimization Theory and Its Application in Transportation and Location Problems

In mathematical optimization, the Lagrangian approach is a general method to find an optimal solution of a finite (infinite) dimensional constrained continuous optimization problem. This method has been introduced by the Italian mathematician Joseph-Louis Lagrange in 1755 in a series of letters to Euler. This approach became known under the name The Principle of Lagrange and was also applied much later to integer optimization problems. The basic idea behind this method is to replace a constrained optimization problem by a sequence of easier solvable optimization problems having fewer constraints and penalizing the deletion of some of the original constraints by replacing the original objective function. To select the best penalization, the so-called Lagrangian dual function needs to be optimized and a possible algorithm to do so is given by the so-called subgradient method. This method is discussed in detail at the end of this chapter. The Lagrangian approach led to the introduction of dual optimization problems and penalization methods in nonlinear programming and recently to the development of interior point methods and the identification of polynomial solvable classes of continuous optimization problems. Also it had its impact on how to construct algorithms to generate approximate solutions of integer optimization problems. In this chapter, we discuss in the first part the main ideas behind this approach for any type of finite dimensional optimization problem. In the remaining parts of this chapter we focus in more detail on how this approach is used in continuous optimization problems and show its full impact on the so-called K-convex continuous optimization problems. Also we consider its application within linear integer programming problems and show how it is used to solve these type of problems. To illustrate its application to the well-known integer programming problems, we consider in the final section its application to some classical vehicle routing and location models. As such this chapter should be regarded as an introduction to duality theory and the Lagrangian approach for less mathematically oriented readers proving at the same time most of the results using the simplest possible proofs.