logo_acta

Acta Mathematica Vietnamica

A NEW DECOMPOSITION ALGORITHM FOR GLOBALLY SOLVING MATHEMATICAL PROGRAMS WITH AFFINE EQUILIBRIUM CONSTRAINTS

L. D. MUU, Q. TRAN DINH, L. T. H. AN, P. D. TAO

Abstract

This paper proposes a new decomposition method for globally solving mathematical programming problems with affine equilibrium constraints (AMPEC). First, we view AMPEC as a bilevel programming problem where the lower level problem is a parametric affine variational inequality. Then we use a regularization technique to formulate the resulting problem as a mathematical program with an additional constraint defined by the difference of two convex functions (DC function). A main feature of this DC decomposition is that the second component depends upon only the parameter in the lower level problem. This property allows us to develop branch-and-bound algorithms for globally solving AMPEC where the adaptive rectangular bisection takes place only in the space of the parameters. As an example, we use the proposed algorithm to solve a bilevel Nash-Cournot equilibrium market model. Computational results show the efficiency of the proposed algorithm.