Robust optimization for non-linear impact of data variation. (November 2018)

• Record Type: Journal Article
• Authors: Alfandari, Laurent; Espinoza García, Juan-Carlos
• Is Part Of: Computers & operations research. Volume 99(2018)
• Page Start: 38
• Page End: 47
• Publication Date: 2018-11
• Subjects: Linear programming -- Non-linear programming -- Robust optimization -- Duality -- Uncertainty; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2018.06.011
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: We study generic Linear Programs where coefficients are non linear functions of uncertain data. We approximate the worst-case subproblem using piece-wise linear functions. We show the relaxed subproblem has the integrality property which enables dualization. We test the robust approach on Capital Budgeting, Knapsack and Generalized Assignment instances. The results show the robust solution is 100% (>99%) feasible with 5 (2) pieces, and often infeasible with 1 piece. Abstract: We extend the Γ-robustness approach proposed by Bertsimas and Sim for Linear Programs to the case of non-linear impact of parameter variation. The seminal work considered protection from infeasibility over the worst-case variation of coefficients in a constraint, this variation being controlled by an uncertainty budget called Γ. When coefficients are non-linear functions of a parameter subject to uncertainty, we study a piecewise linear approximation of the function, and show that the subproblem of determining the worst-case variation can still be dualized despite the discrete structure of the piecewise linear function. We conduct numerical experiments on three different problems: Capital Budgeting, Generalized Assignment and Knapsack problems to analyze the trade-off between feasibility and objective value for the robust solution of the piecewise linear approximation compared to the nominal solution, and to a simpler binary approximation. Despite the piecewise approximation, the robust solution reveals to remain feasible over the 6800 runs performed in our experiments, with an average deterioration of the objective value of only a few percents.