Author: haroonkhan
-
Expected value of perfect information
Decision trees are a very simple tool for framing decision problems with a discrete set of alternatives and a discrete representation of uncertainty. We may start moving to more complicated cases by expressing a decision problem under risk in a more general way: It is important to understand what problem (13.1) represents: This is a here-and-now decision,…
-
DECISION TREES
Decision trees are a natural way to describe decision problems under risk, involving a sequence of decisions among a finite set of alternative options and a set of discrete scenarios, modeling uncertain outcomes that follow our decisions. Actually, we have already dealt with decision trees informally in earlier examples.1 Now we should treat this formalism more…
-
Introduction
This represents a synthesis of what we have become acquainted with so far. Decision making under uncertainty is a quite challenging topic, merging probability theory and statistics with optimization modeling. This mix may result in quite demanding mathematics, which we will avoid by focusing on fundamental concepts and a few illustrative toy examples to clarify…
-
The impact of model formulation
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…
-
LP-based branch and bound method
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…
-
Simplex 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…
-
A GLANCE AT SOLUTION METHODS
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…
-
An economic interpretation of Lagrange multipliers: shadow prices
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…
-
Dealing with inequality constraints: Karush–Kuhn–Tucker conditions
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*) =…
-
The case of equality constraints Lagrange multipliers
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…