Séminaire Yi-Shuai NIU

Jeudi 06 Décembre 2012 (14h00, salle G001)

Yi-Shuai NIU, CORIA, Rouen.

Titre : On Combination of DCA Branch-and-Bound and DC-Cut for Solving Mixed-01 Linear Program.

Résumé : We propose a new hybrid approach based on DC (Difference of convex functions) programming and DCA (DC algorithm) with combination of Branch-and-Bound (BB) framework and new local cutting plan technique (DC-Cut) for globally solving mixed-01 linear program.

We will firstly reformulate a mixed-integer linear program as a DC program via exact penalty technique, then an efficient local optimization algorithm DCA is proposed for searching upper bound solutions. The new DC-Cut technique can construct cutting plans from some integer and non-integer local minimizers of DC program which helps to reduce the feasible set and accelerate the convergence of BB. Preliminary numerical results comparing with some existing methods will be reported.