Solving the quadratic 0-1 problem

Schutz, G.; Pires, F. M.; Ruano, Antonio

http://hdl.handle.net/10400.1/2148

Use this identifier to reference this record.

Name:	Description:	Size:	Format:
36.pdf		95.92 KB	Adobe PDF	Download

Send Feedback

Authors

Schutz, G.

Pires, F. M.

Ruano, Antonio

Abstract(s)

The quadratic 0-1 programming is a discrete optimization problem, with many important applications. Difficult graph problems can be formulated and solved as a quadratic 0-1 programming problem. This is a NP-hard combinatorial problem very difficult to solve, even if the dimension is small. The branch-and-bound algorithms are the most used for solving exactly this sort of problems. In this paper, based on an efficient sequential branch-and-bound algorithm for the unconstrained quadratic 0-1 programming, we study the behaviour of its parallel implementation using transputers and present some computational results. We also analyse the workload distribution among processors.

Keywords

Quadratic 0-1 programming Branch and Bound Algorithms Parallel Numerical Algorithms

URI

http://hdl.handle.net/10400.1/2148

Citation

Schutz, G.; Pires, F. M.; Ruano, A. E. Solving the Quadratic 0-1 Problem, Trabalho apresentado em 4th Int. Meeting on Vector and Parallel Processing (VecPar’2000), In 4th Int. Meeting on Vector and Parallel Processing (VecPar’2000), Porto, 2000.