An algorithm for approximate multiparametric linear programming (Q1431701)

This paper is devoted to linear programming problems with the right hand side being an affine function of a parameter vector. The problem considered is the approximation of the optimal value function and of an optimizer for every value of the parameter. Two versions of an algorithm for solving this problem are proposed. The algorithm starts with a full dimensional simplex such that a finite optimizer is known for every linear problem associated to the vertices of the simplex. The linear interpolation of the optimizer as a function of the parameters is then proposed as an approximation of the optima for every parameter vector in the simplex. The algorithm then calculates a lower and an upper bound for the absolute error in the optimal value function and stops if certain tolerance is greater than the upper bound. Otherwise it refines the bounds until they coincide or divide the simplex into two or more full-dimensional simplices and use the same idea recursively. Each evaluation of the bounds involves the solution of an auxiliary linear program. Both version of the algorithm presented are independent of the LP solver used for the auxiliary problems. Complexity results for both algorithms and a global error bound on the optimizer are given. Finally numerical results are discussed.