An exact solution method for unconstrained quadratic 0–1 programming: a geometric approach

An exact solution method for unconstrained quadratic 0–1 programming: a geometric approach

0.00 Avg rating0 Votes
Article ID: iaor20123063
Volume: 52
Issue: 4
Start Page Number: 797
End Page Number: 829
Publication Date: Apr 2012
Journal: Journal of Global Optimization
Authors: , ,
Keywords: programming: geometric, programming: branch and bound
Abstract:

We explore in this paper certain rich geometric properties hidden behind quadratic 0–1 programming. Especially, we derive new lower bounding methods and variable fixation techniques for quadratic 0–1 optimization problems by investigating geometric features of the ellipse contour of a (perturbed) convex quadratic function. These findings further lead to some new optimality conditions for quadratic 0–1 programming. Integrating these novel solution schemes into a proposed solution algorithm of a branch‐and‐bound type, we obtain promising preliminary computational results.

Reviews

Required fields are marked *. Your email address will not be published.