Multiobjective quadratic programs (MOQPs) are appealing since convex quadratic programs have elegant mathematical properties and model important applications. Adding mixed-integer variables extends their applicability while the resulting programs become global optimization problems.
We design and implement a branch and bound (BB) algorithm for biobjective mixed-integer quadratic programs (BOMIQPs). In contrast to the existing algorithms in which the Pareto set is approximated, the proposed algorithm provides the exact Pareto set in closed form. The algorithm relies on three fundamental modules of the BB scheme: solving node problems, branching, and fathoming; and a newly developed module of set dominance. Continuous relaxations of the BOMIQP are solved at the BB nodes with the mpLCP method that provides exact efficient solutions to MOQPs.
The branching module is extended to be applicable to BOMIQPs and is integrated with the mpLCP method. Selected fathoming rules are implemented in a new way to account for the properties of the Pareto set of the BOMIQP. In the module of set dominance, Pareto sets are compared under incomplete information to yield the resulting nondominated set and eventually produce the Pareto set of the BOMIQP.
Numerical results are provided.
Article
View A Branch and Bound Algorithm for Biobjective Mixed Integer Quadratic Programs