Résumé de séminaire

Résumé :

Given a set of the form P = {(x,y) : Ax+By <= d }, we address the question of finding a description for the convex hull of the mixed-integer set Z^MIP = {(x,y) in P, y integer } associated with P.

Given a mixed-integer set Z^MIP, the approach that we use here to compute a formulation for conv(Z^MIP) is as follows. We study the sets V_Z^MIP, R_Z^MIP of vertices and extreme rays of conv(Z^MIP). We then find a small number of subsets V ⁱ of conv(Z^MIP) and R ⁱ of R_Z^MIP whose union contains V_Z^MIP and R_Z^MIP respectively. For each of the pairs (V ⁱ,R ⁱ) we compute a formulation for conv(V ⁱ)+cone(R ⁱ). The last step is to derive a formulation for the convex hull of the union of these polyhedra. For this we use a classical result of Balas.