A decision space algorithm for multiobjective convex quadratic integer optimization. (October 2021)

• Record Type: Journal Article
• Authors: De Santis, Marianna; Eichfelder, Gabriele
• Is Part Of: Computers & operations research. Volume 134(2021)
• Publication Date: 2021-10
• Subjects: 90C10 -- 90C25 -- 90C29 -- 90C57; Multiobjective optimization -- Convex quadratic optimization -- Integer quadratic programming -- Branch-and-bound algorithm; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2021.105396
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: We present a branch-and-bound algorithm for minimizing multiple convex quadratic objective functions over integer variables. Our method looks for efficient points by fixing subsets of variables to integer values and by using lower bounds in the form of hyperplanes in the image space derived from the continuous relaxations of the restricted objective functions. We show that the algorithm stops after finitely many fixings of variables with detecting both the full efficient and the nondominated set of multiobjective strictly convex quadratic integer problems. A major advantage of the approach is that the expensive calculations are done in a preprocessing phase so that the nodes in the branch-and-bound tree can be enumerated fast. We show numerical experiments on biobjective instances and on instances with three and four objectives. Highlights: We define a decision space algorithm for a class of multiobjective integer nonlinear programming problems We propose new theoretical results that can be used for further developments in the context of multiobjective quadratic integer optimization We examine the possibility of using more general lower bound sets with respect to the ideal point.