On the representativeness of approximate solutions of discrete optimization problems with interval cost function

01/01/2022

∙

by   Alexander Prolubnikov, et al.

∙

0

∙

share

We consider discrete optimization problems with interval uncertainty of cost function coefficients. The interval uncertainty models the measurements errors. A possible optimal solution is a solution that is optimal for some possible values of the coefficients. The probability of a possible solution is a probability of obtaining such coefficients that the solution is optimal. Similarly we define the notion of a possible approximate solution and its probability. We consider a possible solution unrepresentative if its probability less than some boundary value. The mean (optimal or approximate) solution is a solution that we obtain for mean values of interval coefficients. We show that the share of instances of a discrete optimization problem with unrepresentative mean approximate solution may be large enough for rather small values of errors.