Robust Linear Programming

Robust linear programming addresses linear programming problems where the data is uncertain, and a solution which remains feasible despite that uncertainty is sought. The robust counterpart to an LP is not an LP in general, but is always convex. The figure on the left illustrates the feasible set of the ‘‘robust counterpart’’ of an LP after we take into account uncertainty in the facets’ directions.

We focus on specific models of uncertainty that lead to tractable solutions, and describe a few applications of the method.

Outline

• Motivations and standard forms
• Tractable cases
• Applications
• Exercises