On estimating workload in branch-and-bound global optimization algorithms

J.L. Berenguel, L.G. Casado, I. Garcia, E.M.T. Hendrix

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)

Abstract

In general, solving Global Optimization (GO) problems by Branch-and-Bound (B&B) requires a huge computational capacity. Parallel execution is used to speed up the computing time. As in this type of algorithms, the foreseen computational workload (number of nodes in the B&B tree) changes dynamically during the execution, the load balancing and the decision on additional processors is complicated. We use the term left-over to represent the number of nodes that still have to be evaluated at a certain moment during execution. In this work, we study new methods to estimate the left-over value based on the observed amount of pruning. This provides information about the remaining running time of the algorithm and the required computational resources. We focus on their use for interval B&B GO algorithms.
Original languageEnglish
Pages (from-to)821-844
JournalJournal of Global Optimization
Volume56
Issue number3
DOIs
Publication statusPublished - 2013

Fingerprint

Branch-and-bound
Global optimization
Global Optimization
Workload
Optimization Algorithm
B-tree
Vertex of a graph
Pruning
Load Balancing
Resource allocation
Speedup
Optimization Problem
Moment
Resources
Interval
Computing
Term
Estimate
Node

Keywords

  • implementation
  • selection
  • programs

Cite this

Berenguel, J.L. ; Casado, L.G. ; Garcia, I. ; Hendrix, E.M.T. / On estimating workload in branch-and-bound global optimization algorithms. In: Journal of Global Optimization. 2013 ; Vol. 56, No. 3. pp. 821-844.
@article{5da2cc3296f44dd4ad447e78486b28fe,
title = "On estimating workload in branch-and-bound global optimization algorithms",
abstract = "In general, solving Global Optimization (GO) problems by Branch-and-Bound (B&B) requires a huge computational capacity. Parallel execution is used to speed up the computing time. As in this type of algorithms, the foreseen computational workload (number of nodes in the B&B tree) changes dynamically during the execution, the load balancing and the decision on additional processors is complicated. We use the term left-over to represent the number of nodes that still have to be evaluated at a certain moment during execution. In this work, we study new methods to estimate the left-over value based on the observed amount of pruning. This provides information about the remaining running time of the algorithm and the required computational resources. We focus on their use for interval B&B GO algorithms.",
keywords = "implementation, selection, programs",
author = "J.L. Berenguel and L.G. Casado and I. Garcia and E.M.T. Hendrix",
year = "2013",
doi = "10.1007/s10898-011-9771-5",
language = "English",
volume = "56",
pages = "821--844",
journal = "Journal of Global Optimization",
issn = "0925-5001",
publisher = "Springer Verlag",
number = "3",

}

On estimating workload in branch-and-bound global optimization algorithms. / Berenguel, J.L.; Casado, L.G.; Garcia, I.; Hendrix, E.M.T.

In: Journal of Global Optimization, Vol. 56, No. 3, 2013, p. 821-844.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - On estimating workload in branch-and-bound global optimization algorithms

AU - Berenguel, J.L.

AU - Casado, L.G.

AU - Garcia, I.

AU - Hendrix, E.M.T.

PY - 2013

Y1 - 2013

N2 - In general, solving Global Optimization (GO) problems by Branch-and-Bound (B&B) requires a huge computational capacity. Parallel execution is used to speed up the computing time. As in this type of algorithms, the foreseen computational workload (number of nodes in the B&B tree) changes dynamically during the execution, the load balancing and the decision on additional processors is complicated. We use the term left-over to represent the number of nodes that still have to be evaluated at a certain moment during execution. In this work, we study new methods to estimate the left-over value based on the observed amount of pruning. This provides information about the remaining running time of the algorithm and the required computational resources. We focus on their use for interval B&B GO algorithms.

AB - In general, solving Global Optimization (GO) problems by Branch-and-Bound (B&B) requires a huge computational capacity. Parallel execution is used to speed up the computing time. As in this type of algorithms, the foreseen computational workload (number of nodes in the B&B tree) changes dynamically during the execution, the load balancing and the decision on additional processors is complicated. We use the term left-over to represent the number of nodes that still have to be evaluated at a certain moment during execution. In this work, we study new methods to estimate the left-over value based on the observed amount of pruning. This provides information about the remaining running time of the algorithm and the required computational resources. We focus on their use for interval B&B GO algorithms.

KW - implementation

KW - selection

KW - programs

U2 - 10.1007/s10898-011-9771-5

DO - 10.1007/s10898-011-9771-5

M3 - Article

VL - 56

SP - 821

EP - 844

JO - Journal of Global Optimization

JF - Journal of Global Optimization

SN - 0925-5001

IS - 3

ER -