CUHK electronic theses & dissertations collection

In part I of this dissertation, certain rich geometric properties hidden behind quadratic 0-1 programming are investigated. 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.In part II of this dissertation, we present new results of the duality gap between the binary quadratic optimization problem and its Lagrangian dual. We first derive a necessary and sufficient condition for the zero duality gap and discuss its relationship with the polynomial solvability of the problem. We then characterize the zeroness of duality gap by the distance, delta, between the binary set and certain affine space C. Finally, we discuss a computational procedure of the distance delta. These results provide new insights into the duality gap and polynomial solvability of binary quadratic optimization problems.The unconstraint quadratic binary problem (UBQP), as a classical combinatorial problem, finds wide applications in broad field and human activities including engineering, science, finance, etc. The NP-hardness of the combinatorial problems makes a great challenge to solve the ( UBQP). The main purpose of this research is to develop high performance solution method for solving (UBQP) via the geometric properties of the objective ellipse contour and the optimal solution. This research makes several contributions to advance the state-of-the-art of geometric approach of (UBQP). These contributions include both theoretical and numerical aspects as stated below.Liu, Chunli.Adviser: Duan Li.Source: Dissertation Abstracts International, Volume: 70-06, Section: B, page: 3764.Thesis (Ph.D.)--Chinese University of Hong Kong, 2008.Includes bibliographical references (leaves 140-153).Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web.Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web.Abstracts in English and Chinese.School code: 1307