Let E be a finite set, and F be a family of subsets of E. For each element e ∈ E, p weights cie, i = 1, 2, . . . , p are prescribed. Then the minmax combinatorial optimization problem is to MinimizeS∈F Maximum1≤i≤pΣe∈S{cie}. Several special cases of this general problem, viz. 3-partition, makespan minimization problem, bandwidth minimization in matrices and graphs, categorized assignment problem, etc., have been studied in literature. In this paper we propose exact and heuristic methods to solve the general problem. Our algorithms also give some new insights into the application of subgradient optimization in solving the Lagrangean dual of combinatorial problems when the Lagrange multipliers are required to satisfy additional constraints. Encouraging computational results are also reported.
