Minimizing maximum regret for linear programs with interval objective function coefficients.

摘要

Empirical evidence suggests that the anticipation of regret resulting from a poor decision can influence the actions of decision makers. Many observed violations of expected utility theory can be explained by a desire to avoid frustration of this nature. The regret criterion is particularly relevant for decisions that are subject to ex post review, as is often the case in a business environment. When a decision problem is expressed in the form of a stochastic optimization model, aversion to regret motivates finding a solution that is robust, or close to optimal, regardless of how the future unfolds.; This thesis formulates mathematical programs and develops solution procedures for minimizing the maximum regret, both in an absolute and relative sense, for linear programs with interval objective function coefficients. Absolute regret is the difference between the outcome resulting from the chosen action and the best possible outcome (i.e., that which could have been achieved under perfect information) while relative regret expresses this difference on a percentage basis. We use an iterative approach that solves a linear program to find a candidate solution, and a mixed integer program to obtain a cost scenario that maximizes regret for the current candidate. The latter problem is of particular interest because of its computational complexity. By exploiting the structure of regret-maximizing solutions, we improve upon existing methods in terms of both the execution time and the size of problems that can be solved. Since the computational effort required to solve the mixed integer program becomes prohibitive as the number of uncertain costs increases, we also derive a heuristic approach that provides good solutions in such cases.