Robust optimality analysis for linear programming problems with uncertain objective function coefficients: an outer approximation approach

@article{Gao2023,
abstract = {Linear programming (LP) problems with uncertain objective function coefficients (OFCs) are treated in this paper. In such problems, the decision-maker would be interested in an optimal solution that has robustness against uncertainty. A solution optimal for all conceivable OFCs can be considered a robust optimal solution. Then we investigate an efficient method for checking whether a given non-degenerate basic feasible (NBF) solution is optimal for all OFC vectors in a specified range. When the specified range of the OFC vectors is a hyper-box, i. e., the marginal range of each OFC is given by an interval, it has been shown that the tolerance approach can efficiently solve the robust optimality test problem of an NBF solution. However, the hyper-box case is a particular case where the marginal ranges of some OFCs are the same no matter what values the remaining OFCs take. In real life, we come across cases where some OFCs' marginal ranges depend on the remaining OFCs' values. For example, the prices of products rise together in tandem with raw materials, the gross profit of exported products increases while that of imported products decreases because they depend on the currency exchange rates, and so on. Considering those dependencies, we consider a case where the range of the OFC vector is specified by a convex polytope. In this case, the tolerance approach to the robust optimality test problem of an NBF solution becomes in vain. To treat the problem, we propose an algorithm based on the outer approximation approach. By numerical experiments, we demonstrate how the proposed algorithm efficiently solves the robust optimality test problems of NBF solutions compared to a conventional vertex-listing method.},
author = {Gao, Zhenzhong, Inuiguchi, Masahiro},
journal = {Kybernetika},
keywords = {linear programming problems; interactive uncertain coefficients; robust optimality analysis; outer approximation approach; convex polytope},
language = {eng},
number = {1},
pages = {64-87},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Robust optimality analysis for linear programming problems with uncertain objective function coefficients: an outer approximation approach},
url = {http://eudml.org/doc/299085},
volume = {59},
year = {2023},
}

TY - JOUR
AU - Gao, Zhenzhong
AU - Inuiguchi, Masahiro
TI - Robust optimality analysis for linear programming problems with uncertain objective function coefficients: an outer approximation approach
JO - Kybernetika
PY - 2023
PB - Institute of Information Theory and Automation AS CR
VL - 59
IS - 1
SP - 64
EP - 87
AB - Linear programming (LP) problems with uncertain objective function coefficients (OFCs) are treated in this paper. In such problems, the decision-maker would be interested in an optimal solution that has robustness against uncertainty. A solution optimal for all conceivable OFCs can be considered a robust optimal solution. Then we investigate an efficient method for checking whether a given non-degenerate basic feasible (NBF) solution is optimal for all OFC vectors in a specified range. When the specified range of the OFC vectors is a hyper-box, i. e., the marginal range of each OFC is given by an interval, it has been shown that the tolerance approach can efficiently solve the robust optimality test problem of an NBF solution. However, the hyper-box case is a particular case where the marginal ranges of some OFCs are the same no matter what values the remaining OFCs take. In real life, we come across cases where some OFCs' marginal ranges depend on the remaining OFCs' values. For example, the prices of products rise together in tandem with raw materials, the gross profit of exported products increases while that of imported products decreases because they depend on the currency exchange rates, and so on. Considering those dependencies, we consider a case where the range of the OFC vector is specified by a convex polytope. In this case, the tolerance approach to the robust optimality test problem of an NBF solution becomes in vain. To treat the problem, we propose an algorithm based on the outer approximation approach. By numerical experiments, we demonstrate how the proposed algorithm efficiently solves the robust optimality test problems of NBF solutions compared to a conventional vertex-listing method.
LA - eng
KW - linear programming problems; interactive uncertain coefficients; robust optimality analysis; outer approximation approach; convex polytope
UR - http://eudml.org/doc/299085
ER -