Combinatorial min-max-min-sum optimisation over a polytope

This paper studies a combinatorial optimisation problem in which the objective function is the sum of a linear (min-sum) part and a concave bottleneck (min-max) part, and the feasible region in a convex polytope. The optimisation problem has its global optimal solution (which may or may not be unique) at an extreme point of the feasible region. A criterion for ‘local’ optimal solution of the problem is obtained and it is shown that a ‘local’ optimal solution of this probem is either an optimal solution of a related linear programming problem or a ‘local’ optimal solution of a modified combinatorial problem. The proposed algorithm is convergent and involves solving a series of related linear programming problems. A simple numerical illustration is also provided.