Déploiement et mise à jour de coupes de concavité

In the context of concave minimisation, a type of quadratic optimization problem, called BILD problem, can be reformulated into two symmetrical linear MinMax problems LMM. As there is a simple bijection between the optimal solution of BILD and their reformulations LMM, our research question is to take advantage of this reformulations for solving BILD. In the litterature, a computation technique , called concavity cut, proposed by Tuy [39] in 1964, has been shown to be useful solving the BILD problem. However, it is still unknown whether the nite convergence of a cutting planes algorithm can be enforced by the concavity cut itself or not. This is due to several problems, among which we mention : the degeneracy problem and the accumulation of cuts. Since then, researchers have attempted to improve the convergence of the cutting planes algorithm. To achieve this, they have integrated the algorithm with other computation techniques. Indeed, Konno [23] introduced in 1971 the mountain climbing (MC) technique to evaluate in each iteration a local optimal solution. In 1999, Marcus [34] used the pseudo-vertices to developed similar Tuy cuts by decomposing the polyhedral cone. Alarie and al. treated in 2001 the degeneracy problem ant they have exploited the "Branch and Bound" technique for solvign BILD instances with large dimensions. The proposed research in this project is the continuation of this works. Thus, we proposed two ways for deploying cuts. In the rst one, we dynamically update previously generated cuts after an improvement of the objective function value. In the second, instead rooting the cuts at vertices, we root them at pseudo-vertices. These two new strategies are tested numerically on a set of test problems issued from the literature as well as on a collection of randomly generated instances.

Résumé

Dans le cadre de minimisation concave, un type de problème d'optimisation quadratique, nommé bilinéaire disjoint (BILD), peut se reformuler en deux problèmes linéaires symétriques MinMax (LMM). Comme les solutions optimales de BILD et de ses reformulations LMM sont liées par une simple bijection, la question de notre travail de recherche s'agit profiter de cette reformulation pour résoudre BILD. Dans la littérature, une technique de calcul, appelée coupe de concavitée, proposée par Tuy [39] en 1964, s'avère importante afin de résoudre les BILD. L'algorithme basé uniquement sur cette technique n'est pas sûrement de convergence finie. Cela est dû à plusieurs problèmes, parmi lesquels nous citons : le problème de dégénérescene et le problème de cumul des coupes. Depuis, des chercheurs tentent d'améliorer la convergence de l'algorithme des plans coupants. Pour ce faire, ils ont intégré cet algorithme avec d'autres techniques de calcul. En effet, Konno [23] a introduit la technique Mountain Climbing en 1971 pour évaluer à chaque itération une solution locale. Avec l'usage des pseudo-sommets, Marcus [34] a developpé en 1999 des coupes similaires à celles de Tuy en décomposant le cône polyèdral. En 2001, Alarie et al. ont traité le problème de dégénérescence et ont exploité la technique de "Branch and Bound" pour les instances BILD de grande dimension. La recherche proposée dans ce mémoire se situe dans la continuation de ces travaux. Nous proposons deux nouvelles stratégies pour la génération de coupes de concavité. Dans la première, nous avons élaboré une mise à jour dynamique des coupes après qu'une améioration de la valeur objectif soit faite. Dans la seconde, au lieu que les coupes soient associées à des sommets, nous les avons associées aux pseudo-sommets. Ces deux nouvelles stratégies sont testées numériquement sur un ensemble de problèmes tests tirés de la littérature ainsi que sur une collection de problèmes générés aléatoirement.