A continuous approch for globally solving linearly constrained quadratic
- 1 January 2001
- journal article
- research article
- Published by Informa UK Limited in Optimization
- Vol. 50 (1), 93-120
- https://doi.org/10.1080/02331930108844555
Abstract
In a continuous approach we propose an efficient method for globally solving linearly constrained quadratic zero-one programming considered as a d.c. (difference of onvex functions) program. A combination of the d.c. optimization algorithm (DCA) which has a finite convergence, and the branch-and-bound scheme was studied. We use rectangular bisection in the branching procedure while the bounding one proceeded by applying d.c.algorithms from a current best feasible point (for the upper bound) and by minimizing a well tightened convex underestimation of the objective function on the current subdivided domain (for the lower bound). DCA generates a sequence of points in the vertex set of a new polytope containing the feasible domain of the problem being considered. Moreover if an iterate is integral then all following iterates are integral too.Our combined algorithm converges so quite often to an integer approximate solution.Finally, we present computational results of several test problems with up to 1800 variables which prove the efficiency of our method, in particular, for linear zero-one programmingKeywords
This publication has 29 references indexed in Scilit:
- A Branch and Bound Method via d.c. Optimization Algorithms and Ellipsoidal Technique for Box Constrained Nonconvex Quadratic ProblemsJournal of Global Optimization, 1998
- Solving a Class of Linearly Constrained Indefinite Quadratic Problems by D.C. AlgorithmsJournal of Global Optimization, 1997
- Numerical solution for optimization over the efficient set by d.c. optimization algorithmsOperations Research Letters, 1996
- Solving Multiple Knapsack Problems by Cutting PlanesSIAM Journal on Optimization, 1996
- A new algorithm for solving the general quadratic programming problemComputational Optimization and Applications, 1996
- On solving a D.C. programming problem by a sequence of linear programsJournal of Global Optimization, 1991
- Separable concave minimization via partial outer approximation and branch and boundOperations Research Letters, 1990
- An Algorithm for Global Minimization of Linearly Constrained Concave Quadratic FunctionsMathematics of Operations Research, 1987
- Une caractérisation complète des minima locaux en programmation quadratiqueNumerische Mathematik, 1980
- An Algorithm for Separable Nonconvex Programming ProblemsManagement Science, 1969