Groupe d’études et de recherche en analyse des décisions

G-96-15

On the Linear Maxmin and Related Programming Problems

, , et

The maxmin problem models a game sequentially played by two players having opposite objective. Before making his move, the first player must anticipate the reaction of his opponent. The linear maxmin problem can either be seen as a particular instance of the linear bilevel programming problem, or as an equivalent reformulation of the disjoint bilinear programming problem. Links between these and other problems are presented. The linear mixed 0-1 programming problem can be reformulated as a linear bilevel problem and vice-versa. Moreover, the similarity between these problems is deeper. Beale and Small's (1965) algorithm for mixed 0-1 programming is embedded into Hansen, Jaumard and Savard's (1992) algorithm for bilevel programming, i.e., when applied to any mixed 0-1 instance and its bilevel reformulation, both algorithms generate sequences of subproblems which are identical through the reformulation. The linear maxmin problem is a concave optimization problem. Moreover, to any linear maxmin problem, one may associate another linear maxmin problem which is obtained through the equivalent bilinear reformulation. Concavity cuts can be obtained for both reformulations. We show how to exploit these symmetrical maxmin reformulations in order to obtain a finitely convergent branch and bound algorithm. Numerical results and an application to bimatrix games are presented.

, 31 pages