Back to search

University of British Columbia

On methods for the maximization of a zero-one quadratic function

Abstract

dc:description

The research addresses the problem of maximizing a zero-one quadratic function. The report falls into three main sections. The first section uses results from Hammer [12] and Picard and Ratliff [23] to develop a new test for fixing the value of a variable in some solution and to provide a means for calculating a new upper bound on the maximum of the function. In addition the convergence of the method of calculation for the bounds is explored in an investigation of its sharpness. The second section proposes a branch and bound algorithm that uses the ideas of the first along with a heuristic solution procedure. It is shown that one advantage of this is that it may now be possible to identify how successful this algorithm will be in finding the maximum of a specified problem. The third section gives a basis for a new heuristic solution procedure. The method defines a concept of gradient which enables a simple steepest ascent technique to be used. It is shown that in general this will find a local maximum of the function. A further procedure to help distinguish between local and global maxima is also given.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Business Administration
Grantor dc:publisher
University of British Columbia
Year dc:date
1978

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Hawkins, Stephen Peter

Rights

dc:rights
Statement dc:rights
  • For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/20745

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Hawkins, Stephen Peter. On methods for the maximization of a zero-one quadratic function. master's thesis, University of British Columbia, 1978. http://hdl.handle.net/2429/20745