Month: February 2023

The simplex method is the standard algorithm to solve LP problems and is based on the following observations: It is useful to visualize this process, by referring to Fig. 1.3. Imagine starting from a trivially feasible solution, the origin M0. We may improve this production plan by moving along the edges of the polyhedron; one possible path… Continue reading Simplex method

In this section we outline two standard solution methods: Both are widely available in commercial software packages, but even a cursory knowledge of their internal working may be a useful asset; nevertheless, readers may safely skip this section. We should also stress the fact that we are going to describe basic solution strategies, leaving aside… Continue reading A GLANCE AT SOLUTION METHODS

Lagrange multipliers play a major role in optimization theory, as well as in economics. Indeed, within the economic community, they are rather known as shadow prices,30 due to their important economical interpretation, which we illustrate in this section. Consider an equality-constrained problem and apply a small perturbation to the constraints: Let  be a vector collecting these perturbations. Solving… Continue reading An economic interpretation of Lagrange multipliers: shadow prices

Consider the following problem, featuring only inequality constraints: In order to characterize a (locally) optimal solution, we may follow the same reasoning as in the equality-constrained case; if x* is a locally optimal solution, then we cannot find a feasible descent direction at x*. A fundamental observation is that an inequality constraint can be either active at x*, gk(x*) =… Continue reading Dealing with inequality constraints: Karush–Kuhn–Tucker conditions

For the sake of simplicity, we start by considering the equality constrained case: which can be dealt with by the classical Lagrange multiplier method. THEOREM 12.10 Assume that the functions f and hj in problem (12.60) meet some differentiability requirements, that the point x* is feasible, and that the constraints satisfy a suitable regularity property in x*. Then, a necessary condition for local optimality of x* is… Continue reading The case of equality constraints Lagrange multipliers

In this section and the next one, we consider the solution of a mathematical programming problem. We will do so essentially for linear programs, continuous and mixed-integer ones, but it is also important to get a feeling for more general, theoretical concepts in nonlinear programming. We will not cover nonlinear programming methods, but we will… Continue reading NONLINEAR PROGRAMMING CONCEPTS

Sometimes, there are nonlinear relationships between variables, which cannot be disregarded, as forcing the problem into a linear framework would result in a blatantly inadequate model. For instance, we may have to do with economies or diseconomies of scale: One possibility would be to resort to nonlinear programming solvers to cope with a nonlinear formulation.… Continue reading Piecewise linear functions

The portfolio optimization model that we have considered in Example 12.5 does not place any restriction on the composition of the portfolio. In practice, bounds are enforced, e.g., to limit exposure to certain risk factors; for instance, we might wish to limit exposure to emerging markets or to the energy sector. Another practical issue that is worth… Continue reading An optimization model for portfolio tracking and compression

In the network optimization models of Section 12.2.4, we have taken the network structure as given. Hence, the decisions we had to make were tactical or operational, and just linked to flow routing. However, at a more strategic level, we have to make decisions concerning: As far as the last point is concerned, we have considered… Continue reading Plant location

A classical example involving fixed charges is the lot-sizing model, which is essentially a generalization of the basic EOQ model to take into account multiple items, limited production capacity, and time-varying demand. To see why such a model arises, note that in the multiperiod planning models (12.26) and (12.27) we did not consider at all… Continue reading Lot-sizing with setup times and costs