On combined minmax-minsum optimization

This paper presents 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. The relationship between the optimal solutions of MMCOP and an associated minsum problem is then studied in the context of matroids. Further, the combined minmax-minsum linear programming probem (MMLP) is introduced. MMLP can be transformed into a linear program with additional constraints and variables. The paper presents an efficient simplex based algorithm to solve MMLP which treats these additional constraints implicitly. The present computational results show that the proposed algorithm performs better than the simplex method used directly on a linear program equivalent to MMLP.