The mixed-integer bilinear programming problem with extensions to zero-one quadratic programs

This research effort is concerned with a class of mathematical programming problems referred to as Mixed-Integer Bilinear Programming Problems. This class of problems, which arises in production, location-allocation, and distribution-application contexts, may be considered as a discrete version of the well-known Bilinear Programming Problem in that one set of decision variables is restricted to be binary valued. The structure of this problem is studied, and special cases wherein it is readily solvable are identified. For the more general case, a new linearization technique is introduced and demonstrated to lead to a tighter linear programming relaxation than obtained through available linearization methods. Based on this linearization, a composite Lagrangian relaxation-implicit enumeration-cutting plane algorithm is developed. Extensive computational experience is provided to test the efficiency of various algorithmic strategies and the effects of problem data on the computational effort of the proposed algorithm. The solution strategy developed for the Mixed-Integer Bilinear Programming Problem may be applied, with suitable modifications,. to other classes of mathematical programming problems: in particular, to the Zero-One Quadratic Programming Problem. In what may be considered as an extension to the work performed on the Mixed-Integer Bilinear Programming Problem, a solution strategy based on an equivalent linear reformulation is developed for the Zero-One Quadratic Programming Problem. The strategy is essentially an implicit enumeration algorithm which employs Lagrangian relaxation, Benders' cutting planes, and local explorations. Computational experience for this problem class is provided to justify the worth of the proposed linear reformulation and algorithm.

Name thesis:degree_name

Ph. D.

Level thesis:degree_level

doctoral

Discipline thesis:degree_discipline

Industrial Engineering and Operations Research

Department dc:contributor.department

Industrial Engineering and Operations Research

Grantor dc:publisher

Virginia Polytechnic Institute and State University

Year dc:date.issued

1985

Author dc:creator

• Adams, Warren Philip

Chair dc:contributor.committeechair

• Sherali, Hanif

Committee members dc:contributor.committeemember

• Frair, Lester C.
• Ghandforoush, F.
• Moore, L.J.
• Nachlas, Joel A.

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Language dc:language.iso

en_US

Handle dc:identifier.uri

http://hdl.handle.net/10919/74711

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/74711