RELAXATION-BASED ALGORITHMS FOR MINIMAX OPTIMIZATION PROBLEMS WITH RESOURCE-ALLOCATION APPLICATIONS

We consider minimax optimization problems where each term in the objec tive function is a continuous, strictly decreasing function of a singl e variable and the constraints are linear. We develop relaxation-based algorithms to solve such problems. At each iteration, a relaxed minim ax problem is solved, providing either an optimal solution or a better lower bound. We develop a general methodology for such relaxation sch emes for the minimax optimization problem. The feasibility tests and f ormulation of subsequent relaxed problems can be done by using Phase I of the Simplex method and the Farkas multipliers provided by the fina l Simplex tableau when the corresponding problem is infeasible. Such r elaxation-based algorithms are particularly attractive when the minima x optimization problem exhibits additional structure. We explore speci al structures for which the relaxed problem is formulated as a minimax problem with knapsack type constraints; efficient algorithms exist to solve such problems. The relaxation schemes are also adapted to solve certain resource allocation problems with substitutable resources. Th ere, instead of Phase I of the Simplex method, a max-flow algorithm is used to test feasibility and formulate new relaxed problems.