A branch and bound algorithm for solving a class of D-C programming
type: Item
instance of: scholarly article
title: A branch and bound algorithm for solving a class of D-C programming
zbMATH Open document ID: 1076.65055
author: H. Xue
author: Cheng-Xian Xu
published in: Applied Mathematics and Computation
publication date: 2005-06-13T00:00:00Z
review text: A special class of DC programming problems is considered where the objective function is the sum of a convex quadratic function, \(p(x)\), and a separable concave function, \(\varphi(x)= \varphi_1(x_1)+\cdots+ \varphi_n(x_n)\). The feasible domain is the intersection of a polytope and a box. The problem is converted into a quadratic convex problem by replacing the functions \(\varphi_j(x_j)\) by linear underestimates \(\psi_j(x_j)\), which depend on the subdomains generated by the branch and bound algorithm. Several bisection techniques are compared in numerical examples.
reviewed by: H. Ratschek
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C30
Mathematics Subject Classification ID: 90C57
Mathematics Subject Classification ID: 90C55
zbMATH DE Number: 2175490
zbMATH Keywords: DC programming
zbMATH Keywords: branch and bound algorithm
zbMATH Keywords: \(\omega\)-subdivision
zbMATH Keywords: largest distance bisection
zbMATH Keywords: normal rectangular subdivision
zbMATH Keywords: numerical examples
MaRDI profile type: Publication
full work available at URL: j.amc.2004.06.016
OpenAlex ID: W2059990420
cites work: An Algorithm for Separable Nonconvex Programming Problems
cites work: Portfolio optimization problem under concave transaction costs and minimal transaction unit constraints
cites work: Optimization on low rank nonconvex structures
cites work: Introduction to global optimization
cites work: Decomposition branch and bound method for globally solving linearly constrained indefinite quadratic minimization problems
cites work: Convex analysis and global optimization
cites work: Q4658641
DOI: 10.1016/J.AMC.2004.06.016
Recommended article: Q5128175
Recommended article: A branch-and-bound algorithm embedded with DCA for DC programming
Recommended article: A branch and bound algorithm for solving a class of nonlinear integer programming problems
Recommended article: Q4901802
Recommended article: A branch and bound algorithm for solving separable convex integer programming problems
Recommended article: A Branch and Bound Algorithm for the Bilevel Programming Problem
Recommended article: Q5860790
Recommended article: Solving a class of low rank d.c. programs via a branch and bound approach: a computational experience
Recommended article: A BRANCH-AND-BOUND ALGORITHM FOR FINDING ALL OPTIMAL SOLUTIONS OF THE ASSIGNMENT PROBLEM
Recommended article: Q4658641
description: scientific article; zbMATH DE number 2175490