Research Repository

The quadratic balanced optimization problem

Punnen, Abraham P and Taghipour, Sara and Karapetyan, Daniel and Bhattacharyya, Bishnu (2014) 'The quadratic balanced optimization problem.' Discrete Optimization, 12. 47 - 60. ISSN 1572-5286

1-s2.0-S1572528614000024-main.pdf - Published Version

Download (548kB) | Preview


We introduce the quadratic balanced optimization problem (QBOP) which can be used to model equitable distribution of resources with pairwise interaction. QBOP is strongly NP-hard even if the family of feasible solutions has a very simple structure. Several general purpose exact and heuristic algorithms are presented. Results of extensive computational experiments are reported using randomly generated quadratic knapsack problems as the test bed. These results illustrate the efficacy of our exact and heuristic algorithms. We also show that when the cost matrix is specially structured, QBOP can be solved as a sequence of linear balanced optimization problems. As a consequence, we have several polynomially solvable cases of QBOP.

Item Type: Article
Uncontrolled Keywords: Combinatorial optimization Balanced optimization Knapsack problem Bottleneck problems Heuristics
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science and Health > Computer Science and Electronic Engineering, School of
Depositing User: Elements
Date Deposited: 24 May 2018 10:44
Last Modified: 24 May 2018 11:15

Actions (login required)

View Item View Item