logo_acta

Acta Mathematica Vietnamica

A NEW BOUNDING TECHNIQUE IN BRANCH-AND-BOUND ALGORITHMS FOR MIXED INTEGER PROGRAMMING

TRAN VU THIEU, TRAN XUAN SINH

Abstract

A branch-and-bound algorithm using a new bounding technique is presented for solving the mixed integer problem. The technique
involves considering a piecewise linear and concave function of a parameter $\lambda\in\mathbb R^1$ whose maximum gives the largest lower bound. A parametric method is developed for finding the maximum of a such function.