Category: Deterministic Decision Models

The idea that most decision makers are risk-averse is intuitively clear, but what does risk aversion really mean? A theoretical answer, commonly put forward in economic theory, can be found by assuming that decision makers order uncertain outcomes by a utility function rather than by straightforward expected monetary values. To introduce the concept, let us consider simple… Continue reading A conceptual tool: the utility function

We have seen that commercial branch and bound procedures compute bounds by LP-based (continuous) relaxations. Given a MILP problem where S denotes its feasible set, the continuous relaxation is obtained by relaxing the integrality constraints, which yields the relaxed feasible set  and the relaxed problem: If we could find the convex hull of S, which is a polyhedron, the… Continue reading The impact of model formulation

When dealing with a MILP, the simplex method cannot guarantee an integer solution; more often than not, we obtain a fractional solution. There is an even more troubling fact, which is essentially due to the lack of convexity. In fact, if some magical oracle hands over the optimal solution of a continuous LP, we know… Continue reading LP-based branch and bound method

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