Branch-and-bound Algorithm (branch-and-bound + algorithm)

Distribution by Scientific Domains
Mathematics and Statistics75%

Selected Abstracts

Using an interval branch-and-bound algorithm in the Hartree,Fock method

INTERNATIONAL JOURNAL OF QUANTUM CHEMISTRY, Issue 5 2005
Carlile C. Lavor
Abstract The Hartree,Fock (HF) method is widely used to obtain atomic and molecular electronic wave functions, based on the minimization of a functional of the energy. We propose to use a deterministic global optimization algorithm, based on a branch-and-bound method, that applies techniques of interval arithmetic. This algorithm is applied directly to the minimization of the energy expression derived from the HF method. The proposed approach was successfully applied to the ground state of He and Be atoms. © 2005 Wiley Periodicals, Inc. Int J Quantum Chem, 2005 [source]

Path optimization for the resource-constrained searcher,

NAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 5 2010
Hiroyuki Sato
Abstract We formulate and solve a discrete-time path-optimization problem where a single searcher, operating in a discretized three-dimensional airspace, looks for a moving target in a finite set of cells. The searcher is constrained by maximum limits on the consumption of one or more resources such as time, fuel, and risk along any path. We develop a specialized branch-and-bound algorithm for this problem that uses several network reduction procedures as well as a new bounding technique based on Lagrangian relaxation and network expansion. The resulting algorithm outperforms a state-of-the-art algorithm for solving time-constrained problems and also is the first algorithm to solve multi-constrained problems. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010 [source]

Minimizing weighted earliness and tardiness penalties in single-machine scheduling with idle time permitted

NAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 8 2002
Jaw-Yeh Chen
Abstract In this paper, a single-machine scheduling problem with weighted earliness and tardiness penalties is considered. Idle time between two adjacent jobs is permitted and due dates of jobs could be unequal. The dominance rules are utilized to develop a relationship matrix, which allows a branch-and-bound algorithm to eliminate a high percentage of infeasible solutions. After combining this matrix with a branching strategy, a procedure to solve the problem is proposed. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 760,780, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10039 [source]

Solving the minimum-weighted coloring problem

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 2 2001
Massimiliano Caramia
Abstract Weighted coloring is a generalization of the well-known vertex (unweighted) coloring for which a number of exact algorithms have been presented in the literature. We are not aware of any optimal method specifically designed for the minimum-weighted coloring problem on arbitrary graphs. Only a few heuristics have been developed with the goal of finding tighter upper bounds for the maximum-weighted clique problem. Moreover, as shown in the paper, a straightforward reduction of a weighted instance into an unweighted one permits us to solve only very small instances. In this paper, we present a branch-and-bound algorithm for the weighted case capable of solving random graphs of up to 90 vertices for any edge density with integer weights uniformly drawn from the range [1, ,,10]. Likewise, we have used properly modified benchmark instances borrowed from vertex coloring as a further test bed for our algorithm. © 2001 John Wiley & Sons, Inc. [source]