Connard, Peter (1992) Mixed integer programming on transputers. PhD thesis, University of Warwick.

Preview

PDF WRAP_Theses_Connard_1992.pdf - Unspecified Version - Requires a PDF viewer. Download (8Mb) | Preview

Request Changes to record.

Abstract

Mixed Integer Programming (MIP) problems occur in many industries and their practical solution can be challenging in terms of both time and effort. Although faster computer hardware has allowed the solution of more MIP problems in reasonable times, there will come a point when the hardware cannot be speeded up any more. One way of improving the solution times of MIP problems without further speeding up the hardware is to improve the effectiveness of the solution algorithm used.

The advent of accessible parallel processing technology and techniques provides the opportunity to exploit any parallelism within MIP solving algorithms in order to accelerate the solution of MIP problems. Many of the MIP problem solving algorithms in the literature contain a degree of exploitable parallelism. Several algorithms were considered as candidates for parallelisation within the constraints imposed by the currently available parallel hardware and techniques.

A parallel Branch and Bound algorithm was designed for and implemented on an array of transputers hosted by a PC. The parallel algorithm was designed to operate as a process farm, with a master passing work to various slave processors. A message-passing harness was developed to allow full control of the slaves and the work sent to them.

The effects of using various node selection techniques were studied and a default node selection strategy decided upon for the parallel algorithm. The parallel algorithm was also designed to take full advantage of the structure of MIP problems formulated using global entities such as general integers and special ordered sets. The presence of parallel processors makes practicable the idea of performing more than two branches on an unsatisfied global entity. Experiments were carried out using multiway branching strategies and a default branching strategy decided upon for appropriate types of MIP problem.

Item Type:	Thesis (PhD)
Subjects:	Q Science > QA Mathematics T Technology > T Technology (General) T Technology > TK Electrical engineering. Electronics Nuclear engineering
Library of Congress Subject Headings (LCSH):	Integer programming -- Research, Transputers, Computer algorithms
Official Date:	December 1992
Dates:	Date Event December 1992 Submitted
Institution:	University of Warwick
Theses Department:	School of Industrial and Business Studies
Thesis Type:	PhD
Publication Status:	Unpublished
Supervisor(s)/Advisor:	Ashford, Robert W.
Sponsors:	Science and Engineering Research Council (Great Britain) ; Dash Associates Limited
Extent:	xi, 291, [129] leaves : illustrations
Language:	eng

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads