An Iterative Approach for Finding Minimal-Optimal Solutions of the Min-Max Programming Problem with Addition-Overlap Functions

Finding an optimal solution of the min-max programming problem with addition-overlap function constraints has been studied in the literature. Since the definition of overlap functions is very general and has no explicit formulations, a bisection method was proposed to yield a uniform-optimal solution for such optimization problems with a general overlap function involved in its constraint part. The uniform-optimal solution could be improved if the system manager wants extra properties such as also yielding lower cost performance. The minimal-optimal solution is proposed other than the uniform-optimal solution to answer manager’s call. In this paper, we propose an iterative method to yield at least one minimal-optimal solution. Our method starts from the uniform-optimal solution and systematically reduces the values of some non-binding variables while preserving the feasibility and optimality. To rigorously establish our method, we specify explicitly a nontrivial “min-shifted” overlap function in place of the general overlap function of the min-max programming problem. The proof of finding a minimal-optimal solution of our algorithm is given. By shifting the searching sequence of decision variables, our algorithm may find other minimal-optimal solutions which provide more flexibility for the system manager to choose. Numerical examples are provided to illustrate the procedures of the algorithm.