Induced optimal partition invariancy in linear optimization: constraints perturbation

Published in arXiv preprint arXiv:2008.02305, 2020


In this paper, we study uni-parametric linear optimization problems, in which simultaneously the right-hand-side and the left-hand-side of constraints are linearly perturbed with identical parameter. In addition to the concept of change point, the induced optimal partition is introduced, and its relation to the well-known optimal partition is investigated. Further, the concept of free variables in each invariancy intervals is described. A modified generalized computational method is provided with the capability of identifying the intervals for the parameter value where induced optimal partitions are invariant. The behavior of the optimal value function is described in its domain. Some concrete examples depict the results. We further implement the methodology on some test problems to observe its behavior on large scale problems.