The quadratic balanced optimization problem

DOI10.1016/J.DISOPT.2014.01.001zbMATH Open1308.90152arXiv1212.4211OpenAlexW1999004550MaRDI QIDQ2339810FDOQ2339810

Bishnu Bhattacharyya, Sara Taghipour, Abraham P. Punnen, Daniel Karapetyan

Publication date: 9 April 2015

Published in: Discrete Optimization (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1212.4211

zbMATH Keywords

heuristicscombinatorial optimizationknapsack problembottleneck problemsbalanced optimization

Mathematics Subject Classification ID

Quadratic programming (90C20) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Bottleneck extrema
• Quadratic bottleneck problems
• A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms
• Efficient algorithms for minimum range cut problems
• Minimizing maximum absolute lateness and range of lateness under generalized due dates on a single machine
• Independent Sets of Maximum Weight in Apple-Free Graphs
• Balanced paths in acyclic networks: Tractable cases and related approaches
• The minimum spanning tree problem with conflict constraints and its variations
• Paths, trees and matchings under disjunctive constraints
• On finding most uniform spanning trees
• Minimum dispersion problems
• Lexicographic balanced optimization problems
• On generalized balanced optimization problems
• Balanced optimization problems
• Maximum weight independent sets in hole- and co-chair-free graphs
• On combined minmax-minsum optimization
• Minimum deviation and balanced optimization: A unified approach
• Minimum cost-reliability ratio path problem
• Most and least uniform spanning trees
• Minimization of maximum absolute deviation in integers
• An \(\varepsilon\)-approximation scheme for combinatorial optimization problems with minimum variance criterion
• The balanced linear programming problem
• A strongly polynomial algorithm for the uniform balanced network flow problem
• Constrained balanced optimization problems
• An Algorithm for Minimizing the Range of Lateness on a Single Machine
• Minimizing the Range of Lateness on a Single Machine
• Minimum Range Balanced Cuts via Dynamic Subset Sums
• Balanced problems on graphs with categorization of edges
• An algorithm to determine a path with minimal cost/capacity ratio
• The balanced traveling salesman problem
• Quadratic bottleneck knapsack problems
• Improved Bounds for the Range of Lateness on a Single Machine
• Paths with minimum range and ratio of arc lengths
• Minimizing The Range Of Lateness On A Single Machine Under Generalized Due Dates

Cited In (7)

• Effective metaheuristic algorithms for the minimum differential dispersion problem
• Title not available (Why is that?)
• Tabu search guided by reinforcement learning for the max-mean dispersion problem
• Constrained balanced optimization problems
• A hybrid metaheuristic of integrating estimation of distribution algorithm with Tabu search for the max-mean dispersion problem
• Balanced optimization problems
• The quadratic Gaussian CEO problem

This page was built for publication: The quadratic balanced optimization problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2339810)