Linear bilevel programming with interval coefficients (Q432810)

Bilevel programming involves two optimization problems with the upper and lower level objective functions \(f_1\) and \(f_2\), respectively, and where the constraint region of one of the problems is implicitly determined by the other. This paper treats linear bilevel problems with interval coefficients in both objective functions and whose objective coefficients are assumed to lie between specific bounds, i.e., \(f_1\) and \(f_2\) are linear functions with interval coefficients and the common constraint region is polyhedron. The aim of this paper is to solve the optimal value range problem which consists of computing the best and worst optimal objective function values and determining the settings of the interval coefficients which provide these values. It is shown that these two optimal solutions occur at extreme points of the polyhedron defined by the common constraints. Although the term linear is used in the description of these bilevel problems, the fact that the feasible region is implicitly determined by another mathematical program makes them nonlinear problems thus more difficult to solve. It is proved by examples that, in general, there is no precise way of systematizing the specific values of the interval coefficients that can be used to compute the best and worst possible optimal solutions. Two algorithms based on ranking extreme points are developed to solve the optimal value range problem for bilevel problems with interval coefficients in both the upper and lower objective functions.