ON COMBINED MINMAX-MINSUM OPTIMIZATION

In this paper we present a modification of Minoux's algorithm for solving the combined minmax-minsum combinatorial optimization problem (MMCOP) in view of improving its average performance. Computational results are presented which establish the superiority of the modified algorithm over the existing algorithms. We then study the relationship between the optimal solutions of MMCOP and an associated minsum problem in the context of matroids. Further, we introduce combined minmax-minsum linear programming problem (MMLP). MMLP can be transformed into a linear program with additional constraints and variables. We present an efficient simplex based algorithm to solve MMLP which treats these additional constraints implicitly. Our computational results show that the proposed algorithm performs better than the simplex method used directly on a linear program equivalent to MMLP.