Technical Note—Exact Solutions of Inexact Linear Programs

Abstract

We address the problem of solving a linear program whose objective function coefficients are known only to lie in a given convex set. We seek a solution that is optimal against the worst possible realization of the objective function, i.e., a max-min solution. We present optimality criteria that characterize the desired solution and strengthen earlier results due to Soyster. The conditions are computationally implementable.