Branch and Bound Algorithm for Multiprocessor Scheduling
Rahman, Mostafizur
2009-01-01
The multiprocessor task graph scheduling problem has been extensively studied asacademic optimization problem which occurs in optimizing the execution time of parallelalgorithm with parallel computer. The problem is already being known as one of the NPhardproblems. There are many good approaches made with many optimizing algorithmto find out the optimum solution for this problem with less computational time. One ofthem is branch and bound algorithm.In this paper, we propose a branch and bound...
An ellipsoidal branch and bound algorithm for global optimization
Hager, William; Phan, Dzung
2009-01-01
A branch and bound algorithm is developed for global optimization. Branching in the algorithm is accomplished by subdividing the feasible set using ellipses. Lower bounds are obtained by replacing the concave part of the objective function by an affine underestimate. A ball approximation algorithm, obtained by generalizing of a scheme of Lin and Han, is used to solve the convex relaxation of the original problem. The ball approximation algorithm is compared to SEDUMI as well as to gradient pr...
Towards a taxonomy of parallel branch and bound algorithms
Trienekens, H.W.J.M.; Bruin, Arie
1992-01-01
textabstractIn this paper we present a classification of parallel branch and bound algorithms, and elaborate on the consequences of particular parameter settings. The taxonomy is based upon how the algorithms handle the knowledge about the problem instance to be solved, generated during execution. The starting point of the taxonomy is the generally accepted description of the sequential branch and bound algorithm, as presented in, for example, [Mitten 1970] and [Ibaraki 1976a, 1976b, 1977a, 1...
Kodiak: An Implementation Framework for Branch and Bound Algorithms
Smith, Andrew P.; Munoz, Cesar A.; Narkawicz, Anthony J.; Markevicius, Mantas
2015-01-01
Recursive branch and bound algorithms are often used to refine and isolate solutions to several classes of global optimization problems. A rigorous computation framework for the solution of systems of equations and inequalities involving nonlinear real arithmetic over hyper-rectangular variable and parameter domains is presented. It is derived from a generic branch and bound algorithm that has been formally verified, and utilizes self-validating enclosure methods, namely interval arithmetic and, for polynomials and rational functions, Bernstein expansion. Since bounds computed by these enclosure methods are sound, this approach may be used reliably in software verification tools. Advantage is taken of the partial derivatives of the constraint functions involved in the system, firstly to reduce the branching factor by the use of bisection heuristics and secondly to permit the computation of bifurcation sets for systems of ordinary differential equations. The associated software development, Kodiak, is presented, along with examples of three different branch and bound problem types it implements.
Initialization of parallel branch-and-bound algorithms
Henrich, Dominik
1993-01-01
Four different initialization methods for parallel Branch-and-bound algorithms are described and compared with reference to several criteria. A formal analysis of their idle times and efficiency follows. It indicates that the efficiency of three methods depends on the branching factor of the search tree. Furthermore, the fourth method offers the best efficiency of the overall algorithm when a centralized OPEN set is used. Experimental results by a PRAM simulation support these statements.
A Simplicial Branch and Bound Duality-Bounds Algorithm to Linear Multiplicative Programming
Xue-Gang Zhou; Bing-Yuan Cao
2013-01-01
A simplicial branch and bound duality-bounds algorithm is presented to globally solving the linear multiplicative programming (LMP). We firstly convert the problem (LMP) into an equivalent programming one by introducing $p$ auxiliary variables. During the branch and bound search, the required lower bounds are computed by solving ordinary linear programming problems derived by using a Lagrangian duality theory. The proposed algorithm proves that it is convergent to a global mini...
Computing real zeros of a polynomial by branch and bound and branch and reduce algorithms
Le Thi Hoai An
2014-01-01
Full Text Available In this paper we propose two algorithms based on branch and bound method and reduced interval techniques to compute all real zeros of a polynomial. Quadratic bounding functions are proposed which are better than the well known linear underestimator. Experimental result shows the efficiency of the two algorithms when facing ill-conditioned polynomials.
An Effective Branch and Bound Algorithm for Minimax Linear Fractional Programming
Hong-Wei Jiao; Feng-Hui Wang; Yong-Qiang Chen
2014-01-01
An effective branch and bound algorithm is proposed for globally solving minimax linear fractional programming problem (MLFP). In this algorithm, the lower bounds are computed during the branch and bound search by solving a sequence of linear relaxation programming problems (LRP) of the problem (MLFP), which can be derived by using a new linear relaxation bounding technique, and which can be effectively solved by the simplex method. The proposed branch and bound algorithm is convergent to the...
A Branch and Bound Algorithm for the Global Optimization of Hessian Lipschitz Continuous Functions
Fowkes, J. M.; Gould, N. I. M.; Farmer, C.L.
2012-01-01
We present a branch and bound algorithm for the global optimization of a twice differentiable nonconvex objective function with a Lipschitz continuous Hessian over a compact, convex set. The algorithm is based on applying cubic regularisation techniques to the objective function within an overlapping branch and bound algorithm for convex constrained global optimization. Unlike other branch and bound algorithms, lower bounds are obtained via nonconvex underestimators of the function. For a num...
A branch and bound algorithm for the global optimization of Hessian Lipschitz continuous functions
Fowkes, Jaroslav M.
2012-06-21
We present a branch and bound algorithm for the global optimization of a twice differentiable nonconvex objective function with a Lipschitz continuous Hessian over a compact, convex set. The algorithm is based on applying cubic regularisation techniques to the objective function within an overlapping branch and bound algorithm for convex constrained global optimization. Unlike other branch and bound algorithms, lower bounds are obtained via nonconvex underestimators of the function. For a numerical example, we apply the proposed branch and bound algorithm to radial basis function approximations. © 2012 Springer Science+Business Media, LLC.
Revisiting the upper bounding process in a safe Branch and Bound algorithm
Goldsztejn, Alexandre; Lebbah, Yahia; Michel, Claude; Rueher, Michel
2008-01-01
Finding feasible points for which the proof succeeds is a critical issue in safe Branch and Bound algorithms which handle continuous problems. In this paper, we introduce a new strategy to compute very accurate approximations of feasible points. This strategy takes advantage of the Newton method for under-constrained systems of equations and inequalities. More precisely, it exploits the optimal solution of a linear relaxation of the problem to compute efficiently a promising upper bound. Firs...
Parallel Branch and Bound Algorithm for Computing Maximal Structured Singular Value
Chen, Xinjia; Zhou, Kemin
2008-01-01
In this paper, we have developed a parallel branch and bound algorithm which computes the maximal structured singular value $\\mu$ without tightly bounding $\\mu$ for each frequency and thus significantly reduce the computational complexity.
Revisiting the upper bounding process in a safe Branch and Bound algorithm
Goldsztejn, Alexandre; Michel, Claude; Rueher, Michel
2008-01-01
Finding feasible points for which the proof succeeds is a critical issue in safe Branch and Bound algorithms which handle continuous problems. In this paper, we introduce a new strategy to compute very accurate approximations of feasible points. This strategy takes advantage of the Newton method for under-constrained systems of equations and inequalities. More precisely, it exploits the optimal solution of a linear relaxation of the problem to compute efficiently a promising upper bound. First experiments on the Coconuts benchmarks demonstrate that this approach is very effective.
Branch and bound algorithms for rate-distortion optimized media streaming
Röder, Martin; Cardinal, Jean; Hamzaoui, Raouf
2006-01-01
We consider the problem of ratedistortion optimized streaming of packetized multimedia data over a single quality of service network using feedback and retransmissions. For a single data unit, we prove that the problem is NP-hardand provide efficient branch and bound algorithms that are much faster than the previously best solution based on dynamic programming. For a group of interdependent data units, we show how to compute optimal solutions with branch and bound algorithms. The branch and b...
A new branch and bound algorithm for the network design problem
G. Gallo
1981-01-01
A Branch and Bound algorithm is presented to solve the Network Design Problem. This algorithm makes use of new upper and lower bounds which are sharper than the ones used in previous algorithms of the same type. The results of a rather wide numerical experimentation are illustrated.
An Enhanced Branch-and-bound Algorithm for the Talent Scheduling Problem
Zhang, Zizhen; Qin, Hu; Liang, Xiaocong; Lim, Andrew
2014-01-01
The talent scheduling problem is a simplified version of the real-world film shooting problem, which aims to determine a shooting sequence so as to minimize the total cost of the actors involved. In this article, we first formulate the problem as an integer linear programming model. Next, we devise a branch-and-bound algorithm to solve the problem. The branch-and-bound algorithm is enhanced by several accelerating techniques, including preprocessing, dominance rules and caching search states....
A Branch and Bound Reduced Algorithm for Quadratic Programming Problems with Quadratic Constraints
Yuelin Gao; Feifei Li; Siqiao Jin
2013-01-01
We propose a branch and bound reduced algorithm for quadratic programming problems with quadratic constraints. In this algorithm, we determine the lower bound of the optimal value of original problem by constructing a linear relaxation programming problem. At the same time, in order to improve the degree of approximation and the convergence rate of acceleration, a rectangular reduction strategy is used in the algorithm. Numerical experiments show that the proposed algorithm is feasible and ef...
A Branch and Bound Algorithm for Project Scheduling Problem with Spatial Resource Constraints
Shicheng Hu; Song Wang; Yonggui Kao; Takao Ito; Xuedong Sun
2015-01-01
With respect to the block assembly schedule in a shipbuilding enterprise, a spatial resource constrained project scheduling problem (SRCPSP) is proposed, which aims to minimize the makespan of a project under the constraints of the availability of a two-dimensional spatial resource and the precedence relationship between tasks. In order to solve SRCPSP to the optimum, a branch and bound algorithm (BB) is developed. For the BB-SRCPSP, first, an implicitly enumerative branch scheme is presented...
Brusco, Michael J.
2002-01-01
Developed a branch-and-bound algorithm that can be used to seriate a symmetric dissimilarity matrix by identifying a reordering of rows and columns of the matrix optimizing an anti-Robinson criterion. Computational results suggest that with respect to computational efficiency, the approach is generally competitive with dynamic programming. (SLD)
Veldkamp, Bernard P.
A mathematical programming approach is presented for computer adaptive testing (CAT) with many constraints on the item and test attributes. Because mathematical programming problems have to be solved while the examinee waits for the next item, a fast implementation of the Branch-and-Bound algorithm is needed for this approach. Eight modifications…
A branch-and-bound algorithm for stable scheduling in single-machine production systems
Leus, Roel; Herroelen, Willy
2004-01-01
Robust scheduling aims at the construction of a schedule that is protected against uncertain events. A stable schedule is a robust schedule that will change little when variations in the input parameters arise. This paper proposes a branch-and-bound algorithm for optimally solving a single-machine scheduling problem with stability objective, when a single job is anticipated to be disrupted.
Parallel Branch and Bound Algorithm - A comparison between serial, OpenMP and MPI implementations
This paper presents a comparison of an extended version of the regular Branch and Bound algorithm previously implemented in serial with a new parallel implementation, using both MPI (distributed memory parallel model) and OpenMP (shared memory parallel model). The branch-and-bound algorithm is an enumerative optimization technique, where finding a solution to a mixed integer programming (MIP) problem is based on the construction of a tree where nodes represent candidate problems and branches represent the new restrictions to be considered. Through this tree all integer solutions of the feasible region of the problem are listed explicitly or implicitly ensuring that all the optimal solutions will be found. A common approach to solve such problems is to convert sub-problems of the mixed integer problem to linear programming problems, thereby eliminating some of the integer constraints, and then trying to solve that problem using an existing linear program approach. The paper describes the general branch and bound algorithm used and provides details on the implementation and the results of the comparison.
A Branch and Bound Algorithm for the Critical Grid Coverage Problem in Wireless Sensor Networks
Maher Rebai; Matthieu Le Berre; Faicel Hnaien; Hichem Snoussi; Lyes Khoukhi
2014-01-01
We aim to cover a grid fully by deploying the necessary wireless sensors while maintaining connectivity between the deployed sensors and a base station (the sink). The problem is NP-Complete as it can be reduced to a 2-dimensional critical coverage problem, which is an NP-Complete problem. We develop a branch and bound (B&B) algorithm to solve the problem optimally. We verify by computational experiments that the proposed B&B algorithm is more efficient, in terms of computation time, than the...
M Barketau; Kopfer, H; E. Pesch
2013-01-01
In this paper, we consider the container transshipment problem at a railway hub. A simple lower bound known for this problem will be improved by a new Lagrangian relaxation lower bound. Computational tests show that this lower bound outperforms the simple one and decreases substantially the run time of the branch-and-bound algorithm.
Nakariyakul, Songyot; Casasent, David
2006-10-01
Detection of skin tumors on chicken carcasses is considered. A chicken skin tumor consists of an ulcerous lesion region surrounded by a region of thickened-skin. We use a new adaptive branch-and-bound (ABB) feature selection algorithm to choose only a few useful wavebands from hyperspectral data for use in a real-time multispectral camera. The ABB algorithm selects an optimal feature subset and is shown to be much faster than any other versions of the branch and bound algorithm. We found that the spectral responses of the lesion and the thickened-skin regions of tumors are considerably different; thus we train our feature selection algorithm to separately detect the lesion regions and thickened-skin regions of tumors. We then fuse the two HS detection results of lesion and thickened-skin regions to reduce false alarms. Initial results on six hyperspectral cubes show that our method gives an excellent tumor detection rate and a low false alarm rate.
A branch-and-bound algorithm for single-machine earliness-tardiness scheduling with idle time
Hoogeveen, Han; Velde, Steef
1996-01-01
textabstractPresents a branch-and-bound algorithm which is based upon many dominance rules and various lower bound approaches, including relaxation of the machine capacity, data manipulation and Lagrangian relaxation. Insertion of the idle time for a given sequence; Properties of the proposed lower bounds.
A Parallel Branch and Bound Algorithm for the Maximum Labelled Clique Problem
McCreesh, Ciaran; Prosser, Patrick
2014-01-01
The maximum labelled clique problem is a variant of the maximum clique problem where edges in the graph are given labels, and we are not allowed to use more than a certain number of distinct labels in a solution. We introduce a new branch-and-bound algorithm for the problem, and explain how it may be parallelised. We evaluate an implementation on a set of benchmark instances, and show that it is consistently faster than previously published results, sometimes by four or five orders of magnitude.
A Branch and Bound Algorithm for a Class of Biobjective Mixed Integer Programs
Stidsen, Thomas Riis; Andersen, Kim Allan; Dammann, Bernd
2014-01-01
Pareto-optimal front). In this paper, we first give a survey of the newly developed branch and bound methods for solving MOMIP problems. After that, we propose a new branch and bound method for solving a subclass of MOMIP problems, where only two objectives are allowed, the integer variables are binary......, and one of the two objectives has only integer variables. The proposed method is able to find the full set of nondominated points. It is tested on a large number of problem instances, from six different classes of MOMIP problems. The results reveal that the developed biobjective branch and bound...
Belgacem BETTAYEB; Imed KACEM; Kondo H.ADJALLAH
2008-01-01
This article investigates identical parallel machines scheduling with family setup times. Theobjective function being the weighted sum of completion times, the problem is known to be strongly NP-hard. We propose a constructive heuristic algorithm and three complementary lower bounds. Two of these bounds proceed by elimination of setup times or by distributing each of them to jobs of the corresponding family, while the third one is based on a lagrangian relaxation. The bounds and the heuristic are incorporated into a branch-and-bound algorithm. Experimental results obtained outperform those of the methods presented in previous works, in term of size of solved problems.
A Branch and Bound Algorithm for a Class of Biobjective Mixed Integer Programs
Stidsen, Thomas Riis; Andersen, Kim Allan; Dammann, Bernd
2014-01-01
Pareto-optimal front). In this paper, we first give a survey of the newly developed branch and bound methods for solving MOMIP problems. After that, we propose a new branch and bound method for solving a subclass of MOMIP problems, where only two objectives are allowed, the integer variables are binary......, and one of the two objectives has only integer variables. The proposed method is able to find the full set of nondominated points. It is tested on a large number of problem instances, from six different classes of MOMIP problems. The results reveal that the developed biobjective branch and bound...... method performs better on five of the six test problems, compared with a generic two-phase method. At this time, the two-phase method is the most preferred exact method for solving MOMIP problems with two criteria and binary variables....
A Lagrangian Dual-Based Branch-and-Bound Algorithm for the Generalized Multi-Assignment Problem
June S. Park; Byung Ha Lim; Youngho Lee
1998-01-01
This paper develops a Lagrangian dual-based branch-and-bound algorithm for the generalized multi-assignment problem (GMAP) which includes the well-known generalized assignment problem (GAP) as a special case. In GMAP, an object may be required to be duplicated in multiple locations. We develop a Lagrangian dual ascent algorithm for GMAP. This dual ascent and the subgradient search each possess advantages that can be combined to develop a new Lagrangian dual search algorithm. The latter algori...
A simple but usually fast branch-and-bound algorithm for the capacitated facility location problem
Görtz, Simon; Klose, Andreas
2012-01-01
This paper presents a simple branch-and-bound method based on Lagrangean relaxation and subgradient optimization for solving large instances of the capacitated facility location problem (CFLP) to optimality. To guess a primal solution to the Lagrangean dual, we average solutions to the Lagrangean...
A subgradient-based branch-and-bound algorithm for the capacitated facility location problem
Görtz, Simon; Klose, Andreas
This paper presents a simple branch-and-bound method based on Lagrangean relaxation and subgradient optimization for solving large instances of the capacitated facility location problem (CFLP) to optimality. In order to guess a primal solution to the Lagrangean dual, we average solutions to the...... Lagrangean subproblem. Branching decisions are then based on this estimated (fractional) primal solution. Extensive numerical results reveal that the method is much more faster and robust than other state-of-the-art methods for solving the CFLP exactly....
On prediction mechanisms in Fast Branch & Bound algorithms
Somol, Petr; Pudil, Pavel; Grim, Jiří
Berlin : Springer, 2004 - (Fred, A.; Caelli, T.; Duin, R.), s. 716-724 ISBN 3-540-22570-6. - (Lecture Notes in Computer Science.. 3138). [Joint IAPR Workshops SSPR 2004 and SPR 2004. Lisbon (PT), 18.08.2004-20.08.2004] R&D Projects: GA ČR GA402/02/1271; GA ČR GA402/03/1310 Institutional research plan: CEZ:AV0Z1075907 Keywords : subset search * feature selection * search tree Subject RIV: BD - Theory of Information http://library.utia.cas.cz/separaty/historie/somol-on prediction mechanisms in fast branch & bound algorithms.pdf
Towards an abstract parallel branch and bound machine
Bruin, Arie; Kindervater, Gerard; Trienekens, H.W.J.M.
1995-01-01
textabstractMany (parallel) branch and bound algorithms look very different from each other at first glance. They exploit, however, the same underlying computational model. This phenomenon can be used to define branch and bound algorithms in terms of a set of basic rules that are applied in a specific (predefined) order. In the sequential case, the specification of Mitten's rules turns out to be sufficient for the development of branch and bound algorithms. In the parallel case, the situation...
Shangchia Liu
2015-01-01
Full Text Available In the field of distributed decision making, different agents share a common processing resource, and each agent wants to minimize a cost function depending on its jobs only. These issues arise in different application contexts, including real-time systems, integrated service networks, industrial districts, and telecommunication systems. Motivated by its importance on practical applications, we consider two-agent scheduling on a single machine where the objective is to minimize the total completion time of the jobs of the first agent with the restriction that an upper bound is allowed the total completion time of the jobs for the second agent. For solving the proposed problem, a branch-and-bound and three simulated annealing algorithms are developed for the optimal solution, respectively. In addition, the extensive computational experiments are also conducted to test the performance of the algorithms.
Combining Interval Branch and Bound and Stochastic Search
Dhiranuch Bunnag
2014-01-01
This paper presents global optimization algorithms that incorporate the idea of an interval branch and bound and the stochastic search algorithms. Two algorithms for unconstrained problems are proposed, the hybrid interval simulated annealing and the combined interval branch and bound and genetic algorithm. The numerical experiment shows better results compared to Hansen’s algorithm and simulated annealing in terms of the storage, speed, and number of function evaluations. The convergence pro...
An object oriented approach to generic branch and bound
Bruin, Arie; Kindervater, Gerard; Trienekens, H.W.J.M.; Goot, R.A.
1996-01-01
textabstractBranch and bound algorithms can be characterized by a small set of basic rules that are applied in a divide-and-conquer-like framework. The framework is about the same in all applications, whereas the specification of the rules is problem dependent. Building a framework is a rather simple task in sequential implementations, but must not be underestimated in the parallel case, especially if an efficient branch and bound algorithm is required. In generic branch and bound models, the...
Distribution Network Planning and Design Using Branch and Bound Methods
Jalal Abdallah
2005-01-01
This study presents implementation of the bound and branch methods as an optimization mathematical device for distribution network planning. A development technology concentrates on minimizing the total costs and provides extended opportunities for improvement of network operation, from the initial planning stage. The study illustrate the mathematical and the algorithm of the branch and bound method with an example to indicate the efficiency of the branch and bound in plan...
Distribution Network Planning and Design Using Branch and Bound Methods
Jalal Abdallah
2005-01-01
Full Text Available This study presents implementation of the bound and branch methods as an optimization mathematical device for distribution network planning. A development technology concentrates on minimizing the total costs and provides extended opportunities for improvement of network operation, from the initial planning stage. The study illustrate the mathematical and the algorithm of the branch and bound method with an example to indicate the efficiency of the branch and bound in planning and design processes. It also shows that the optimal configuration strongly depends on the branching rule and on the bound calculation bases.
Improved branch and bound method for control structure screening
Cao, Yi; Saha, Prabirkumar
2005-01-01
The main aim of this paper is to present an improved algorithm of “Branch and Bound” method for control structure screening. The new algorithm uses a best- first search approach, which is more efficient than other algorithms based on depth-first search approaches. Detailed explanation of the algorithms is provided in this paper along with a case study on Tennessee–Eastman process to justify the theory of branch and bound method. The case study uses the Hankel singular value ...
Muu, Lê D.; Oettli, Werner
1988-01-01
A unifled approach to branch-and-bound and cutting plane methods for solving a certain class of nonconvex optimization problems is proposed. Based on this approach an implementable algorithm is obtained for programming problems with a bilinear objective function and jointly convex constraints.
A branch and bound algorithm to optimize the representation of tabular decision processe
Vanthienen, Jan; Dries, E
1996-01-01
Decision situations have various aspects: knowledge acquisition and structuring, knowledge representation, knowledge validation and decision making. It has been recognized in literature that decision tables can play an important role in each of these stages. It is however not necessary to use only one representation formalism during the whole life cycle of an intelligent system. Likewise it is possible that different formats of the same formalism serve different purposes in the development...
A Branch and Bound Method for Optimization Problems with Fuzzy Numbers
Iemets, O.; Yemets, O.
2012-01-01
The algorithm of branch and bound method for the minimization problem in the fuzzy setting is proposed. The use of branch and bound method for combinatorial transportation problem on permutations with fuzzy data is shown.
Basis Reduction, and the Complexity of Branch-and-Bound
Pataki, Gabor; Tural, Mustafa
2009-01-01
The classical branch-and-bound algorithm for the integer feasibility problem has exponential worst case complexity. We prove that it is surprisingly efficient on reformulated problems, in which the columns of the constraint matrix are short, and near orthogonal, i.e. a reduced basis of the generated lattice; when the entries of A (the dense part of the constraint matrix) are from {1, ..., M} for a large enough M, branch-and-bound solves almost all reformulated instances at the rootnode. We al...
Branch and Bound Experiments in Convex Nonlinear Integer Programming
Omprakash K. Gupta; Ravindran, A
1985-01-01
The branch and bound principle has long been established as an effective computational tool for solving mixed integer linear programming problems. This paper investigates the computational feasibility of branch and bound methods in solving convex nonlinear integer programming problems. The efficiency of a branch and bound method often depends on the rules used for selecting the branching variables and branching nodes. Among others, the concepts of pseudo-costs and estimations are implemented ...
Solving Multistage Influence Diagrams using Branch-and-Bound Search
Yuan, Changhe; Wu, Xiaojian; Hansen, Eric A.
2012-01-01
A branch-and-bound approach to solving influ- ence diagrams has been previously proposed in the literature, but appears to have never been implemented and evaluated - apparently due to the difficulties of computing effective bounds for the branch-and-bound search. In this paper, we describe how to efficiently compute effective bounds, and we develop a practical implementa- tion of depth-first branch-and-bound search for influence diagram evaluation that outperforms existing methods for solvin...
A Branch and Bound and Simulated Annealing Approach for Job Shop Scheduling
Tan Hui Woon; Sutinah Salim
2004-01-01
This paper presents two approaches to the solution of the job shop scheduling problem, namely the branch and bound, and simulated annealing approach. The objective is to schedule the jobs on the machines so that the total completion time is minimized. In the branch and bound approach, the job shop scheduling problem is represented by a disjunctive graph, then the optimal schedule is obtained using the branch and bound algorithm while simulated annealing is a local search based algorithm which...
Faster Algorithms on Branch and Clique Decompositions
Bodlaender, Hans L.; van Leeuwen, Erik Jan; van Rooij, Johan M. M.; Vatshelle, Martin
We combine two techniques recently introduced to obtain faster dynamic programming algorithms for optimization problems on graph decompositions. The unification of generalized fast subset convolution and fast matrix multiplication yields significant improvements to the running time of previous algorithms for several optimization problems. As an example, we give an O^{*}(3^{ω/2k}) time algorithm for Minimum Dominating Set on graphs of branchwidth k, improving on the previous O *(4 k ) algorithm. Here ω is the exponent in the running time of the best matrix multiplication algorithm (currently ωgraphs of cliquewidth k, we improve from O *(8 k ) to O *(4 k ). We also obtain an algorithm for counting the number of perfect matchings of a graph, given a branch decomposition of width k, that runs in time O^{*}(2^{ω/2k}). Generalizing these approaches, we obtain faster algorithms for all so-called [ρ,σ]-domination problems on branch decompositions if ρ and σ are finite or cofinite. The algorithms presented in this paper either attain or are very close to natural lower bounds for these problems.
PICO: An Object-Oriented Framework for Branch and Bound
ECKSTEIN,JONATHAN; HART,WILLIAM E.; PHILLIPS,CYNTHIA A.
2000-12-01
This report describes the design of PICO, a C++ framework for implementing general parallel branch-and-bound algorithms. The PICO framework provides a mechanism for the efficient implementation of a wide range of branch-and-bound methods on an equally wide range of parallel computing platforms. We first discuss the basic architecture of PICO, including the application class hierarchy and the package's serial and parallel layers. We next describe the design of the serial layer, and its central notion of manipulating subproblem states. Then, we discuss the design of the parallel layer, which includes flexible processor clustering and communication rates, various load balancing mechanisms, and a non-preemptive task scheduler running on each processor. We describe the application of the package to a branch-and-bound method for mixed integer programming, along with computational results on the ASCI Red massively parallel computer. Finally we describe the application of the branch-and-bound mixed-integer programming code to a resource constrained project scheduling problem for Pantex.
Parallel Branch and Bound on a CPU-GPU System
Boukedjar, Abdelamine; Lalami, Mohamed Esseghir; El-Baz, Didier
2012-01-01
Hybrid implementation via CUDA of a branch and bound method for knapsack problems is proposed. Branch and bound computations can be carried out either on the CPU or on the GPU according to the size of the branch and bound list, i.e. the number of nodes. Tests are carried out on a Tesla C2050 GPU. A first series of computational results showing a substantial speedup is displayed and analyzed.
A branch-and-bound methodology within algebraic modelling systems
Bisschop, J.J.; Heerink, J.B.J.; Kloosterman, G.
1998-01-01
Through the use of application-specific branch-and-bound directives it is possible to find solutions to combinatorial models that would otherwise be difficult or impossible to find by just using generic branch-and-bound techniques within the framework of mathematical programming. {\\sc Minto} is an example of a system which offers the possibility to incorporate user-provided directives (written in {\\sc C}) to guide the branch-and-bound search. Its main focus, however, remains on mathematical p...
A Branch and Bound Approach to Solve the Preemptive Resource Leveling Problem
Behrouz Afshar-Nadjafi; Zeinab Khalaj; Esmaeil Mehdizadeh
2013-01-01
We study resource constrained project scheduling problem with respect to resource leveling as objective function and allowance of preemption in activities. The branch and bound algorithms proposed in previous researches on resource leveling problem do not consider preemption. So, representing a model for the problem, a branch and bound algorithm is proposed. This algorithm can handle preemption in resource leveling problem. Comparing the resource leveling problem and the preemptive resource l...
Metode Branch And Bound Untuk Menyelesaikan Program Stokastik Integer Dengan Adanya Resiko
Pangaribuan, Adil H.
2011-01-01
This thesis is addressed to develop branch-and-bound methods, that is to solve multistage stochastic integer programs with risk objectives which is related to wait-and-see problems which could be separated like risk neutral. All model classi_ed to this is overcome by presenting a combination between branch-and-bound algorithm and relaxation of non-anticipativity and constraint branching along non-anticipativity subspaces.
A parametric branch and bound approach to suboptimal explicit hybrid MPC
Axehill, Daniel; Besselmann, Thomas; Martino Raimondo, Davide; Morari, Manfred
2014-01-01
In this article we present a parametric branch and bound algorithm for computation of optimal and suboptimal solutions to parametric mixed-integer quadratic programs and parametric mixed-integer linear programs. The algorithm returns an optimal or suboptimal parametric solution with the level of suboptimality requested by the user. An interesting application of the proposed parametric branch and bound procedure is suboptimal explicit MPC for hybrid systems, where the introduced user-defined s...
Improved Branch-and-Bound for Low Autocorrelation Binary Sequences
Prestwich, S. D.
2013-01-01
The Low Autocorrelation Binary Sequence problem has applications in telecommunications, is of theoretical interest to physicists, and has inspired many optimisation researchers. Metaheuristics for the problem have progressed greatly in recent years but complete search has not progressed since a branch-and-bound method of 1996. In this paper we find four ways of improving branch-and-bound, leading to a tighter relaxation, faster convergence to optimality, and better empirical scalability.
PENJADWALAN PRODUKSI DENGAN METODE BRANCH AND BOUND PADA PT. XYZ
Mangngenre, Saiful; Rapi, Amrin; Flannery, Wendy
2014-01-01
Penjadwalan adalah suatu proses pengalokasian sumber daya dan mesin yang tersedia untuk menyelesaikan suatu pekerjaan dengan mempertimbangkan batasan-batasan yang ada.Penjadwalan produksi yang diterapkan di PT. XYZ selama ini hanya menggunakan metode intuitif saja. Dalam penelitian ini, untuk memecahkan masalah penjadwalan maka digunakan metode Branch and Bound. Metode Branch and Bound adalah metode pencarian solusi optimal pada permasalahan optimasi seperti pada masalah penjadwalan dengan ...
Branch and peg algorithms for the simple plant location problem
Goldengorin, Boris; Ghosh, Diptesh; Sierksma, Gerard
2001-01-01
The simple plant location problem is a well-studied problem in combinatorial optimization. It is one of deciding where to locate a set of plants so that a set of clients can be supplied by them at the minimum cost. This problem of ten appears as a subproblem in other combinatorial problems. Several branch and bound techniques have been developed to solve these problems. In this paper we present a few techniques that enhance the performance of branch and bound algorithms. The new algorithms th...
Fernandes, Florbela P.; Costa, Fernanda P.M.; Fernandes, Edite M.G.P.
2014-01-01
A mixed-integer nonlinear programming problem (MINLP) is a problem with continuous and integer variables and at least, one nonlinear function. This kind of problem appears in a wide range of real applications and is very difficult to solve. The difficulties are due to the nonlinearities of the functions in the problem and the integrality restrictions on some variables. When they are nonconvex then they are the most difficult to solve above all. We present a methodology to solve nonsmooth no...
Branch and Bound Methods for a Search Problem
Washburn, Alan R.
1997-01-01
The problem of searching for randomly moving targets such as children and submarines is known to be fundamentally difficult, but finding efficient methods for generating optimal or near optimal solutions is nonetheless an important practical problem. This paper investigates the efficiency of Branch and Bound methods, with emphasis on the tradeoff between the accuracy of the bound employed and the time required to compute it. A variety of bounds are investigated, some of which a...
A Branch and Bound Method for Stochastic Global Optimization
V.I. Norkin; G.C. Pflug; Ruszczynski, A.
1996-01-01
A stochastic version of the branch and bound method is proposed for solving stochastic global optimization problems. The method, instead of deterministic bounds, uses stochastic upper and lower estimates of the optimal value of subproblems, to guide the partitioning process. Almost sure convergence of the method is proved and random accuracy estimates derived. Methods for constructing random bounds for stochastic global optimization problems are discussed. The theoretical considerations are i...
Design of planar articulated mechanisms using branch and bound
Stolpe, Mathias; Kawamoto, Atsushi
2005-01-01
that buckling is prevented. The feasible set of the design problem is described by nonlinear differentiable and non-differentiable constraints as well as nonlinear matrix inequalities. To solve the mechanism design problem a branch and bound method based on convex relaxations is developed. To guarantee...... convergence of the method, two different types of convex relaxations are derived. The relaxations are strengthened by adding valid inequalities to the feasible set and by solving bound contraction sub-problems. Encouraging computational results indicate that the branch and bound method can reliably solve...
Design of planar articulated mechanisms using branch and bound
Stolpe, Mathias; Kawamoto, Atsushi
2004-01-01
that buckling is prevented. The feasible set of the design problem is described by nonlinear differentiable and non-differentiable constraints as well as nonlinear matrix inequalities. To solve the mechanism design problem a branch and bound method based on convex relaxations is developed. To guarantee...... convergence of the method, two different types of convex relaxations are derived. The relaxations are strengthened by adding valid inequalities to the feasible set and by solving bound contraction sub-problems. Encouraging computational results indicate that the branch and bound method can reliably solve...
Doyon, Jean-Philippe; Chauve, Cedric
2010-01-01
We describe a Branch-and-Bound algorithm for computing a parsimonious species tree given a set of gene family trees. Our algorithm can compute a parsimonious species tree for three cost measures: number of gene duplications, number of gene losses, and both combined. Moreover, to cope with intrinsic limitations of Branch-and-Bound algorithms for species trees inference regarding the number of taxa that can be considered, our algorithm can naturally take into account predefined relationships be...
Recursive algorithms, branching coefficients and applications
Lyakhovsky, Vladimir
2010-01-01
Recurrent relations for branching coefficients in affine Lie algebras integrable highest weight modules are studied. The decomposition algorithm based on the injection fan technique is adopted to the situation where the Weyl denominator becomes singular with respect to a reductive subalgebra. We study some modifications of the injection fan technique and demonstrate that it is possible to define the "subtracted fans" that play the role similar to the original ones. Possible applications of subtracted fans in CFT models are considered.
Computational Protein Design Using AND/OR Branch-and-Bound Search.
Zhou, Yichao; Wu, Yuexin; Zeng, Jianyang
2016-06-01
The computation of the global minimum energy conformation (GMEC) is an important and challenging topic in structure-based computational protein design. In this article, we propose a new protein design algorithm based on the AND/OR branch-and-bound (AOBB) search, a variant of the traditional branch-and-bound search algorithm, to solve this combinatorial optimization problem. By integrating with a powerful heuristic function, AOBB is able to fully exploit the graph structure of the underlying residue interaction network of a backbone template to significantly accelerate the design process. Tests on real protein data show that our new protein design algorithm is able to solve many problems that were previously unsolvable by the traditional exact search algorithms, and for the problems that can be solved with traditional provable algorithms, our new method can provide a large speedup by several orders of magnitude while still guaranteeing to find the global minimum energy conformation (GMEC) solution. PMID:27167301
N D
2009-01-01
There has been a lot of recent work on Bayesian methods for reinforcement learning exhibiting near-optimal online performance. The main obstacle facing such methods is that in most problems of interest, the optimal solution involves planning in an infinitely large tree. However, it is possible to obtain stochastic lower and upper bounds on the value of each tree node. This enables us to use stochastic branch and bound algorithms to search the tree efficiently. This paper proposes two such alg...
A branch and bound approach for minimizing the energy consumption of an electrical vehicle
Merakeb, Abdelkader; Messine, Frédéric
2013-01-01
National audience In this paper we discuss about the way to approximate the solution of an optimal control problem with a switched command. Our Method is based on a discretization technique associated with a Branch and Bound algorithm. The problem that we focus on is the minimization of the consumption of the energy of an electrical vehicle during some imposed displacements.
Some distance bounds of branching processes and their diffusion limits
Kammerer, Niels B
2010-01-01
We compute exact values respectively bounds of "distances" - in the sense of (transforms of) power divergences and relative entropy - between two discrete-time Galton-Watson branching processes with immigration GWI for which the offspring as well as the immigration is arbitrarily Poisson-distributed (leading to arbitrary type of criticality). Implications for asymptotic distinguishability behaviour in terms of contiguity and entire separation of the involved GWI are given, too. Furthermore, we determine the corresponding limit quantities for the context in which the two GWI converge to Feller-type branching diffusion processes, as the time-lags between observations tend to zero. Some applications to (static random environment like) Bayesian decision making and Neyman-Pearson testing are presented as well.
Optimal material selection using branch and bound techniques
Sepulveda, A. E.
1993-01-01
A methodology for structural synthesis is presented in which the optimal material selection for the structural members is treated in terms of (0,1) variables. Structural member sizes and material selection variables are treated simultaneously as design variables. Optimization is carried out by generating and solving a sequence of explicit approximate problems using a branch and bound strategy. Intermediate design variables and intermediate response quantities are used to enhance the quality of the approximate design problems. Numerical results for example problems are presented to illustrate the efficiency of the design procedure set forth.
Globally Optimal Hand-Eye Calibration Using Branch-and-Bound.
Heller, Jan; Havlena, Michal; Pajdla, Tomas
2016-05-01
This paper introduces a novel solution to the hand-eye calibration problem. It uses camera measurements directly and, at the same time, requires neither prior knowledge of the external camera calibrations nor a known calibration target. Our algorithm uses branch-and-bound approach to minimize an objective function based on the epipolar constraint. Further, it employs Linear Programming to decide the bounding step of the algorithm.Our technique is able to recover both the unknown rotation and translation simultaneously and the solution is guaranteed to be globally optimal with respect to the L∞-norm. PMID:26353364
A Branch and Bound Method for the Open Shop Problem
Brucker, P; Hurink, J.L.; Jurisch, B.; Wöstmann, B.
1997-01-01
A fast branch & bound method for the open-shop problem based on a disjunctive graph formulation of the problem is developed. Computational results show that the method yields excellent results. Some benchmark problems from the literature were solved to optimality for the first time.
Bifurcation Analysis Using Rigorous Branch and Bound Methods
Smith, Andrew P.; Crespo, Luis G.; Munoz, Cesar A.; Lowenberg, Mark H.
2014-01-01
For the study of nonlinear dynamic systems, it is important to locate the equilibria and bifurcations occurring within a specified computational domain. This paper proposes a new approach for solving these problems and compares it to the numerical continuation method. The new approach is based upon branch and bound and utilizes rigorous enclosure techniques to yield outer bounding sets of both the equilibrium and local bifurcation manifolds. These sets, which comprise the union of hyper-rectangles, can be made to be as tight as desired. Sufficient conditions for the existence of equilibrium and bifurcation points taking the form of algebraic inequality constraints in the state-parameter space are used to calculate their enclosures directly. The enclosures for the bifurcation sets can be computed independently of the equilibrium manifold, and are guaranteed to contain all solutions within the computational domain. A further advantage of this method is the ability to compute a near-maximally sized hyper-rectangle of high dimension centered at a fixed parameter-state point whose elements are guaranteed to exclude all bifurcation points. This hyper-rectangle, which requires a global description of the bifurcation manifold within the computational domain, cannot be obtained otherwise. A test case, based on the dynamics of a UAV subject to uncertain center of gravity location, is used to illustrate the efficacy of the method by comparing it with numerical continuation and to evaluate its computational complexity.
A branch and bound method for the job-shop problem with sequence-dependent setup times
Artigues, Christian; Feillet, Dominique
2007-01-01
This paper deals with the job-shop scheduling problem with sequence-dependent setup times. We propose a new method to solve the makespan minimization problem to optimality. The method is based on iterative solving via branch and bound decisional versions of the problem. At each node of the branch and bound tree, constraint propagation algorithms adapted to setup times are performed for domain filtering and feasibility check. Relaxations based on the traveling salesman problem with time window...
Using the primal-dual interior point algorithm within the branch-price-and-cut method
Munari, P.; Gondzio, J.
2013-01-01
Branch-price-and-cut has proven to be a powerful method for solving integer programming problems. It combines decomposition techniques with the generation of both columns and valid inequalities and relies on strong bounds to guide the search in the branch-and-bound tree. In this paper, we present how to improve the performance of a branch-price-and-cut method by using the primal-dual interior point algorithm. We discuss in detail how to deal with the challenges of using the interior point alg...
Clausen, Jens; Zilinskas, A,
2002-01-01
We consider the problem of optimizing a Lipshitzian function. The branch and bound technique is a well-known solution method, and the key components for this are the subdivision scheme, the bound calculation scheme, and the initialization. For Lipschitzian optimization, the bound calculations are...
Parallel Branch-and-Bound Methods for the Job Shop Scheduling
Clausen, Jens; Perregaard, Michael
1998-01-01
the JSS problem, but with limited success. Even with recent methods, it is still not possible to solve problems substantially larger than 10 machines and 10 jobs. In the current study, we focus on parallel methods for solving JSS problems. We implement two different parallel branch......-and-bound algorithms for JSS on a 16-processor MEIKO computing surface with Intel i860 processors and perform extensive computational testing using classical publicly available benchmark problems. The parallel part of one of the implementations is based on a similar parallel code for quadratic assignment problems...
A semidefinite programming based branch-and-bound framework for the quadratic assignment problem
2014-01-01
The practical approach to calculate an exact solution for a quadratic assignment problem (QAP) via a branch-and-bound framework depends strongly on a "smart" choice of different strategies within the framework, for example the branching strategy, heuristics for the upper bound or relaxations for the lower bound. In the first part of this thesis, we analyze promising old and new semidefinite programming (SDP) relaxations. In particular, we focus on their complexity, the strength of the respect...
Morrison, David R.; Sewell, Edward C.; Sheldon H. Jacobson
2014-01-01
Branch-and-price algorithms combine a branch-and-bound search with an exponentially-sized LP formulation that must be solved via column generation. Unfortunately, the standard branching rules used in branch-and-bound for integer programming interfere with the structure of the column generation routine; therefore, most such algorithms employ alternate branching rules to circumvent this difficulty. This paper shows how a zero-suppressed binary decision diagram (ZDD) can be used to solve the pri...
Upper bound on the number of steps for solving the subset sum problem by the Branch-and-Bound method
Kolpakov, Roman; Posypkin, Mikhail
2015-01-01
We study the computational complexity of one of the particular cases of the knapsack problem: the subset sum problem. For solving this problem we consider one of the basic variants of the Branch-and-Bound method in which any sub-problem is decomposed along the free variable with the maximal weight. By the complexity of solving a problem by the Branch-and-Bound method we mean the number of steps required for solving the problem by this method. In the paper we obtain upper bounds on the complex...
A Partitioning and Bounded Variable Algorithm for Linear Programming
Sheskin, Theodore J.
2006-01-01
An interesting new partitioning and bounded variable algorithm (PBVA) is proposed for solving linear programming problems. The PBVA is a variant of the simplex algorithm which uses a modified form of the simplex method followed by the dual simplex method for bounded variables. In contrast to the two-phase method and the big M method, the PBVA does…
GPU Implementation of the Branch and Bound method for knapsack problems
El-Baz, Didier; El Baz, Didier; Lalami, Mohamed Esseghir
2012-01-01
In this paper, we propose an efficient implementation of the branch and bound method for knapsack problems on a CPU-GPU system via CUDA. Branch and bound computations can be carried out either on the CPU or on a GPU according to the size of the branch and bound list. A better management of GPUs memories, less GPU-CPU communications and better synchronization between GPU threads are proposed in this new implementation in order to increase efficiency. Indeed, a series of computational results i...
A Branch and Bound Approach for Truss Topology Design Problems with Valid Inequalities
One of the classical problems in the structural optimization field is the Truss Topology Design Problem (TTDP) which deals with the selection of optimal configuration for structural systems for applications in mechanical, civil, aerospace engineering, among others. In this paper we consider a TTDP where the goal is to find the stiffest truss, under a given load and with a bound on the total volume. The design variables are the cross-section areas of the truss bars that must be chosen from a given finite set. This results in a large-scale non-convex problem with discrete variables. This problem can be formulated as a Semidefinite Programming Problem (SDP problem) with binary variables. We propose a branch and bound algorithm to solve this problem. In this paper it is considered a binary formulation of the problem, to take advantage of its structure, which admits a Knapsack problem as subproblem. Thus, trying to improve the performance of the Branch and Bound, at each step, some valid inequalities for the Knapsack problem are included.
Efficient Implementation Of Branch-And-Bound Method On Desktop Grids
Bo Tian
2014-01-01
Full Text Available The Berkeley Open Infrastructure for Network Computing (BOINC is an opensource middleware system for volunteer and desktop grid computing. In this paper we propose BNBTEST, a BOINC version of distributed branch and bound method. The crucial issues of distributed branch-and-bound method are traversing the search tree and loading balance. We developed subtaskspackaging method and three dierent subtasks' distribution strategies to solve these.
Efficient Implementation Of Branch-And-Bound Method On Desktop Grids
Bo Tian; Mikhail Posypkin
2014-01-01
The Berkeley Open Infrastructure for Network Computing (BOINC) is an opensource middleware system for volunteer and desktop grid computing. In this paper we propose BNBTEST, a BOINC version of distributed branch and bound method. The crucial issues of distributed branch-and-bound method are traversing the search tree and loading balance. We developed subtaskspackaging method and three dierent subtasks' distribution strategies to solve these.
Performance analysis of parallel branch and bound search with the hypercube architecture
Mraz, Richard T.
1987-01-01
With the availability of commercial parallel computers, researchers are examining new classes of problems which might benefit from parallel computing. This paper presents results of an investigation of the class of search intensive problems. The specific problem discussed is the Least-Cost Branch and Bound search method of deadline job scheduling. The object-oriented design methodology was used to map the problem into a parallel solution. While the initial design was good for a prototype, the best performance resulted from fine-tuning the algorithm for a specific computer. The experiments analyze the computation time, the speed up over a VAX 11/785, and the load balance of the problem when using loosely coupled multiprocessor system based on the hypercube architecture.
Tradeoffs Between Branch Mispredictions and Comparisons for Sorting Algorithms
Brodal, Gerth Stølting; Moruz, Gabriel
) comparisons performs Omega(nlogd n) branch mispredictions. We show that Multiway MergeSort achieves this tradeoff by adopting a multiway merger with a low number of branch mispredictions. For adaptive sorting algorithms we similarly obtain that an algorithm performing O(dn(1+log (1+Inv/n))) comparisons must...
Recursive Branching Simulated Annealing Algorithm
Bolcar, Matthew; Smith, J. Scott; Aronstein, David
2012-01-01
solution, and the region from which new configurations can be selected shrinks as the search continues. The key difference between these algorithms is that in the SA algorithm, a single path, or trajectory, is taken in parameter space, from the starting point to the globally optimal solution, while in the RBSA algorithm, many trajectories are taken; by exploring multiple regions of the parameter space simultaneously, the algorithm has been shown to converge on the globally optimal solution about an order of magnitude faster than when using conventional algorithms. Novel features of the RBSA algorithm include: 1. More efficient searching of the parameter space due to the branching structure, in which multiple random configurations are generated and multiple promising regions of the parameter space are explored; 2. The implementation of a trust region for each parameter in the parameter space, which provides a natural way of enforcing upper- and lower-bound constraints on the parameters; and 3. The optional use of a constrained gradient- search optimization, performed on the continuous variables around each branch s configuration in parameter space to improve search efficiency by allowing for fast fine-tuning of the continuous variables within the trust region at that configuration point.
Analisis Permasalahan Cutting Stock Satu Dimensi Dengan Metode Branch And Bound
Sitohang, Veronika LS
2011-01-01
Yang menjadi tujuan dalam permasalahan cutting stock adalah meminimumkan sisa potongan sehingga menambah keuntungan perusahaan. Untuk mencapai tujuan yang sedemikian, diperlukan pemotongan pola yang baik, tanpa mengabaikan panjang standard suatu gulungan raw. Metode Branch and Bound dapat digunakan untuk mengoptimalkan keuntungan dalam menentukan pola yang optimal untuk dipotong dengan memperhatikan batasan-batasan yang diberikan. Tulisan ini membahas tentang bagaimana me...
Enhancements of branch and bound methods for the maximal constraint satisfaction problem
Wallace, R.J. [Univ. of New Hampshire, Durham, NH (United States)
1996-12-31
Two methods are described for enhancing performance of branch and bound methods for overconstrained CSPs. These methods improve either the upper or lower bound, respectively, during search, so the two can be combined. Upper bounds are improved by using heuristic repair methods before search to find a good solution quickly, whose cost is used as the initial upper bound. The method for improving lower bounds is an extension of directed arc consistency preprocessing, used in conjunction with forward checking. After computing directed arc consistency counts, inferred counts are computed for all values based on minimum counts for values of adjacent variables that are later in the search order. This inference process can be iterated, so that counts are cascaded from the end to the beginning of the search order, to augment the initial counts. Improvements in time and effort are demonstrated for both techniques using random problems.
Brusco, Michael J.; Stahl, Stephanie
2005-01-01
There are two well-known methods for obtaining a guaranteed globally optimal solution to the problem of least-squares unidimensional scaling of a symmetric dissimilarity matrix: (a) dynamic programming, and (b) branch-and-bound. Dynamic programming is generally more efficient than branch-and-bound, but the former is limited to matrices with…
A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem
Jepsen, Mads Kehlet; Spoorendonk, Simon; Røpke, Stefan
2013-01-01
This paper presents an exact method for solving the symmetric two-echelon capacitated vehicle routing problem, a transportation problem concerned with the distribution of goods from a depot to a set of customers through a set of satellite locations. The presented method is based on an edge flow m...... model that is a relaxation and provides a valid lower bound. A specialized branching scheme is employed to obtain feasible solutions. Out of a test set of 93 instances the algorithm is able to solve 47 to optimality surpassing previous exact algorithms....
Managing Water Quality under Uncertainty: Application of a New Stochastic Branch and Bound Method
Lence, B.J.; Ruszczynski, A.
1996-01-01
The problem of water quality management under uncertain emission levels, reaction rates and pollutant transport is considered. Various performance measures: reliability, resiliency and vulnerability are taken into account. A general methodology for finding a cost-effective water quality management program is developed. The approach employs a new idea of the stochastic branch and bound method, which combines random estimates of the performance for subsets of decisions with iterative refinement...
Parallel Branch-and-Bound Methods for the Job Shop Scheduling
Clausen, Jens; Perregaard, Michael
1998-01-01
-and-bound algorithms for JSS on a 16-processor MEIKO computing surface with Intel i860 processors and perform extensive computational testing using classical publicly available benchmark problems. The parallel part of one of the implementations is based on a similar parallel code for quadratic assignment problems...
Optimal chiller sequencing by branch and bound method for saving energy
This paper proposes a method for using the branch and bound (B and B) method to solve the optimal chiller sequencing (OCS) problem and to eliminate the deficiencies of conventional methods. The coefficient of performance (COP) of the chiller is adopted as the objective function because it is concave. The Lagrangian method determines the optimal chiller loading (OCL) in each feasible state. The potential performance of the proposed method is examined with reference to an example system. The proposed method consumes much less power than the conventional method and is very appropriate for application in air conditioning systems
A branch and bound for single machine stochastic scheduling to minimize the maximum lateness ,
Hamidreza Haddad
2012-04-01
Full Text Available This paper studies the problem of single machine stochastic scheduling with random processing times, deterministic due dates and an independent setup time. The jobs are also deteriorated based on the position, which their processes are done. The objective function is to find a schedule of jobs, which minimizes the expected value of maximum lateness. A branch and bound scheme is presented to solve the problem analytically and a simulated annealing meta-heuristic (SA is also provided for solving the problem in larger scales. Computational experiments demonstrate that the proposed SA is capable of finding near optimal solutions with very low gap.
Mukhacheva E.A.
2000-01-01
Full Text Available Two algorithms for the one-dimensional cutting problem, namely, a modified branch-and-bound method (exact method and a heuristic sequential value correction method are suggested. In order to obtain a reliable assessment of the efficiency of the algorithms, hard instances of the problem were considered and from the computational experiment it seems that the efficiency of the heuristic method appears to be superior to that of the exact one, taking into account the computing time of the latter. A detailed description of the two methods is given along with suggestions for their improvements.
Gadegaard, Sune Lauth; Ehrgott, Matthias; Nielsen, Lars Relund
2016-01-01
strengthened by cutting planes. In addition, we suggest an extension of the branching strategy "Pareto branching''. Extensive computational results obtained for the bi-objective single source capacitated facility location problem prove the effectiveness of the algorithms....... bound sets that prevents us from solving the bi-objective LP-relaxation of each branching node. To strengthen the lower bound sets, we propose a bi-objective cutting plane algorithm that dynamically adjusts the weights of the objective functions such that different parts of the feasible set are...
Traditional probabilistic risk assessment (PRA) methods have been developed to evaluate risk associated with complex systems; however, PRA methods lack the capability to evaluate complex dynamic systems. In these systems, time and energy scales associated with transient events may vary as a function of transition times and energies to arrive at a different physical state. Dynamic PRA (DPRA) methods provide a more rigorous analysis of complex dynamic systems. Unfortunately DPRA methods introduce issues associated with combinatorial explosion of states. In order to address this combinatorial complexity, a branch-and-bound optimization technique is applied to the DPRA formalism to control the combinatorial state explosion. In addition, a new characteristic scaling metric (LENDIT – length, energy, number, distribution, information and time) is proposed as linear constraints that are used to guide the branch-and-bound algorithm to limit the number of possible states to be analyzed. The LENDIT characterization is divided into four groups or sets – 'state, system, resource and response' (S2R2) – describing reactor operations (normal and off-normal). In this paper we introduce the branch-and-bound DPRA approach and the application of LENDIT scales and S2R2 sets to a station blackout (SBO) transient. (author)
Highlights: • A hierarchical MILP method for optimal design of energy supply systems is proposed. • Lower bounds for the optimal value of the objective function are evaluated. • Bounding operations using the lower bounds are proposed. • The proposed method is implemented into open and commercial MILP solvers. • Validity and effectiveness of the proposed method are clarified by case studies. - Abstract: To attain the highest performance of energy supply systems, it is necessary to rationally determine types, capacities, and numbers of equipment in consideration of their operational strategies corresponding to seasonal and hourly variations in energy demands. In the combinatorial optimization method based on the mixed-integer linear programming (MILP), integer variables are used to express the selection, numbers, and on/off status of operation of equipment, and the number of these variables increases with those of equipment and periods for variations in energy demands, and affects the computation efficiency significantly. In this paper, a MILP method utilizing the hierarchical relationship between design and operation variables is proposed to solve the optimal design problem of energy supply systems efficiently: At the upper level, the optimal values of design variables are searched by the branch and bound method; At the lower level, the values of operation variables are optimized independently at each period by the branch and bound method under the values of design variables given tentatively during the search at the upper level; Lower bounds for the optimal value of the objective function to be minimized are evaluated, and are utilized for the bounding operations at both the levels. This method is implemented into open and commercial MILP solvers. Illustrative and practical case studies on the optimal design of cogeneration systems are conducted, and the validity and effectiveness of the proposed method are clarified
Disjunctive cuts in a branch-and-price algorithm for the capacitated vehicle routing problem
Røpke, Stefan
This talk presents computational results that show the usefulness of the general-purpose valid inequalities disjunctive cuts when applied to the CVRP. Results indicate that the disjunctive cuts are able to reduce the gap between lower bound and upper bound more than state-of-the-art problem speci...... specific inequalities. Results also indicate that introducing the cuts leads to a smaller branch and bound tree and faster solution times overall.......This talk presents computational results that show the usefulness of the general-purpose valid inequalities disjunctive cuts when applied to the CVRP. Results indicate that the disjunctive cuts are able to reduce the gap between lower bound and upper bound more than state-of-the-art problem...
Nuclear magnetic resonance (NMR) assignment of small molecules is presented as a typical example of a combinatorial optimization problem in chemical physics. Three strategies that help improve the efficiency of solution search by the branch and bound method are presented: 1. reduction of the size of the solution space by resort to a condensed structure formula, wherein symmetric nuclei are grouped together; 2. partitioning of the solution space based on symmetry, that becomes the basis for an efficient branching procedure; and 3. a criterion of selection of input restrictions that leads to increased gaps between branches and thus faster pruning of non-viable solutions. Although the examples chosen to illustrate this work focus on small-molecule NMR assignment, the results are generic and might help solving other combinatorial optimization problems
Interval Bound Algorithm is a well performance algorithm to optimize reactor reloading pattern problem. In order to improve the performance of the algorithm further, this paper added 'elitism strategy' to it. The numerical result showed that the improved algorithm became better than the basic algorithm in terms of both solution quality and convergence speed. Moreover, in order to solve multi-modal reloading pattern optimization problem, the multi-interval-model was added to the algorithm. The numerical result also illustrated that the re-improved algorithm was able to find multi-modal optimization solutions simultaneously without increasing of calculation load. With the two improvement measures, Interval Bound Algorithm has performed better in realistic application. (authors)
A branch-and-cut algorithm for the capacitated open vehicle routing problem
Letchford, A.N.; Lysgaard, Jens; Eglese, R.W.
2007-01-01
In open vehicle routing problems, the vehicles are not required to return to the depot after completing service. In this paper, we present the first exact optimization algorithm for the open version of the well-known capacitated vehicle routing problem (CVRP). The algorithm is based on branch...... assess the quality of existing heuristic methods, and to compare the relative difficulty of open and closed versions of the same problem....
A Branch-and-Cut Algorithm for the Capacitated Open Vehicle Routing Problem
Letchford, Adam N.; Lysgaard, Jens; Eglese, Richard W.
In open vehicle routing problems, the vehicles are not required to return to the depot after completing service. In this paper, we present the first exact optimization algorithm for the open version of the well-known capacitated vehicle routing problem (CVRP). The algorithm is based on branch...... assess the quality of existing heuristic methods, and to compare the relative difficulty of open and closed versions of the same problem....
Lower bounds for 1-, 2- and 3-dimensional on-line bin packing algorithms
G. Galambos; A. van Vliet (André)
1994-01-01
textabstractIn this paper we discuss lower bounds for the asymptotic worst case ratio of on-line algorithms for different kind of bin packing problems. Recently, Galambos and Frenk gave a simple proof of the 1.536 ... lower bound for the 1-dimensional bin packing problem. Following their ideas, we p
A Branch-and-Price Algorithm for the Capacitated Arc Routing Problem with Stochastic Demands
Christiansen, Christian Holk; Lysgaard, Jens; Wøhlk, Sanne
2009-01-01
We address the Capacitated Arc Routing Problem with Stochastic Demands (CARPSD), which we formulate as a Set Partitioning Problem. The CARPSD is solved by a Branch-and-Price algorithm, which we apply without graph transformation. The demand's stochastic nature is incorporated into the pricing pro...... problem. Computational results are reported....
Persistence-Based Branch Misprediction Bounds for WCET Analysis
Puffitsch, Wolfgang
Branch prediction is an important feature of pipelined processors to achieve high performance. However, it can lead to overly pessimistic worst-case execution time (WCET) bounds when being modeled too conservatively. This paper presents bounds on the number of branch mispredictions for local...... dynamic branch predictors. To handle interferences between branch instructions we use the notion of persistence, a concept that is also found in cache analyses. The bounds apply to branches in general, not only to branches that close a loop. Furthermore, the bounds can be easily integrated into integer...... linear programming formulations of the WCET problem. An evaluation on a number of benchmarks shows that with these bounds, dynamic branch prediction does not necessarily lead to higher WCET bounds than static prediction schemes....
Phylogenies without Branch Bounds: Contracting the Short, Pruning the Deep
Daskalakis, Constantinos; Roch, Sebastien
2008-01-01
We introduce a new phylogenetic reconstruction algorithm which, unlike most previous rigorous inference techniques, does not rely on assumptions regarding the branch lengths or the depth of the tree. The algorithm returns a forest which is guaranteed to contain all edges that are: 1) sufficiently long and 2) sufficiently close to the leaves. How much of the true tree is recovered depends on the sequence length provided. The algorithm is distance-based and runs in polynomial time.
JPLEX: Java Simplex Implementation with Branch-and-Bound Search for Automated Test Assembly
Park, Ryoungsun; Kim, Jiseon; Dodd, Barbara G.; Chung, Hyewon
2011-01-01
JPLEX, short for Java simPLEX, is an automated test assembly (ATA) program. It is a mixed integer linear programming (MILP) solver written in Java. It reads in a configuration file, solves the minimization problem, and produces an output file for postprocessing. It implements the simplex algorithm to create a fully relaxed solution and…
Parameterized Expectations Algorithm and the Moving Bounds: a comment on convergence properties
Pérez, Javier J.; A. Jesús Sánchez
2005-01-01
In this paper we analyze the convergence properties of the moving bounds algorithm to initialize the Parameterized Expectations Algorithm suggested by Maliar and Maliar (2003) [Journal of Business and Economic Statistics 1, pp. 88-92]. We carry out a Monte Carlo experiment to check its performance against some initialization alternatives based on homotopy principles. We do so within the framework of two standard neoclassical growth models. We show that: (i) speed of convergence is poor as com...
A hybrid of genetic algorithm and Fletcher-Reeves for bound constrained optimization problems
Asoke Kumar Bhunia; Pintu Pal; Samiran Chattopadhyay
2015-01-01
In this paper a hybrid algorithm for solving bound constrained optimization problems having continuously differentiable objective functions using Fletcher Reeves method and advanced Genetic Algorithm (GA) have been proposed. In this approach, GA with advanced operators has been applied for computing the step length in the feasible direction in each iteration of Fletcher Reeves method. Then this idea has been extended to a set of multi-point approximations instead of single point approximation...
Blind Deconvolution Meets Blind Demixing: Algorithms and Performance Bounds
Ling, Shuyang; Strohmer, Thomas
2015-01-01
Consider $r$ sensors, each one intends to send a function $x_i$ (e.g. a signal or image) to a receiver common to all $r$ sensors. Before transmission, each $x_i$ is multiplied by an "encoding matrix" $A_i$. During transmission each $A_ix_i$ gets convolved with a function $h_i$. The receiver records the function $y$, given by the sum of all these convolved signals. Assume that the receiver knowns all the $A_i$, but does neither know the $x_i$ nor the $h_i$. When and under which conditions is i...
Joseph W. Nielsen; Akira Tokurio; Robert Hiromoto; Jivan Khatry
2014-06-01
Traditional Probabilistic Risk Assessment (PRA) methods have been developed and are quite effective in evaluating risk associated with complex systems, but lack the capability to evaluate complex dynamic systems. These time and energy scales associated with the transient may vary as a function of transition time to a different physical state. Dynamic PRA (DPRA) methods provide a more rigorous analysis of complex dynamic systems, while complete, results in issues associated with combinatorial explosion. In order to address the combinatorial complexity arising from the number of possible state configurations and discretization of transition times, a characteristic scaling metric (LENDIT – length, energy, number, distribution, information and time) is proposed as a means to describe systems uniformly and thus provide means to describe relational constraints expected in the dynamics of a complex (coupled) systems. Thus when LENDIT is used to characterize four sets – ‘state, system, resource and response’ (S2R2) – describing reactor operations (normal and off-normal), LENDIT and S2R2 in combination have the potential to ‘branch and bound’ the state space investigated by DPRA. In this paper we introduce the concept of LENDIT scales and S2R2 sets applied to a branch-and-bound algorithm and apply the methods to a station black out transient (SBO).
A branch-and-price algorithm for the capacitated facility location problem
Klose, Andreas; Görtz, Simon
2007-01-01
The capacitated facility location problem (CFLP) is a well-known combinatorial optimization problem with applications in distribution and production planning. It consists in selecting plant sites from a finite set of potential sites and in allocating customer demands in such a way as to minimize...... operating and transportation costs. A number of solution approaches based on Lagrangean relaxation and subgradient optimization has been proposed for this problem. Subgradient optimization does not provide a primal (fractional) optimal solution to the corresponding master problem. However, in order to...... compute optimal solutions to large or difficult problem instances by means of a branch-and-bound procedure information about such a primal fractional solution can be advantageous. In this paper, a (stabilized) column generation method is, therefore, employed in order to solve a corresponding master...
Kim, Nam-Geun; Park, Youngsu; Kim, Jong-Wook; Kim, Eunsu; Kim, Sang Woo
In this paper, we present a recently developed pattern search method called Genetic Pattern Search algorithm (GPSA) for the global optimization of cost function subject to simple bounds. GPSA is a combined global optimization method using genetic algorithm (GA) and Digital Pattern Search (DPS) method, which has the digital structure represented by binary strings and guarantees convergence to stationary points from arbitrary starting points. The performance of GPSA is validated through extensive numerical experiments on a number of well known functions and on robot walking application. The optimization results confirm that GPSA is a robust and efficient global optimization method.
The first experimental observation of bound-state beta-decay showed, that due solely to the electron stripping, a stable nuclide, e.g. 163Dy, became unstable. Also a drastic modification of the half-life of bare 187Re, from 4.12(2) x 1010 years down to 32.9(20) years, could be observed. It was mainly due to the possibility for the mother nuclide to decay into a previously inaccessible nuclear level of the daughter nuclide. It was proposed to study a nuclide where this decay mode was competing with continuum-state beta-decay, in order to measure their respective branchings. The ratio βb/βc could also be evaluated for the first time. 207Tl was chosen due to its high atomic number, and Q-value of about 1.4 MeV, small enough to enhance the βb probability and large enough to allow the use of time-resolved Schottky Mass Spectrometry (SMS) to study the evolution of mother and bound-state beta-decay daughter ions. The decay properties of the ground state and isomeric state of 207Tl81+ have been investigated at the GSI accelerator facility in two separate experiments. For the first time β-decay where the electron could go either to a bound state (atomic orbitals) and lead to 207Pb81+ as a daughter nuclide, or to a continuum state and lead to 207Pb82+, has been observed. The respective branchings of these two processes could be measured as well. The deduced total nuclear half-life of 255(17) s for 207Tl81+, was slightly modified with respect to the half-life of the neutral atom of 286(2) s. It was nevertheless in very good agreement with calculations based on the assumption that the beta-decay was following an allowed type of transition. The branching βb/βc=0.192(20), was also in very good agreement with the same calculations. The application of stochastic precooling allowed to observe in addition the 1348 keV short-lived isomeric state of 207Tl. The half-life of this isomeric state was measured as 1.47(32) s, which shows a small deviation compared to the half-life for
Highlights: → A hybrid SCUC solution is developed to deal with large-scale, real-time and long-term problems. → New formulations are proposed for considering valve point effect and warmth-dependent start-up cost. → A new algorithm is developed for modeling the AC power flow in SCUC problems. → Using the power flow algorithm both steps in traditional SCUC is done simultaneously. → The proposed method provides better solutions than previous ones with a fast speed. - Abstract: In this paper, a new practical method is presented for solving the non-convex security constraint unit commitment (SCUC) problem in power systems. The accuracy of the proposed method is desirable while the shorter computation time makes it useful for SCUC solution of large-scale power systems, real-time market operation and long-term SCUC problems. The proposed framework allows inclusion of the valve point effects, warmth-dependent start-up costs, ramp rates, minimum up/down time constraints, multiple fuels costs, emission costs, prohibited operating zones and AC power flow limits in normal and contingency conditions. To solve the non-convex problem, combination of a modified Branch-and-Bound method with the Quadratic Programming is used as an optimization tool and a developed AC power flow algorithm is applied for considering the security and contingency concerns using the nonlinear/linear AC model. These modifications improve the convergence speed and solution precision of SCUC problem. In the proposed method, in contrast with traditional SCUC algorithms, unit commitment solution, checking and satisfying the security constraints are managed simultaneously. The obtained results are compared with other reported methods for investigating the effectiveness of the proposed method. Also, the proposed method is applied to an Iranian power system including 493 thermal units.
A hybrid of genetic algorithm and Fletcher-Reeves for bound constrained optimization problems
Asoke Kumar Bhunia
2015-04-01
Full Text Available In this paper a hybrid algorithm for solving bound constrained optimization problems having continuously differentiable objective functions using Fletcher Reeves method and advanced Genetic Algorithm (GA have been proposed. In this approach, GA with advanced operators has been applied for computing the step length in the feasible direction in each iteration of Fletcher Reeves method. Then this idea has been extended to a set of multi-point approximations instead of single point approximation to avoid the convergence of the existing method at local optimum and a new method, called population based Fletcher Reeves method, has been proposed to find the global or nearer to global optimum. Finally to study the performance of the proposed method, several multi-dimensional standard test functions having continuous partial derivatives have been solved. The results have been compared with the same of recently developed hybrid algorithm with respect to different comparative factors.
A branch-and-cut algorithm for the capacitated profitable tour problem
Jepsen, Mads Kehlet; Petersen, Bjørn; Spoorendonk, Simon;
2014-01-01
This paper considers the Capacitated Profitable Tour Problem (CPTP) which is a special case of the Elementary Shortest Path Problem with Resource Constraints (ESPPRC). The CPTP belongs to the group of problems known as traveling salesman problems with profits. In CPTP each customer is associated...... with a profit and a demand and the objective is to find a capacitated tour (rooted in a depot node) that minimizes the total travel distance minus the profit of the visited customers. The CPTP can be recognized as the sub-problem in many column generation applications, where it is traditionally solved...... instances with 800 nodes to optimality where the dynamic programming algorithms cannot solve instances with more than 200 nodes. Moreover dynamic programming and branch-and-cut complement each other well, giving us hope for solving more general problems through hybrid approaches. The paper is intended to...
Frecon, Jordan; Didier, Gustavo; Pustelnik, Nelly; Abry, Patrice
2016-08-01
Self-similarity is widely considered the reference framework for modeling the scaling properties of real-world data. However, most theoretical studies and their practical use have remained univariate. Operator Fractional Brownian Motion (OfBm) was recently proposed as a multivariate model for self-similarity. Yet it has remained seldom used in applications because of serious issues that appear in the joint estimation of its numerous parameters. While the univariate fractional Brownian motion requires the estimation of two parameters only, its mere bivariate extension already involves 7 parameters which are very different in nature. The present contribution proposes a method for the full identification of bivariate OfBm (i.e., the joint estimation of all parameters) through an original formulation as a non-linear wavelet regression coupled with a custom-made Branch & Bound numerical scheme. The estimation performance (consistency and asymptotic normality) is mathematically established and numerically assessed by means of Monte Carlo experiments. The impact of the parameters defining OfBm on the estimation performance as well as the associated computational costs are also thoroughly investigated.
AnkurPachauriand Gursaran
2012-01-01
In search based test data generation, the problem of test data generation is reduced to that of function minimization or maximization.Traditionally, for branch testing, the problem of test data generation has been formulated as a minimization problem. In this paper we define an alternate maximization formulation and experimentally compare it with the minimization formulation. We use a genetic algorithm as the search technique and in addition to the usual genetic algorithm opera...
Comparing branch-and-price algorithms for the Multi-Commodity k-splittable Maximum Flow Problem
Gamst, Mette; Petersen, Bjørn
2012-01-01
, shows some performance difficulty due to large search trees. The second method, which branches on forbidden and forced edge sequences, demonstrates much better performance. The latter also outperforms a leading exact solution method from the literature. Furthermore, a heuristic algorithm is presented....... The heuristic is fast and yields good solution values. (C) 2011 Elsevier B.V. All rights reserved....
Robenek, Tomáš; Umang, Nitish; Bierlaire, Michel;
2014-01-01
In this research, two crucial optimization problems of berth allocation and yard assignment in the context of bulk ports are studied. We discuss how these problems are interrelated and can be combined and solved as a single large scale optimization problem. More importantly we highlight the...... differences in operations between bulk ports and container terminals which highlights the need to devise specific solutions for bulk ports. The objective is to minimize the total service time of vessels berthing at the port. We propose an exact solution algorithm based on a branch and price framework to solve......-shaking neighborhood search is presented. The proposed algorithms are tested and validated through numerical experiments based on instances inspired from real bulk port data. The results indicate that the algorithms can be successfully used to solve instances containing up to 40 vessels within reasonable computational...
Refined Error Bounds for Several Learning Algorithms
Hanneke, Steve
2015-01-01
This article studies the achievable guarantees on the error rates of certain learning algorithms, with particular focus on refining logarithmic factors. Many of the results are based on a general technique for obtaining bounds on the error rates of sample-consistent classifiers with monotonic error regions, in the realizable case. We prove bounds of this type expressed in terms of either the VC dimension or the sample compression size. This general technique also enables us to derive several ...
Properties of branching exponential flights in bounded domains
In a series of recent works, important results have been reported concerning the statistical properties of exponential flights evolving in bounded domains, a widely adopted model for finite-speed transport phenomena (Blanco S. and Fournier R., Europhys. Lett., 61 (2003) 168; Mazzolo A., Europhys. Lett., 68 (2004) 350; Benichou O. et al., Europhys. Lett., 70 (2005) 42). Motivated by physical and biological systems where random spatial displacements are coupled with Galton-Watson birth-death mechanisms, such as neutron multiplication, diffusion of reproducing bacteria or spread of epidemics, in this letter we extend those results in two directions, via a Feynman-Kac formalism. First, we characterize the occupation statistics of exponential flights in the presence of absorption and branching, and give explicit moment formulas for the total length travelled by the walker and the number of performed collisions in a given domain. Then, we show that the survival and escape probability can be derived as well by resorting to a similar approach. (authors)
Zhou, YuQian
2012-01-01
This paper proposes a method to find efficient bounded algorithms of NPC problems by machine enumeration. The key contributions are: * On Universal Turing Machines, a program's time complexity should be characterized as: execution time(n) = loading time(n) + running time(n). * Introduces the concept of bounded algorithms; proposes a comparison based criterion to decide if a bounded algorithm is inefficient; and establishes the length upper bound of efficient bounded programs. * Introduces a new way to evaluate program complexity by using the growth rate characteristic function, which is more easily machine checkable based on observations.
Algorithms for Quantum Branching Programs Based on Fingerprinting
Ablayev, Farid; 10.4204/EPTCS.9.1
2009-01-01
In the paper we develop a method for constructing quantum algorithms for computing Boolean functions by quantum ordered read-once branching programs (quantum OBDDs). Our method is based on fingerprinting technique and representation of Boolean functions by their characteristic polynomials. We use circuit notation for branching programs for desired algorithms presentation. For several known functions our approach provides optimal QOBDDs. Namely we consider such functions as Equality, Palindrome, and Permutation Matrix Test. We also propose a generalization of our method and apply it to the Boolean variant of the Hidden Subgroup Problem.
New physics upper bound on the branching ratio of B_s--> l+ l- and B_s--> l+ l- gamma
Alok, A K; Alok, Ashutosh Kumar
2007-01-01
We consider the most general new physics effective Lagrangian for b--> s l+ l-. We derive the upper limit on the branching ratio for the processes B_s--> l^+ l- where l=e, mu, subject to the current experimental bounds on related processes, B--> (K,K*) l+ l-. If the new physics interactions are of vector/axial-vector form, the present measured rates for B--> (K,K*) l+ l- constrain B_s--> l+ l to be of the same order of magnitude as their respective Standard Model (SM) predictions. On the other hand, if the new physics interactions are of scalar/pseudoscalar form, B--> (K,K*) l+ l- rates do not impose any useful constraint on B_s--> l+ l- and the branching ratios of these decays can be as large as present experimental upper bounds. If future experiments measure B_s--> l+ l- to be > 10^{-8} then the new physics giving rise to these decays has to be of the scalar/pseudoscalar form. We also consider the effect of new physics on B_s--> l+ l- gamma subject to the present experimental constraints on B--> (K,K*) l+ l...
R Ball; Lee, J.
1996-01-01
We prove that a new, irreversible growth algorithm, Non-Deletion Reaction-Limited Cluster-cluster Aggregation (NDRLCA), produces equilibrium Branched Polymers, expected to exhibit Lattice Animal statistics [1]. We implement NDRLCA, off-lattice, as a computer simulation for embedding dimension d=2 and 3, obtaining values for critical exponents, fractal dimension D and cluster mass distribution exponent τ: d=2,D≈1.53±0.05,τ= 1.09±0.06; d=3,D=1.96±0.04,τ=1.50±0.04 in good agreement with theoreti...
A fast and simple branching algorithm for solving small scale fixed-charge transportation problem
Krzysztof Kowalski; Benjamin Lev; Wenjing Shen; Yan Tu
2014-01-01
In this paper, we develop a simple algorithm for obtaining the global solution to a small scale fixed-charge transportation problem (FCTP). The procedure itself is very quick. The proposed method solves FCTP by decomposing the problem into series of smaller sub-problems, which is novel and can be useful to researchers solving any size of the problem.
A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands
Christiansen, Christian Holk; Lysgaard, Jens
This article introduces a new exact algorithm for the Capacitated Vehicle Routing Problem with Stochastic Demands (CVRPSD). The CVRPSD can be formulated as a Set Partitioning Problem and it is shown that the associated column generation subproblem can be solved using a dynamic programming scheme....... Computational experiments show promising results....
A Branch and Cut algorithm for the container shipping network design problem
Reinhardt, Line Blander; Kallehauge, Brian; Pisinger, David
The network design problem in liner shipping is of increasing importance in a strongly competitive market where potential cost reductions can influence market share and profits significantly. In this paper the network design and fleet assignment problems are combined into a mixed integer linear...... programming model minimizing the overall cost. To better reflect the real-life situation we take into account the cost of transhipment, a heterogeneous fleet, route dependant capacities, and butterfly routes. To the best of our knowledge it is the first time an exact solution method to the problem considers...... transhipment cost. The problem is solved with branch-and-cut using clover and transhipment inequalities. Computational results are reported for instances with up to 15 ports....
Nghia, Nguyen Duc; Binh, Huynh Thi Thanh
2008-01-01
We have introduced the heuristic algorithm for solving BDMST problem, called CBRC. The experiment shows that CBRC have best result than the other known heuristic algorithm for solving BDMST prolem on Euclidean instances. The best solution found by the genetic algorithm which uses best heuristic algorithm or only one heuristic algorithm for initialization the population is not better than the best solution found by the genetic algorithm which uses mixed heuristic algorithms (randomized heurist...
Cramér-Rao Bounds and Estimation Algorithms for Delay/Doppler and Conventional Altimetry
Halimi, Abderrahim; Mailhes, Corinne; Tourneret, J. -Y.
2013-01-01
International audience Delay/Doppler radar altimetry has been receiving an increasing interest, especially since the launch of the first altimeter in 2010. It aims at reducing the measurement noise and increasing the along-track resolution in comparison with conventional pulse limited altimetry. A semi-analytical model was recently introduced for this new generation of delay/Doppler altimeters. The first contribution of this paper is the derivation of the Cramér-Rao bounds (CRBs) associat...
Çağlar, F; Ozbek, I Y
2012-01-01
Heart sound localization in chest sound is an essential part for many heart sound cancellation algorithms. The main difficulty for heart sound localization methods is the precise determination of the onset and offset boundaries of the heart sound segment. This paper presents a novel method to estimate lower and upper bounds for the onset and offset of the heart sound segment, which can be used as anchor points for more precise estimation. For this purpose, first chest sound is divided into frames and then entropy and smoothed entropy features of these frames are extracted, and used in the Convex-hull algorithm to estimate the upper and lower bounds for heart sound boundaries. The Convex-hull algorithm constructs a special type of envelope function for entropy features and if the maximal difference between the envelope function and the entropy is larger than a certain threshold, this point is considered as a heart sound bound. The results of the proposed method are compared with a baseline method which is a modified version of a well-known heart sound localization method. The results show that the proposed method outperforms the baseline method in terms of accuracy and detection error rate. Also, the experimental results show that smoothing entropy features significantly improves the performance of both baseline and proposed methods. PMID:23366867
New physics upper bound on the branching ratio of B_s --> l+ l-
Alok, A K; Alok, Ashutosh Kumar
2005-01-01
We consider new physics interactions for b --> s l+ l- of the form vector/axial-vector. We derive the upper limit on the branching ratio for the processes B_s --> l+ l-, where l=e or mu, subject to the current experimental bounds on related processes, B --> K l+ l- and B --> K* l+ l-. We obtain 3 sigma upper bounds B(B_s --> e+ e-) mu+ mu-) < 5*10^(-9).
A branch-and-price algorithm for the long-term home care scheduling problem
Gamst, Mette; Jensen, Thomas Sejr
2012-01-01
In several countries, home care is provided for certain citizens living at home. The long-term home care scheduling problem is to generate work plans such that a high quality of service is maintained, the work hours of the employees are respected, and the overall cost is kept as low as possible. We...... propose a branchand-price algorithm for the long-term home care scheduling problem. The pricing problem generates a one-day plan for an employee, and the master problem merges the plans with respect to regularity constraints. The method is capable of generating plans with up to 44 visits during one week....
A New Bound for 3-Satisfiable MaxSat and its Algorithmic Application
Gutin, Gregory; Yeo, Anders
2011-01-01
Let $F$ be a CNF formula with $n$ variables and $m$ clauses. $F$ is $t$-satisfiable if for any $t$ clauses in $F$, there is a truth assignment which satisfies all of them. Lieberherr and Specker (1982) and, later, Yannakakis (1994) proved that in each 3-satisfiable CNF formula at least 2/3 of its clauses can be satisfied by a truth assignment. Yannakakis's proof utilizes the fact that 2/3 m$ is a lower bound on the expected number of clauses satisfied by a random truth assignment over a certain distribution. A CNF formula $F$ is called \\emph{expanding} if for every subset $X$ of the variables of $F$, the number of clauses containing variables of $X$ is not smaller than $|X|.$ In this paper we strengthen the 2/3 m bound by showing that, for every expanding 3-satisfiable CNF formula $F$, at least 2/3 m + \\rho n$ clauses of $F$ can be satisfied by a truth assignment, where $\\rho(>0.0019)$ is a constant. Our proof uses the probabilistic method with a sophisticated distribution for truth values. We use the bound 2...
Ait moussa, Abdellah; Jassemnejad, Bahaeddin
2014-05-01
Nanocomposites with high-aspect ratio fillers attract enormous attention because of the superior physical properties of the composite over the parent matrix. Nanocomposites with functionalized graphene as fillers did not produce the high thermal conductivity expected due to the high interfacial thermal resistance between the functional groups and graphene flakes. We report here a robust and efficient technique that identifies the configuration of the functionalities for improved thermal conductivity. The method combines linearization of the interatomic interactions, calculation, and optimization of the thermal conductivity using the globalized and bounded Nelder-Mead algorithm.
, number, distribution, information and time) is proposed as a means to describe systems uniformly and thus provide means to describe relational constraints expected in the dynamics of a complex (coupled) systems. Thus when LENDIT is used to characterize four sets - 'state, system, resource and response' (S2R2) - describing reactor operations (normal and off-normal), LENDIT and S2R2 in combination have the potential to 'branch and bound' the state space investigated by DPRA. LENDIT and S2R2 provide a consisting methodology across both deterministic and heuristic domains. This paper explores the reduction of a PWR's state-space using a RELAP5 model of a plant subject to a SBO. We introduce LENDIT metrics and S2R2 sets to show the branch-and-bound concept. (author)
Hadi Mokhtari
2013-01-01
Full Text Available In this paper, the problem of received order scheduling by a manufacturer, with the measure of maximum completion times of orders, has been formulated and then an analytical approach has been devised for its solution. At the beginning of a planning period, the manufacturer receives a number of orders from customers, each of which requires two different stages for processing. In order to minimize the work in process inventories, the no-wait condition between two operations of each order is regarded. Then, the equality of obtained schedules is proved by machine idle time minimization, as objective, with the schedules obtained by maximum completion time minimization. A concept entitled “Order pairing” has been defined and an algorithm for achieving optimal order pairs which is based on symmetric assignment problem has been presented. Using the established order pairs, an upper bound has been developed based on contribution of every order pair out of total machines idle time. Out of different states of improving upper bound, 12 potential situations of order pairs sequencing have been also evaluated and then the upper bound improvement has been proved in each situation, separately. Finally, a heuristic algorithm has been developed based on attained results of pair improvement and a case study in printing industry has been investigated and analyzed to approve its applicability.
Boutin, D.
2005-08-01
The first experimental observation of bound-state beta-decay showed, that due solely to the electron stripping, a stable nuclide, e.g. {sup 163}Dy, became unstable. Also a drastic modification of the half-life of bare {sup 187}Re, from 4.12(2) x 10{sup 10} years down to 32.9(20) years, could be observed. It was mainly due to the possibility for the mother nuclide to decay into a previously inaccessible nuclear level of the daughter nuclide. It was proposed to study a nuclide where this decay mode was competing with continuum-state beta-decay, in order to measure their respective branchings. The ratio {beta}{sub b}/{beta}{sub c} could also be evaluated for the first time. {sup 207}Tl was chosen due to its high atomic number, and Q-value of about 1.4 MeV, small enough to enhance the {beta}{sub b} probability and large enough to allow the use of time-resolved Schottky Mass Spectrometry (SMS) to study the evolution of mother and bound-state beta-decay daughter ions. The decay properties of the ground state and isomeric state of {sup 207}Tl{sup 81+} have been investigated at the GSI accelerator facility in two separate experiments. For the first time {beta}-decay where the electron could go either to a bound state (atomic orbitals) and lead to {sup 207}Pb{sup 81+} as a daughter nuclide, or to a continuum state and lead to {sup 207}Pb{sup 82+}, has been observed. The respective branchings of these two processes could be measured as well. The deduced total nuclear half-life of 255(17) s for {sup 207}Tl{sup 81+}, was slightly modified with respect to the half-life of the neutral atom of 286(2) s. It was nevertheless in very good agreement with calculations based on the assumption that the beta-decay was following an allowed type of transition. The branching {beta}{sub b}/{beta}{sub c}=0.192(20), was also in very good agreement with the same calculations. The application of stochastic precooling allowed to observe in addition the 1348 keV short-lived isomeric state of {sup
Artigues, Christian; Gendreau, Michel; Rousseau, Louis-Martin; Vergnaud, Adrien
2009-01-01
We propose exact hybrid methods based on integer linear programming and constraint programming for an integrated employee timetabling and job-shop scheduling problem. Each method we investigate uses a constraint programming (CP) formulation associated with a linear programming (LP) relaxation. Under a CP framework, the LP-relaxation is integrated into a global constraint using in addition reduced cost-based filtering techniques. We propose two CP formulations of the problem yielding two diffe...
Improved branch and bound algorithm for detecting SNP-SNP interactions in breast cancer
Chuang, Li-Yeh; Chang, Hsueh-Wei; Lin, Ming-Cheng; Yang, Cheng-Hong
2013-01-01
Background Single nucleotide polymorphisms (SNPs) in genes derived from distinct pathways are associated with a breast cancer risk. Identifying possible SNP-SNP interactions in genome-wide case–control studies is an important task when investigating genetic factors that influence common complex traits; the effects of SNP-SNP interaction need to be characterized. Furthermore, observations of the complex interplay (interactions) between SNPs for high-dimensional combinations are still computati...
Pebbles and Branching Programs for Tree Evaluation
Cook, Stephen; Wehr, Dustin; Braverman, Mark; Santhanam, Rahul
2010-01-01
We introduce the Tree Evaluation Problem, show that it is in logDCFL (and hence in P), and study its branching program complexity in the hope of eventually proving a superlogarithmic space lower bound. The input to the problem is a rooted, balanced d-ary tree of height h, whose internal nodes are labeled with d-ary functions on [k] = {1,...,k}, and whose leaves are labeled with elements of [k]. Each node obtains a value in [k] equal to its d-ary function applied to the values of its d children. The output is the value of the root. We show that the standard black pebbling algorithm applied to the binary tree of height h yields a deterministic k-way branching program with Theta(k^h) states solving this problem, and we prove that this upper bound is tight for h=2 and h=3. We introduce a simple semantic restriction called "thrifty" on k-way branching programs solving tree evaluation problems and show that the same state bound of Theta(k^h) is tight (up to a constant factor) for all h >= 2 for deterministic thrift...
LIU Xiao; WANG Cheng-en
2005-01-01
This paper addresses a single item dynamic lot-sizing model with inventory capacity and out-sourcing. The goal is to minimize the total costs of production, setup, inventory holding and out-sourcing. Two versions of an out-sourcing model with time-varying costs are considered: stock out case and conservation case. Zero Inventory Order property has been found and some new properties are obtained in an optimal solution. Dynamic programming algorithms are developed to solve the problem in strongly polynomial time respectively. Furthermore, some numerical results demonstrate that the approach proposed is efficient and applicable.
Upper and lower bounds for disadvantage factors as a test of algorithm used in a synthesis method
A lower bound for the disadvantage factor of a lattice cell of arbitrary configuration is obtained using a finite element method which is based on a variational principle for the even-parity angular flux. An upper bound for the disadvantage factor is given by a finite element method using the complementary variational principle for the odd-parity angular flux. These theoretical results are illustrated by calculations for uranium/graphite and uranium/water lattices. As the approximations are refined the fluxes obtained by the first method tend towards the actual flux from below in the moderator, and from above in the fuel. These trends are reversed for the second method. This derivation of benchmarks for disadvantage factors has been undertaken primarily as a test of an important algorithm used by the authors in a method of synthesising transport solutions starting with a diffusion theory approximation. The algorithm is used to convert odd-parity approximations for the angular flux into even-parity approximations and vice versa. (author). 15 refs., 8 tabs., 9 figs
Bisheng He
2014-01-01
Full Text Available A time-space network based optimization method is designed for high-speed rail train timetabling problem to improve the service level of the high-speed rail. The general time-space path cost is presented which considers both the train travel time and the high-speed rail operation requirements: (1 service frequency requirement; (2 stopping plan adjustment; and (3 priority of train types. Train timetabling problem based on time-space path aims to minimize the total general time-space path cost of all trains. An improved branch-and-price algorithm is applied to solve the large scale integer programming problem. When dealing with the algorithm, a rapid branching and node selection for branch-and-price tree and a heuristic train time-space path generation for column generation are adopted to speed up the algorithm computation time. The computational results of a set of experiments on China’s high-speed rail system are presented with the discussions about the model validation, the effectiveness of the general time-space path cost, and the improved branch-and-price algorithm.
New physics upper bound on the branching ratio of B_s--> l+ l- and B_s--> l+ l- gamma
Alok, Ashutosh Kumar; Sankar, S. Uma
2006-01-01
We consider the most general new physics effective Lagrangian for b--> s l+ l-. We derive the upper limit on the branching ratio for the processes B_s--> l^+ l- where l=e, mu, subject to the current experimental bounds on related processes, B--> (K,K*) l+ l-. If the new physics interactions are of vector/axial-vector form, the present measured rates for B--> (K,K*) l+ l- constrain B_s--> l+ l to be of the same order of magnitude as their respective Standard Model (SM) predictions. On the othe...
Better Polynomial Algorithms on Graphs of Bounded Rank-Width
Ganian, Robert; Hliněný, Petr
Although there exist many polynomial algorithms for NP-hard problems running on a bounded clique-width expression of the input graph, there exists only little comparable work on such algorithms for rank-width. We believe that one reason for this is the somewhat obscure and hard-to-grasp nature of rank-decompositions. Nevertheless, strong arguments for using the rank-width parameter have been given by recent formalisms independently developed by Courcelle and Kanté, by the authors, and by Bui-Xuan et al. This article focuses on designing formally clean and understandable "pseudopolynomial" (XP) algorithms solving "hard" problems (non-FPT) on graphs of bounded rank-width. Those include computing the chromatic number and polynomial or testing the Hamiltonicity of a graph and are extendable to many other problems.
New Facets and a Branch-and-Cut Algorithm for the Weighted Clique Problem
Sørensen, Michael Malmros
2001-01-01
We consider a polyhedral approach to the weighted maximal b-clique problem. Given a node- and edge-weighted complete graph the problem is to find a complete subgraph (clique) with no more than b nodes such that the sum of the weights of all nodes and edges in the clique is maximal. We introduce...... four new classes of facet defining inequalities for the associated b-clique polytope. One of these inequality classes constitutes a generalization of the well known tree inequalities; the other classes are associated with multistars. We utilize these inequality classes together with other classes of...
New facets and a branch-and-cut algorithm for the weighted clique problem
Sørensen, Michael Malmros
2004-01-01
We consider a polyhedral approach to the weighted maximal b-clique problem. Given a node- and edge-weighted complete graph the problem is to find a complete subgraph (clique) with no more than b nodes such that the sum of the weights of all nodes and edges in the clique is maximal. We introduce...... four new classes of facet defining inequalities for the associated b-clique polytope. One of these inequality classes constitutes a generalization of the well known tree inequalities; the other classes are associated with multistars. We use these inequalities together with other classes of facet...
Formulations and Branch-and-Cut Algorithms for the Generalized Vehicle Routing Problem
Bektas, Tolga; Erdogan, Günes; Røpke, Stefan
2011-01-01
The Generalized Vehicle Routing Problem (GVRP) consists of nding a set of routes for a number of vehicles with limited capacities on a graph with the vertices partitioned into clusters with given demands such that the total cost of travel is minimized and all demands are met. This paper offers four...
A Branch and Cut algorithm for the container shipping network design problem
Reinhardt, Line Blander; Kallehauge, Brian; Pisinger, David
2010-01-01
The network design problem in liner shipping is of increasing importance in a strongly competitive market where potential cost reductions can influence market share and profits significantly. In this paper the network design and fleet assignment problems are combined into a mixed integer linear programming model minimizing the overall cost. To better reflect the real-life situation we take into account the cost of transhipment, a heterogeneous fleet, route dependant capacities, and butterfly ...
A Branch and Cut algorithm for the container shipping network design problem
Reinhardt, Line Blander; Pisinger, David
2012-01-01
The network design problem in liner shipping is of increasing importance in a strongly competitive market where potential cost reductions can influence market share and profits significantly. In this paper the network design and fleet assignment problems are combined into a mixed integer linear...
A General Nonlinear Optimization Algorithm for Lower Bound Limit Analysis
Krabbenhøft, Kristian; Damkilde, Lars
2003-01-01
finite element discretization or yield criterion is required. As with interior point methods for linear programming the number of iterations is affected only little by the problem size. Some practical implementation issues are discussed with reference to the special structure of the common lower bound......The non-linear programming problem associated with the discrete lower bound limit analysis problem is treated by means of an algorithm where the need to linearize the yield criteria is avoided. The algorithm is an interior point method and is completely general in the sense that no particular...... load optimization problem, and finally the efficiency and accuracy of the method is demonstrated by means of examples of plate and slab structures obeying different non-linear yield criteria....
Branch-and-cut-and-price for the traveling salesman problem with time windows
Røpke, Stefan; Madsen, Oli B.G.
paradigms such as branch-and-cut, dynamic programming and constraint programming. We cannot conclude that the branch-and-cut-and-price approach always is superior to the others paradigms, but several instances are reported solved to optimality for the rst time and bounds are strengthened for other, still...... generation process converges slowly for the problem and therefore a stabilization procedure is implemented. Valid inequalities expressed in the original, arc-based variables are added to the LP relaxation to strengthen the lower bound. The proposed algorithm is compared to exact algorithms based on other...
Kohei Arai
2012-01-01
Method for visualization of URL link structure and URL retrievals using internal structure of URLs based on brunch and bound method is proposed. Twisting link structure of URLs can be solved by the proposed visualization method. Also some improvements are observed for the proposed brunch and bound based method in comparison to the conventional URL retrieval methods.
Friel, Thilo-Thomas; Harrison, R.
1998-01-01
Three novel algorithms are presented; the linear programming (LP) machine for pattern classification, the LP machine for regression estimation and the set-reduction (SR) algorithm. The LP machine is a learning machine which achieves solutions as good as the SV machine by only maximising a linear cost-function (SV machine are based on quadratic programming). The set-reduction algorithm improves the speed and accuracy of LP machines, SV machines and other related algorithms. An LP machines's de...
Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem
Fukasawa, R.; Longo, H.; Lysgaard, Jens; Poggi de Aragão, M.; Reis, M.; Uchoa, E.; Werneck, R.F.
2006-01-01
traditional Lagrangean relaxation over q-routes, the other defined by bound, degree and capacity constraints. This is equivalent to a linear program with exponentially many variables and constraints that can lead to lower bounds that are superior to those given by previous methods. The resulting branch......The best exact algorithms for the Capacitated Vehicle Routing Problem (CVRP) have been based on either branch-and-cut or Lagrangean relaxation/column generation. This paper presents an algorithm that combines both approaches: it works over the intersection of two polytopes, one associated with a...
R. Freling (Richard); R.M. Lentink (Ramon); A.P.M. Wagelmans (Albert)
2001-01-01
textabstractThis paper discusses a decision support system for airline and railway crew planning. The system is a state-of-the-art branch-and-price solver that is used for crew scheduling and crew rostering. We briefly discuss the mathematical background of the solver, of which most part is covered
Improved Bounds on Quantum Learning Algorithms
Atici, A; Atici, Alp; Servedio, Rocco A.
2004-01-01
In this article we give several new results on the complexity of algorithms that learn Boolean functions from quantum queries and quantum examples. Hunziker et al. conjectured that for any class C of Boolean functions, the number of quantum black-box queries which are required to exactly identify an unknown function from C is at most $O(\\frac{\\log |C|}{\\sqrt{{\\hat{\\gamma}}^{C}}})$, where $\\hat{\\gamma}^{C}$ is a combinatorial parameter of the class C. We essentially resolve this conjecture in the affirmative by giving a quantum algorithm that, for any class C, identifies any unknown function from C using at most $O(\\frac{\\log |C| \\log \\log |C|}{\\sqrt{{\\hat{\\gamma}}^{C}}})$ quantum black-box queries. We consider a range of natural problems intermediate between the exact learning problem (in which the learner must obtain all bits of information about the black-box function) and the usual problem of computing a predicate (in which the learner must obtain only one bit of information about the black-box function). ...
New physics upper bound on the branching ratio of B_s --> l+ l-
Alok, Ashutosh Kumar; Sankar, S. Uma
2005-01-01
We consider the most general new physics effective Lagrangian for b --> s l+ l-. We derive the upper limit on the branching ratio for the processes B_s --> l+ l- where l=e, mu, subject to the current experimental bounds on related processes, B --> K l+ l- and B --> K* l+ l-. If the new physics interactions are of vector/axial-vector form, the present measured rates for B --> (K,K*) l+ l- constrain B(B_s --> l+ l-) to be of the same order of magnitude as their respective Standard Model predict...
Freling, Richard; Lentink, Ramon; Wagelmans, Albert
2001-01-01
textabstractThis paper discusses a decision support system for airline and railway crew planning. The system is a state-of-the-art branch-and-price solver that is used for crew scheduling and crew rostering. We briefly discuss the mathematical background of the solver, of which most part is covered in the Operations Research literature. Crew scheduling is crew planning for one or a few days that results in crew duties or pairings, and crew rostering is crew planning for at least one week for ...
Dinesh Gupta
2012-03-01
Full Text Available Various sheduling algorithm are available forthe operating system to improve CPU utilization.Different scheduling algorithms have differentproperties that work on different schedulingcriterias and the choice of a particular algorithmmay favor one class of processes over another.SJF gives minimum average waiting time for agiven set of processes. The Round Robinalgorithm decreases the response time. In thispaper we have proposed an algorithm which hasresponse time aproximately zero and itincreases the efficiency of I/O boundedprocess.
Analysis of the contact graph routing algorithm: Bounding interplanetary paths
Birrane, Edward; Burleigh, Scott; Kasch, Niels
2012-06-01
Interplanetary communication networks comprise orbiters, deep-space relays, and stations on planetary surfaces. These networks must overcome node mobility, constrained resources, and significant propagation delays. Opportunities for wireless contact rely on calculating transmit and receive opportunities, but the Euclidean-distance diameter of these networks (measured in light-seconds and light-minutes) precludes node discovery and contact negotiation. Propagation delay may be larger than the line-of-sight contact between nodes. For example, Mars and Earth orbiters may be separated by up to 20.8 min of signal propagation time. Such spacecraft may never share line-of-sight, but may uni-directionally communicate if one orbiter knows the other's future position. The Contact Graph Routing (CGR) approach is a family of algorithms presented to solve the messaging problem of interplanetary communications. These algorithms exploit networks where nodes exhibit deterministic mobility. For CGR, mobility and bandwidth information is pre-configured throughout the network allowing nodes to construct transmit opportunities. Once constructed, routing algorithms operate on this contact graph to build an efficient path through the network. The interpretation of the contact graph, and the construction of a bounded approximate path, is critically important for adoption in operational systems. Brute force approaches, while effective in small networks, are computationally expensive and will not scale. Methods of inferring cycles or other librations within the graph are difficult to detect and will guide the practical implementation of any routing algorithm. This paper presents a mathematical analysis of a multi-destination contact graph algorithm (MD-CGR), demonstrates that it is NP-complete, and proposes realistic constraints that make the problem solvable in polynomial time, as is the case with the originally proposed CGR algorithm. An analysis of path construction to complement hop
Lipschitz bounds for noise robustness in compressive sensing: two algorithms
Nicodème, Marc; Dossal, Charles; Turcu, Flavius; Berthoumieu, Yannick
2014-01-01
The paper deals with estimating the local noise robustness in a compressive sensing framework. We provide two algorithms which estimate, for each vector x that can be recovered by $\\ell^1$ minimization, the Lipschitz bounds relating the $\\ell^1$-reconstruction error to the measurement error (or noise) for a given sensing matrix. Classical theoretical estimations, such as those based on the restricted isometry property, theoretically give error bounds estimates depending on RIP constants. Unfo...
Koenigs function and branching processes
Tchikilev, O. G.
2001-01-01
An explicit solution of time-homogeneous pure birth branching processes is described. It gives alternative extensions for the negative binomial distribution (branching processes with immigration) and for the Furry-Yule distribution (branching processes without immigration).
Fast Branch & Bound algorithms for optimal feature selection
Somol, Petr; Pudil, Pavel; Kittler, J.
2004-01-01
Roč. 26, č. 7 (2004), s. 900-912. ISSN 0162-8828 R&D Projects: GA ČR GA402/02/1271; GA ČR GA402/03/1310; GA AV ČR KSK1019101 Institutional research plan: CEZ:AV0Z1075907 Keywords : subset search * feature selection * search tree Subject RIV: BD - Theory of Information Impact factor: 4.352, year: 2004
Branch-pipe-routing approach for ships using improved genetic algorithm
Sui, Haiteng; Niu, Wentie
2016-05-01
Branch-pipe routing plays fundamental and critical roles in ship-pipe design. The branch-pipe-routing problem is a complex combinatorial optimization problem and is thus difficult to solve when depending only on human experts. A modified genetic-algorithm-based approach is proposed in this paper to solve this problem. The simplified layout space is first divided into threedimensional (3D) grids to build its mathematical model. Branch pipes in layout space are regarded as a combination of several two-point pipes, and the pipe route between two connection points is generated using an improved maze algorithm. The coding of branch pipes is then defined, and the genetic operators are devised, especially the complete crossover strategy that greatly accelerates the convergence speed. Finally, simulation tests demonstrate the performance of proposed method.
Bound states and the Bekenstein bound
Bousso, R
2004-01-01
We explore the validity of the generalized Bekenstein bound, S <= pi M a. We define the entropy S as the logarithm of the number of states which have energy eigenvalue below M and are localized to a flat space region of width a. If boundary conditions that localize field modes are imposed by fiat, then the bound encounters well-known difficulties with negative Casimir energy and large species number, as well as novel problems arising only in the generalized form. In realistic systems, however, finite-size effects contribute additional energy. We study two different models for estimating such contributions. Our analysis suggests that the bound is both valid and nontrivial if interactions are properly included, so that the entropy S counts the bound states of interacting fields.
Penentuan Batas Bawah pada Metode Branch and Price
Meliana
2013-01-01
Integer Programming is a specific linear programming where the variables of decision are integer. There are so many kind of way to finish this integer programming; one of them is Branch and Price method. Like Branch and Bound method, in the step to finish the integer programming in Branch and Price method need the iterations that are too long. To make the iteration to be short then should be given the lower bound.
A New Method for Lower Bounds on the Running Time of Evolutionary Algorithms
Sudholt, Dirk
2011-01-01
We present a new method for proving lower bounds on the expected running time of evolutionary algorithms. It is based on fitness-level partitions and an additional condition on transition probabilities between fitness levels. The method is versatile, intuitive, elegant, and very powerful. It yields exact or near-exact lower bounds for LO, OneMax, long k-paths, and all functions with a unique optimum. Most lower bounds are very general: they hold for all evolutionary algorithms that only use b...
An exact approach for single machine scheduling with quadratic earliness and tardiness penalties
Jorge M. S. Valente
2007-01-01
In this paper, we consider the single machine scheduling problem with quadratic earliness and tardiness costs, and no machine idle time. We propose two different lower bounds, as well as a lower bounding procedure that combines these two bounds. Optimal branch-and-bound algorithms are then presented. These algorithms incorporate the proposed lower bound, as well as an insertion-based dominance test. The lower bounding procedure and the branch-and-bound algorithms are tested on a wide set of r...
A BOUND ON THE LIGHT EMITTED DURING THE THERMALLY PULSING ASYMPTOTIC GIANT BRANCH PHASE
The integrated luminosity of the thermally pulsing asymptotic giant branch (TP-AGB) phase is a major uncertainty in stellar population synthesis models. We revise the white dwarf initial-final mass relation (IFMR), incorporating the latest composition and distance measurements for several clusters. Using this IFMR and stellar interiors models, we demonstrate that a significant fraction of the core mass growth for intermediate (1.5 sun sun and 3.5 Msun. Using a simple fuel consumption argument we couple this core mass increase to a lower limit on the TP-AGB phase energy output. We demonstrate that the current TP-AGB models of Pietrinferni et al. and Bertelli et al. systematically grow the core less than we require while the latter predict sufficient integrated light. Our calculated lower bound, coupled with chemical evolution constraints, may provide an upper limit to the integrated luminosity of stars in the TP-AGB phase. Alternatively, a robust measurement of the emitted light in this phase and our constraints could set strong constraints on helium enrichment from TP-AGB stars. We estimate the yields predicted by current models as a function of initial mass. Implications for stellar population studies and prospects for improvements are discussed.
Daniel Morillo-Torres
2015-01-01
Full Text Available En este artículo se aborda el problema de Programación de Tareas con Recursos Restringidos (RCPSP. Para su solución, se desarrolla y se implementa una metodología híbrida que usa como base un algoritmo de Ramificación y Acotamiento con potentes reglas de dominancia, y se combina con cuatro heurísticas determinísticas cuyo objetivo es truncar ramas del árbol de búsqueda, pero, a su vez, minimizar la probabilidad de descartar ramales que contengan soluciones óptimas. En esencia, estas estrategias permiten la repartición de iteraciones en forma mayoritaria y organizada en las regiones más promisorias usando, únicamente, subconjuntos que tengan características similares o iguales a las de las soluciones óptimas en cada nivel del árbol, garantizando así una amplia exploración dentro de la región factible y al mismo tiempo una buena explotación. Finalmente se analiza el desempeño del algoritmo desarrollado mediante la solución de algunos problemas de la librería de prueba PSPLIB.
Exponential Lower Bounds for the PPSZ k-SAT Algorithm
Chen, Shiteng; Scheder, Dominik Alban; Talebanfard, Navid;
2013-01-01
In 1998, Paturi, Pudl´ak, Saks, and Zane presented PPSZ, an elegant randomized algorithm for k-SAT. Fourteen years on, this algorithm is still the fastest known worst-case algorithm. They proved that its expected running time on k-CNF formulas with n variables is at most 2(1−k)n, where k 2 (1/k...
Improved space bounds for strongly competitive randomized paging algorithms
Moruz, Gabriel; Negoescu, Andrei Laurian (Dipl.-Inf.)
2013-01-01
Paging is one of the prominent problems in the field of on-line algorithms. While in the deterministic setting there exist simple and efficient strongly competitive algorithms, in the randomized setting a tradeoff between competitiveness and memory is still not settled. Bein et al. [4] conjectured that there exist strongly competitive randomized paging algorithms, using o(k) bookmarks, i.e. pages not in cache that the algorithm keeps track of. Also in [4] the first algorithm using O(k) bookma...
Quiver Varieties and Branching
Hiraku Nakajima
2009-01-01
Full Text Available Braverman and Finkelberg recently proposed the geometric Satake correspondence for the affine Kac-Moody group Gaff [Braverman A., Finkelberg M., arXiv:0711.2083]. They conjecture that intersection cohomology sheaves on the Uhlenbeck compactification of the framed moduli space of Gcpt-instantons on $R^4/Z_r$ correspond to weight spaces of representations of the Langlands dual group $G_{aff}^{vee}$ at level $r$. When $G = SL(l$, the Uhlenbeck compactification is the quiver variety of type $sl(r_{aff}$, and their conjecture follows from the author's earlier result and I. Frenkel's level-rank duality. They further introduce a convolution diagram which conjecturally gives the tensor product multiplicity [Braverman A., Finkelberg M., Private communication, 2008]. In this paper, we develop the theory for the branching in quiver varieties and check this conjecture for $G = SL(l$.
New hybrid evolutionary algorithm for solving the bounded diameter minimum spanning tree problem
Sakshi Arora
2009-12-01
Full Text Available Given a connected, weighted, undirected graph G and a bound D, the bounded diameterminimum spanning tree (BDMST problem seeks a spanning tree on G of minimum weight among the treesin which no path between two vertices contains more than D edges. This problem is NP-hard for 4 D |v| -1. In present paper a new randomized greedy heuristic algorithm for solving BDMST is proposed. Anevolutionary algorithm encodes spanning trees as lists of their edges, augmented with their center vertices.It applies operators that maintain the diameter bound and always generate valid offspring trees. Theseoperators are efficient, so the algorithm scales well to larger problem instances. On 25 Euclidean instancesof up to 1000 vertices, the EA improved substantially on solutions found by the randomized greedyheuristic.
Methods and Technologies Branch (MTB)
The Methods and Technologies Branch focuses on methods to address epidemiologic data collection, study design and analysis, and to modify technological approaches to better understand cancer susceptibility.
Rational hybrid Monte Carlo algorithm for theories with unknown spectral bounds
The Rational Hybrid Monte Carlo (RHMC) algorithm extends the Hybrid Monte Carlo algorithm for lattice QCD simulations to situations involving fractional powers of the determinant of the quadratic Dirac operator. This avoids the updating increment (dt) dependence of observables which plagues the Hybrid Molecular-dynamics (HMD) method. The RHMC algorithm uses rational approximations to fractional powers of the quadratic Dirac operator. Such approximations are only available when positive upper and lower bounds to the operator's spectrum are known. We apply the RHMC algorithm to simulations of 2 theories for which a positive lower spectral bound is unknown: lattice QCD with staggered quarks at finite isospin chemical potential and lattice QCD with massless staggered quarks and chiral 4-fermion interactions (χQCD). A choice of lower bound is made in each case, and the properties of the RHMC simulations these define are studied. Justification of our choices of lower bounds is made by comparing measurements with those from HMD simulations, and by comparing different choices of lower bounds
An Individual Tree Detection Algorithm for Dense Deciduous Forests with Spreading Branches
Shao, G.
2015-12-01
Individual tree information derived from LiDAR may have the potential to assist forest inventory and improve the assessment of forest structure and composition for sustainable forest management. The algorithms developed for individual tree detection are commonly focusing on finding tree tops to allocation the tree positions. However, the spreading branches (cylinder crowns) in deciduous forests cause such kind of algorithms work less effectively on dense canopy. This research applies a machine learning algorithm, mean shift, to position individual trees based on the density of LiDAR point could instead of detecting tree tops. The study site locates in a dense oak forest in Indiana, US. The selection of mean shift kernels is discussed. The constant and dynamic bandwidths of mean shit algorithms are applied and compared.
Joint MAP bias estimation and data association: algorithms
Danford, Scott; Kragel, Bret; Poore, Aubrey
2007-09-01
The problem of joint maximum a posteriori (MAP) bias estimation and data association belongs to a class of nonconvex mixed integer nonlinear programming problems. These problems are difficult to solve due to both the combinatorial nature of the problem and the nonconvexity of the objective function or constraints. A specific problem that has received some attention in the tracking literature is that of the target object map problem in which one tries match a set of tracks as observed by two different sensors in the presence of biases, which are modeled here as a translation between the track states. The general framework also applies to problems in which the costs are general nonlinear functions of the biases. The goal of this paper is to present a class of algorithms based on the branch and bound framework and the "all-pairs" and k-best heuristics that provide a good initial upper bound for a branch and bound algorithm. These heuristics can be used as part of a real-time algorithm or as part of an "anytime algorithm" within the branch and bound framework. In addition, we consider both the A*-search and depth-first search procedures as well as several efficiency improvements such as gating. While this paper focuses on the algorithms, a second paper will focus on simulations.
Appell, Jürgen; Merentes Díaz, Nelson José
2013-01-01
This monographis a self-contained exposition of the definition and properties of functionsof bounded variation and their various generalizations; the analytical properties of nonlinear composition operators in spaces of such functions; applications to Fourier analysis, nonlinear integral equations, and boundary value problems. The book is written for non-specialists. Every chapter closes with a list of exercises and open problems.
Path-valued branching processes and nonlocal branching superprocesses
Li, Zenghu
2012-01-01
A family of continuous-state branching processes with immigration are constructed as the solution flow of a stochastic equation system driven by time-space noises. The family can be regarded as an inhomogeneous increasing path-valued branching process with immigration. Two nonlocal branching immigration superprocesses can be defined from the flow. We identify explicitly the branching and immigration mechanisms of those processes. The results provide new perspectives into the tree-valued Markov processes of Aldous and Pitman [Ann. Inst. H. Poincare Probab. Statist. 34 (1998), 637--686] and Abraham and Delmas [Ann. Probab. To appear].
Metastability of Bose and Fermi gases on the upper branch
LeClair, Andre; Roditi, Itzhak; Squires, Joshua
2016-01-01
We study three dimensional Bose and Fermi gases in the upper branch, a phase defined by the absence of bound states in the repulsive interaction regime, within an approximation that considers only two-body interactions. Employing a formalism based on the S-matrix, we derive a useful analytic expression that holds on the upper branch in the weak coupling limit. We determine upper branch phase diagrams for both bosons and fermions with techniques valid for arbitrary positive scattering length.
Two-swarm cooperative artificial fish algorithm for bound constrained global optimization
Ana Maria A C Rocha; Costa, M. Fernanda P.; Fernandes, Edite Manuela da G. P.
2014-01-01
This study presents a new two-swarm cooperative ﬁsh intelligence algorithm for solving the bound constrained global optimization problem. The master population is moved by a Lévy distribution and cooperates with the training population that follows mainly the classical ﬁsh behaviors. Some numerical experiments are reported.
Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
Friedmann, Oliver; Hansen, Thomas Dueholm; Zwick, Uri
2011-01-01
The simplex algorithm is among the most widely used algorithms for solving linear programs in practice. With essentially all deterministic pivoting rules it is known, however, to require an exponential number of steps to solve some linear programs. No non-polynomial lower bounds were known, prior...... to this work, for randomized pivoting rules. We provide the first subexponential (i.e., of the form 2Ω(nα), for some α>0) lower bounds for the two most natural, and most studied, randomized pivoting rules suggested to date. The first randomized pivoting rule considered is Random-Edge, which among all...... improving pivoting steps (or edges) from the current basic feasible solution (or vertex) chooses one uniformly at random. The second randomized pivoting rule considered is Random-Facet, a more complicated randomized pivoting rule suggested by Kalai and by Matousek, Sharir and Welzl. Our lower bound for the...
Chunxia Jia; Detong Zhu
2008-01-01
In this paper we propose an affine scaling interior algorithm via conjugate gradient path for solving nonlinear equality systems subject to bounds on variables.By employing the affine scaling conjugate gradient path search strategy,we obtain an iterative direction by solving the linearize model.By using the line search technique,we will find an acceptable trial step length along this direction which is strictly feasible and makes the objective function nonmonotonically decreasing.The global convergence and fast local convergence rate of the proposed algorithm are established under some reasonable conditions.Furthermore,the numerical results of the proposed algorithm indicate to be effective.
Numerical Algorithm for a Class of Linear Fractional Programming Problem
Hongwei Jiao; Kun Li; Jianping Wang
2013-01-01
In this study, a branch and bound algorithm is presented for globally solving a class of linear fractional programming problems. In the algorithm, a linear relaxation method is introduced to generate the linear relaxation programming problem of the investigated linear fractional programming problems. In this study, we pay more attention to the numerical experiments. Several test problems are used to verify the feasibility and computational efficiency of the proposed branch and bound algorithm.
Analysis of imbalanced weather data based on branch-and-bound approach%基于分支限界的不平衡气象数据晴雨分析
王剑辉; 梁路; 王彪
2016-01-01
This paper proposed the modified cost-sensitive learning methods to preprocess the imbalance weather data.Con-sidering about the specialty of weather data,it made the value of rainfall per unit time as the cost value.So the data could be divided into two types of rain and non-rain effectively and reasonably.And then it used logic-based approach to analysie the data processed,used branch-and-bound approach to derive a Boolean classifier.Experimental results show that this method is feasible and effective.What’s more,it’s valid to perform any further logic calculation or logic operation on the result of the Boolean classifiers,achieving more flexibility.%提出基于修改的代价敏感学习的方法对不平衡的天气数据进行预处理，结合天气数据自身的特点，以单位时间的降雨量为成本的值，将数据合理有效地区分为下雨和非下雨两类；进而运用基于逻辑的方法对处理完的数据进行分析，运用分支限界算法得出布尔分类器。实验结果表明此方法可行有效，该方法可进一步对布尔分类器结果进行逻辑运算，从而达到更加灵活的操作分类器的效果。
On Entropy Bounds and Holography
Halyo, Edi
2009-01-01
We show that the holographic entropy bound for gravitational systems and the Bekenstein entropy bound for nongravitational systems are holographically related. Using the AdS/CFT correspondence, we find that the Bekenstein bound on the boundary is obtained from the holographic bound in the bulk by minimizing the boundary energy with respect the AdS radius or the cosmological constant. This relation may also ameliorate some problems associated with the Bekenstein bound.
Lin Chen
2014-01-01
Full Text Available To reduce time for collision detection among articulated models, the collision detection algorithm of Hybrid Bounding Volume Hierarchy Tree (HBVHT was proposed to accelerate the speed of culling away triangles. The HBVHT was composed of two phases: A broad phase and a narrow phase. The broad phase consisted of Axis-Aligned Bounding Box (AABB and the Bounding Volume (BV was used to build a Multi-Level Hierarchy Tree (MLHT; the narrow phase was made up of the Oriented Bounding Box (OBB hierarchy trees and triangles. Furthermore, according to the characteristic of hierarchical structure of the HBVHT, an improved cost function was given to analyze the performance of the HBVHT. Experiments were performed between two 6-DOF robots under the Open GL environment. Two robots with the same number of triangles moved with the same trajectory for the collision experiments. Experimental results show that the efficiency of HBVHT algorithm is higher than that of the RAPID and the other two HBVHTs with different structure. The results indicate that the HBVHT algorithm can effectively improve the efficiency of collision detection among the articulated model robots.
Lan, Fujun; Bayraksan, Güzin; Lansey, Kevin
2016-03-01
A regional water supply system design problem that determines pipe and pump design parameters and water flows over a multi-year planning horizon is considered. A non-convex nonlinear model is formulated and solved by a branch-and-reduce global optimization approach. The lower bounding problem is constructed via a three-pronged effort that involves transforming the space of certain decision variables, polyhedral outer approximations, and the Reformulation Linearization Technique (RLT). Range reduction techniques are employed systematically to speed up convergence. Computational results demonstrate the efficiency of the proposed algorithm; in particular, the critical role range reduction techniques could play in RLT based branch-and-bound methods. Results also indicate using reclaimed water not only saves freshwater sources but is also a cost-effective non-potable water source in arid regions. Supplemental data for this article can be accessed at http://dx.doi.org/10.1080/0305215X.2015.1016508.
An Improved Lower Bound Limit State Optimisation Algorithm
Frier, Christian; Damkilde, Lars
2010-01-01
Limit State analysis has been used in engineering practice for many years e.g. the yield-line method for concrete slabs and slip-line solutions in geotechnics. In the recent years there has been an increased interest in numerical Limit State analysis, and today algorithms take into account the non...
Branch-and-Cut-and-Price for the Pickup and Delivery Problem with Time Windows
Røpke, Stefan; Cordeau, Jean-Francois
2009-01-01
In the pickup and delivery problem with time windows (PDPTW), vehicle routes must be designed to satisfy a set of transportation requests, each involving a pickup and a delivery location, under capacity, time window, and precedence constraints. This paper introduces a new branch-and-cut-and-price......In the pickup and delivery problem with time windows (PDPTW), vehicle routes must be designed to satisfy a set of transportation requests, each involving a pickup and a delivery location, under capacity, time window, and precedence constraints. This paper introduces a new branch......-and-cut-and-price algorithm in which lower bounds are computed by solving through column generation the linear programming relaxation of a set partitioning formulation. Two pricing subproblems are considered in the column generation algorithm: an elementary and a non-elementary shortest path problem. Valid inequalities are...... added dynamically to strengthen the relaxations. Some of the previously proposed inequalities for the PDPTW are also shown to be implied by the set partitioning formulation. Computational experiments indicate that the proposed algorithm outperforms a recent branch-and-cut algorithm....
Branch points of substitutions and closing ordered Bratteli diagrams
Yassawi, Reem
2011-01-01
We study stationary ordered Bratteli diagrams and give necessary and sufficient conditions for these orders to generate a continuous Vershik map. We apply this to finding adic representations for one sided substitution subshifts. We give an algorithm to find the branch points of a substitution, which have to be mapped to the minimal elements of such an ordering. We find adic representations for substitutions with one branch point, and also substitutions all of whose branch points are fixed.
The presence of weakly bound rotationally excited initial states of HD2+ lying just below the lowest dissociation limit has been observed as well as quasi-bound, predissociative final states above the dissociation limit resulting from one-photon excitation of those weakly bound states. The excitation of the initial weakly bound and possibly only few quasi-bound states took place with 1064 nm laser radiation. The possibility of one-photon excitation of the vibrationally excited initial HD2+ ions is considered. The centre-of-mass kinetic energy distributions of the D+ and H+ fragment were used to identify the possible initial and final states involved in the transitions leading to these fragments. The fragment ratio D+/H+ is shown to be critically dependent on the ion source pressure. A strong preference is observed for the D++HD dissociation channel over the H++D2 channel at high source gas pressures. The centre-of-mass energy of the resulting H+ and D+ fragments was found to agree with predicted theoretical values, and suggest that among initially excited HD2+ ions, only a few of these lie initially above the lowest dissociation limit. (author)
Yousif, F.B. [Centro de Ciencias Fisicas, UNAM, Cuernavaca, Morelos (Mexico)]. E-mail: fbyousif@fis.unam.mx; Cisneros, C.; Urquijo, J. de; Alvarez, I. [Centro de Ciencias Fisicas, UNAM, Cuernavaca, Morelos (Mexico)
2001-03-14
The presence of weakly bound rotationally excited initial states of HD{sub 2}{sup +} lying just below the lowest dissociation limit has been observed as well as quasi-bound, predissociative final states above the dissociation limit resulting from one-photon excitation of those weakly bound states. The excitation of the initial weakly bound and possibly only few quasi-bound states took place with 1064 nm laser radiation. The possibility of one-photon excitation of the vibrationally excited initial HD{sub 2}{sup +} ions is considered. The centre-of-mass kinetic energy distributions of the D{sup +} and H{sup +} fragment were used to identify the possible initial and final states involved in the transitions leading to these fragments. The fragment ratio D{sup +}/H{sup +} is shown to be critically dependent on the ion source pressure. A strong preference is observed for the D{sup +}+HD dissociation channel over the H{sup +}+D{sub 2} channel at high source gas pressures. The centre-of-mass energy of the resulting H{sup +} and D{sup +} fragments was found to agree with predicted theoretical values, and suggest that among initially excited HD{sub 2}{sup +} ions, only a few of these lie initially above the lowest dissociation limit. (author)
Pebbles and Branching Programs for Tree Evaluation
Cook, Stephen; McKenzie, Pierre; Wehr, Dustin; Braverman, Mark; Santhanam, Rahul
2010-01-01
We introduce the Tree Evaluation Problem, show that it is in logDCFL (and hence in P), and study its branching program complexity in the hope of eventually proving a superlogarithmic space lower bound. The input to the problem is a rooted, balanced d-ary tree of height h, whose internal nodes are labeled with d-ary functions on [k] = {1,...,k}, and whose leaves are labeled with elements of [k]. Each node obtains a value in [k] equal to its d-ary function applied to the values of its d childre...
A general non-linear optimization algorithm for lower bound limit analysis
Krabbenhøft, Kristian; Damkilde, Lars
2003-01-01
The non-linear programming problem associated with the discrete lower bound limit analysis problem is treated by means of an algorithm where the need to linearize the yield criteria is avoided. The algorithm is an interior point method and is completely general in the sense that no particular...... load optimization problem. and finally the efficiency and accuracy of the method is demonstrated by means of examples of plate and slab structures obeying different non-linear yield criteria. Copyright (C) 2002 John Wiley Sons. Ltd....... finite element discretization or yield criterion is required. As with interior point methods for linear programming the number of iterations is affected only little by the problem size. Some practical implementation issues are discussed with reference to the special structure of the common lower bound...
EXACT ALGORITHM FOR BIN COVERING
无
2001-01-01
This paper presents a new arc flow model for the one-dimensional bin covering problem and an algorithm to solve the problem exactly through a branch-and-bound procedure and the technique of column generation. The subproblems occuring in the procedure of branch-and-bound have the same structure and therefore can be solved by the same algorithm. In order to solve effectively the subproblems which are generally large scale, a column generation algorithm is employed. Many rules found in this paper can improve the performance of the methods.
A Finite Continuation Algorithm for Bound Constrained Quadratic Programming
Madsen, Kaj; Nielsen, Hans Bruun; Pinar, Mustafa C.
1999-01-01
The dual of the strictly convex quadratic programming problem with unit bounds is posed as a linear $\\ell_1$ minimization problem with quadratic terms. A smooth approximation to the linear $\\ell_1$ function is used to obtain a parametric family of piecewise-quadratic approximation problems...
Conjugacy Growth and Conjugacy Width of Certain Branch Groups
Fink, Elisabeth
2014-01-01
The conjugacy growth function counts the number of distinct conjugacy classes in a ball of radius $n$. We give a lower bound for the conjugacy growth of certain branch groups, among them the Grigorchuk group. This bound is a function of intermediate growth. We further proof that certain branch groups have the property that every element can be expressed as a product of uniformly boundedly many conjugates of the generators. We call this property bounded conjugacy width. We also show how bounde...
Branching processes and neutral evolution
Taïb, Ziad
1992-01-01
The Galton-Watson branching process has its roots in the problem of extinction of family names which was given a precise formulation by F. Galton as problem 4001 in the Educational Times (17, 1873). In 1875, an attempt to solve this problem was made by H. W. Watson but as it turned out, his conclusion was incorrect. Half a century later, R. A. Fisher made use of the Galton-Watson process to determine the extinction probability of the progeny of a mutant gene. However, it was J. B. S. Haldane who finally gave the first sketch of the correct conclusion. J. B. S. Haldane also predicted that mathematical genetics might some day develop into a "respectable branch of applied mathematics" (quoted in M. Kimura & T. Ohta, Theoretical Aspects of Population Genetics. Princeton, 1971). Since the time of Fisher and Haldane, the two fields of branching processes and mathematical genetics have attained a high degree of sophistication but in different directions. This monograph is a first attempt to apply the current sta...
Lower Bounds for Howard's Algorithm for Finding Minimum Mean-Cost Cycles
Hansen, Thomas Dueholm; Zwick, Uri
2010-01-01
Mean-Cost cycles (MMCC). Experimental studies suggest that Howard’s algorithm works extremely well in this context. The theoretical complexity of Howard’s algorithm for finding MMCCs is a mystery. No polynomial time bound is known on its running time. Prior to this work, there were only linear lower...
Bechtle, Philip [Bonn Univ. (Germany). Physikalisches Inst.; Heinemeyer, Sven [Instituto de Fisica de Cantabria (CSIC-UC), Santander (Spain); Staal, Oscar [Stockholm Univ. (Sweden). Dept. of Physics; Stefaniak, Tim; Williams, Karina E. [Bonn Univ. (Germany). Physikalisches Inst.; Bonn Univ. (Germany). Bethe Center for Theoretical Physics; Weiglein, Georg [Deutsches Elektronen-Synchrotron (DESY), Hamburg (Germany); Brein, Oliver
2013-12-15
We describe the new developments in version 4 of the public computer code HiggsBounds. HiggsBounds is a tool to test models with arbitrary Higgs sectors, containing both neutral and charged Higgs bosons, against the published exclusion bounds from Higgs searches at the LEP, Tevatron and LHC experiments. From the model predictions for the Higgs masses, branching ratios, production cross sections and total decay widths - which are specified by the user in the input for the program - the code calculates the predicted signal rates for the search channels considered in the experimental data. The signal rates are compared to the expected and observed cross section limits from the Higgs searches to determine whether a point in the model parameter space is excluded at 95% confidence level. In this paper we present a modification of the HiggsBounds main algorithm that extends the exclusion test in order to ensure that it provides useful results in the presence of one or more significant excesses in the data, corresponding to potential Higgs signals. We also describe a new method to test whether the limits from an experimental search performed under certain model assumptions can be applied to a different theoretical model. Further developments discussed here include a framework to take into account theoretical uncertainties on the Higgs mass predictions, and the possibility to obtain the {chi}{sup 2} likelihood of Higgs exclusion limits from LEP. Extensions to the user subroutines from earlier versions of HiggsBounds are described. The new features are demonstrated by additional example programs.
We describe the new developments in version 4 of the public computer code HiggsBounds. Higgs-Bounds is a tool to test models with arbitrary Higgs sectors, containing both neutral and charged Higgs bosons, against the published exclusion bounds from Higgs searches at the LEP, Tevatron and LHC experiments. From the model predictions for the Higgs masses, branching ratios, production cross sections and total decay widths - which are specified by the user in the input for the program - the code calculates the predicted signal rates for the search channels considered in the experimental data. The signal rates are compared to the expected and observed cross section limits from the Higgs searches to determine whether a point in the model parameter space is excluded at 95 % confidence level. In this paper we present a modification of the HiggsBounds main algorithm that extends the exclusion test in order to ensure that it provides useful results in the presence of one or more significant excesses in the data, corresponding to potential Higgs signals. We also describe a new method to test whether the limits from an experimental search performed under certain model assumptions can be applied to a different theoretical model. Further developments discussed here include a framework to take into account theoretical uncertainties on the Higgs mass predictions, and the possibility to obtain the χ2 likelihood of Higgs exclusion limits from LEP. Extensions to the user subroutines from earlier versions ofHiggsBounds are described. The new features are demonstrated by additional example programs. (orig.)
Workshop on Branching Processes and Their Applications
Gonzalez Velasco, Miguel; Martinez, Rodrigo; Molina, Manuel
2010-01-01
Contains papers presented at the Workshop on Branching Processes and Their Applications (WBPA09), held in Badajoz, Spain, April 20-23, 2009, which deal with theoretical and practical aspects of branching process theory
A Super-Polynomial Lower Bound for the Parity Game Strategy Improvement Algorithm as We Know it
Friedmann, Oliver
2009-01-01
This paper presents a new lower bound for the discrete strategy improvement algorithm for solving parity games due to Voege and Jurdziski. First, we informally show which structures are difficult to solve for the algorithm. Second, we outline a family of games of quadratic size on which the algorithm requires exponentially many strategy iterations, answering in the negative the long-standing question whether this algorithm runs in polynomial time. Additionally we note that the same family of games can be used to prove a similar result w.r.t. the strategy improvement variant by Schewe.
Matsen Frederick A
2012-05-01
Full Text Available Abstract Background Although taxonomy is often used informally to evaluate the results of phylogenetic inference and the root of phylogenetic trees, algorithmic methods to do so are lacking. Results In this paper we formalize these procedures and develop algorithms to solve the relevant problems. In particular, we introduce a new algorithm that solves a "subcoloring" problem to express the difference between a taxonomy and a phylogeny at a given rank. This algorithm improves upon the current best algorithm in terms of asymptotic complexity for the parameter regime of interest; we also describe a branch-and-bound algorithm that saves orders of magnitude in computation on real data sets. We also develop a formalism and an algorithm for rooting phylogenetic trees according to a taxonomy. Conclusions The algorithms in this paper, and the associated freely-available software, will help biologists better use and understand taxonomically labeled phylogenetic trees.
Weekly Fleet Assignment Model and Algorithm
ZHU Xing-hui; ZHU Jin-fu; GONG Zai-wu
2007-01-01
A 0-1 integer programming model for weekly fleet assignment was put forward based on linear network and weekly flight scheduling in China. In this model, the objective function is to maximize the total profit of fleet assignment, subject to the constraints of coverage, aircraft flow balance, fleet size, aircraft availability, aircraft usage, flight restriction, aircraft seat capacity,and stopover. Then the branch-and-bound algorithm based on special ordered set was applied to solve the model. At last, a realworld case study on an airline with 5 fleets, 48 aircrafts and 1 786 flight legs indicated that the profit increase was $1591276 one week and the running time was no more than 4 min, which shows that the model and algorithm are fairly good for domestic airline.
Algorithms for Protein Structure Prediction
Paluszewski, Martin
-trace. Here we present three different approaches for reconstruction of C-traces from predictable measures. In our first approach [63, 62], the C-trace is positioned on a lattice and a tabu-search algorithm is applied to find minimum energy structures. The energy function is based on half-sphere-exposure (HSE......) is more robust than standard Monte Carlo search. In the second approach for reconstruction of C-traces, an exact branch and bound algorithm has been developed [67, 65]. The model is discrete and makes use of secondary structure predictions, HSE, CN and radius of gyration. We show how to compute good lower...... bounds for partial structures very fast. Using these lower bounds, we are able to find global minimum structures in a huge conformational space in reasonable time. We show that many of these global minimum structures are of good quality compared to the native structure. Our branch and bound algorithm...
Regret Bounds for Deterministic Gaussian Process Bandits
De Freitas, Nando; Smola, Alex; Zoghi, Masrour
2012-01-01
This paper analyses the problem of Gaussian process (GP) bandits with deterministic observations. The analysis uses a branch and bound algorithm that is related to the UCB algorithm of (Srinivas et al., 2010). For GPs with Gaussian observation noise, with variance strictly greater than zero, (Srinivas et al., 2010) proved that the regret vanishes at the approximate rate of $O(\\frac{1}{\\sqrt{t}})$, where t is the number of observations. To complement their result, we attack the deterministic c...
New physics upper bound on the branching ratio of B_s --> l+ l- gamma
Alok, A K; Alok, Ashutosh Kumar
2006-01-01
We consider the effect of new physics on the branching ratio of B_s --> l+ l- gamma where l = e, mu. If the new physics is of the form scalar/pseudoscalar, then it makes no contribution to B_s --> l+ l- gamma, unlike in the case of B_s --> l+ l-, where it can potentially make a very large contribution. New Physics in the form of vector/axial-vector operators cannot lead to large enhancement of B_s --> l+ l- gamma much beyond the Standard Model expectation. But new physics in the form of tensor/pseudo-tensor operators can.
New physics upper bound on the branching ratio of B_s --> l+ l- gamma
Alok, Ashutosh Kumar; Sankar, S. Uma
2006-01-01
We consider the effect of new physics on the branching ratio of B_s--> l+ l- gamma where l=e,mu. If the new physics is of the form scalar/pseudoscalar, then it makes no contribution to B_s--> l+ l- gamma, unlike in the case of B_s--> l+ l-, where it can potentially make a very large contribution. If the new physics is in the form of vector/axial-vector operators, then present data on B-->(K,K^*)l+ l-, does not allow a large enhancement for B_s--> l+ l- gamma. If the new physics is in the form...
A Note on Multitype Branching Process with Bounded Immigration in Random Environment
Hua Ming WANG
2013-01-01
In this paper,we study the total number of progeny,W,before regenerating of multitype branching process with immigration in random environment.We show that the tail probability of |W| is of order t-κ as t → ∞,with κ some constant.As an application,we prove a stable law for (L-1) random walk in random environment,generalizing the stable law for the nearest random walk in random environment (see "Kesten,Kozlov,Spitzer:A limit law for random walk in a random environment.Compositio Math.,30,145-168 (1975)").
Electron propagator calculations on linear and branched carbon cluster dianions
Zakrzewski, V.G.; Ortiz, J.V. [Univ. of New Mexico, Albuquerque, NM (United States)
1994-12-31
Electron propagator calculations have been performed on linear carbon cluster dianions from C{sub 7}{sup 2-} to C{sub 10}{sup 2-} and on branched C{sub 7}{sup 2-}, C{sub 9}{sup 2-} and C{sub 11}{sup 2-} structures which have a central, tricoordinate carbon bound to three branches with alternating long and short bonds. The more stable, branched isomer of C{sub 7}{sup 2-} has a positive vertical ionization energy, but the linear form does not. While linear C{sub 10}{sup 2-} is stable with respect to electron loss, it is not possible to decide from these calculations whether linear C{sub 8}{sup 2-} and C{sub 9}{sup 2-} have the same property. There is evidence that better calculations would obtain bound C{sub 8}{sup 2-} and C{sub 9}{sup 2-} species. All branched dianions have positive, vertical ionization energies. Feynman-Dyson amplitudes for dianion ionization energies display delocalized {pi} bonding, with the two terminal carbons of the longest branches making the largest contributions.
Stochastic Transition between Turbulent Branch and Thermodynamic Branch of an Inhomogeneous Plasma
Kawasaki, Mitsuhiro; Itoh, Sanae-I.; Yagi, Masatoshi; Itoh, Kimitaka
2002-01-01
Transition phenomena between thermodynamic branch and turbulent branch in submarginal turbulent plasma are analyzed with statistical theory. Time-development of turbulent fluctuation is obtained by numerical simulations of Langevin equation which contains submarginal characteristics. Probability density functions and transition rates between two states are analyzed. Transition from turbulent branch to thermodynamic branch occurs in almost entire region between subcritical bifurcation point an...
Bound orbits and gravitational theory
Dadhich, Naresh; Ghosh, Sushant G.(School of Mathematical Sciences, University of KwaZulu-Natal, Westville, 4000, Durban, South Africa); Jhingan, Sanjay
2013-01-01
It can be easily shown that bound orbits around a static source can exist only in 4 dimension and in none else for any long range force. This is so not only for Maxwell's electromagnetic and Newton's gravity but also for Einstein's gravitation theory. In contrast to Maxwell's electrodynamics and Newton's gravity, GR has a natural higher dimensional generalization in Lovelock gravity which remarkably admits bound orbits around a static black hole in all even d=2N+2 dimensions where $N$ is degr...
Online Stochastic Matching: New Algorithms with Better Bounds
Jaillet, Patrick; Lu, Xin
2012-01-01
We consider variants of the online stochastic bipartite matching problem motivated by Internet advertising display applications, as introduced in Feldman et al. [Feldman J, Mehta A, Mirrokni VS, Muthukrishnan S (2009) Online stochastic matching: Beating 1 − 1/e. FOCS '09: Proc. 50th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Washington, DC), 117–126]. In this setting, advertisers express specific interests into requests for impressions of different types. Advertisers are fixed and kn...
Can the Adaptive Metropolis Algorithm Collapse Without the Covariance Lower Bound?
Vihola, Matti
2009-01-01
The Adaptive Metropolis (AM) algorithm is based on the symmetric random-walk Metropolis algorithm. The proposal distribution has the following time-dependent covariance matrix at step $n+1$ \\[ S_n = Cov(X_1,...,X_n) + \\epsilon I, \\] that is, the sample covariance matrix of the history of the chain plus a (small) constant $\\epsilon>0$ multiple of the identity matrix $I$. The lower bound on the eigenvalues of $S_n$ induced by the factor $\\epsilon I$ is theoretically convenient, but practically cumbersome, as a good value for the parameter $\\epsilon$ may not always be easy to choose. This article considers variants of the AM algorithm that do not explicitly bound the eigenvalues of $S_n$ away from zero. The behaviour of $S_n$ is studied in detail, indicating that the eigenvalues of $S_n$ do not tend to collapse to zero in general.
Bounded Densities and Their Derivatives
Kozine, Igor; Krymsky, V.
2009-01-01
This paper describes how one can compute interval-valued statistical measures given limited information about the underlying distribution. The particular focus is on a bounded derivative of a probability density function and its combination with other available statistical evidence for computing...
Jorge M. S. Valente
2008-01-01
In this paper, we consider the single machine scheduling problem with linear earliness and quadratic tardiness costs, and no machine idle time. We propose a lower bounding procedure based on the relaxation of the jobs' completion times. Optimal branch-and-bound algorithms are then presented. These algorithms incorporate the proposed lower bound, as well as an insertion-based dominance test.The branch-and-bound procedures are tested on a wide set of randomly generated problems. The computation...
Meyer, Ulrich; Negoescu, Andrei; Weichert, Volker
Despite disillusioning worst-case behavior, classic algorithms for single-source shortest-paths (SSSP) like Bellman-Ford are still being used in practice, especially due to their simple data structures. However, surprisingly little is known about the average-case complexity of these approaches. We provide new theoretical and experimental results for the performance of classic label-correcting SSSP algorithms on graph classes with non-negative random edge weights. In particular, we prove a tight lower bound of Ω(n 2) for the running times of Bellman-Ford on a class of sparse graphs with O(n) nodes and edges; the best previous bound was Ω(n 4/3 - ɛ ). The same improvements are shown for Pallottino's algorithm. We also lift a lower bound for the approximate bucket implementation of Dijkstra's algorithm from Ω(n logn / loglogn) to Ω(n 1.2 - ɛ ). Furthermore, we provide an experimental evaluation of our new graph classes in comparison with previously used test inputs.
Computer simulation of long-chain branching and branching indexes
Netopilík, Miloš
Vienna : University of Vienna, 2014. s. 22. [International Conference on Polymer Behaviour /6./. 22.09.2014-26.09.2014, Vienna] R&D Projects: GA ČR(CZ) GA13-02938S Institutional support: RVO:61389013 Keywords : branching indexes * intrinsic viscosity * radius of gyration Subject RIV: CD - Macromolecular Chemistry
Recursion relations and branching rules for simple Lie algebras
Lyakhovsky, V D
1995-01-01
The branching rules between simple Lie algebras and its regular (maximal) simple subalgebras are studied. Two types of recursion relations for anomalous relative multiplicities are obtained. One of them is proved to be the factorized version of the other. The factorization property is based on the existence of the set of weights \\Gamma specific for each injection. The structure of \\Gamma is easily deduced from the correspondence between the root systems of algebra and subalgebra. The recursion relations thus obtained give rise to simple and effective algorithm for branching rules. The details are exposed by performing the explicit decomposition procedure for A_{3} \\oplus u(1) \\rightarrow B_{4} injection.
An Improved Chaotic Bat Algorithm for Solving Integer Programming Problems
Osama Abdel Raouf
2014-08-01
Full Text Available Bat Algorithm is a recently-developed method in the field of computational intelligence. In this paper is presented an improved version of a Bat Meta-heuristic Algorithm, (IBACH, for solving integer programming problems. The proposed algorithm uses chaotic behaviour to generate a candidate solution in behaviors similar to acoustic monophony. Numerical results show that the IBACH is able to obtain the optimal results in comparison to traditional methods (branch and bound, particle swarm optimization algorithm (PSO, standard Bat algorithm and other harmony search algorithms. However, the benefits of this proposed algorithm is in its ability to obtain the optimal solution within less computation, which save time in comparison with the branch and bound algorithm (exact solution method.
Branching processes with immigration and related topics
Li, Zenghu
2006-01-01
This is a survey on recent progresses in the study of branching processes with immigration, generalized Ornstein-Uhlenbeck processes and affine Markov processes. We mainly focus on the applications of skew convolution semigroups and the connections in those processes.
Applied Aeroscience and CFD Branch Overview
LeBeau, Gerald J.; Kirk, Benjamin S.
2014-01-01
The principal mission of NASA Johnson Space Center is Human Spaceflight. In support of the mission the Applied Aeroscience and CFD Branch has several technical competencies that include aerodynamic characterization, aerothermodynamic heating, rarefied gas dynamics, and decelerator (parachute) systems.
From configurations to branched configurations and beyond
Magnot, Jean-Pierre
2013-01-01
We propose here a geometric and topological setting for the study of branching effects arising in various fields of research, e.g. in statistical mechanics and turbulence theory. We describe various aspects that appear key points to us, and finish with a limit of such a construction which stand in the dynamics on probability spaces where it seems that branching effects can be fully studied without any adaptation of the framework.
2013-03-26
... Agency Information Collection Activities; Comment Request; Upward Bound and Upward Bound Math Science... Upward Bound Math Science Annual Performance Report. OMB Control Number: 1840-NEW. Type of Review: New... under the regular Upward Bound (UB) and Upward Bound Math and Science (UBMS) Programs. The Department...
Chi-Jen Lin
2015-11-01
Full Text Available This study constructs a practical fuzzy three-dimensional axial assignment model, and proposes two efficient algorithms to solve the model. In our case, the model is applied to team performance management in a company to promote the performance of all members in a team. Two algorithms, namely the index-based branch and bound (B&B algorithm and the f-g trade-off algorithm, which is a hybrid of the trade-off and B&B concepts, are proposed. A numerical example is presented to illustrate these two algorithms. The computational results show that the proposed algorithms are sufficiently efficient and accurate. Two special cases are also discussed.
Higher-order Boltzmann machines and entropy bounds
Apolloni, Bruno; Battistini, Egidio; de Falco, Diego
1999-07-01
We examine some aspects of the interface area between mathematical statistics and statistical physics relevant to the study of Boltzmann machines. The Boltzmann machine learning algorithm is based on a variational principle (Gibbs' lemma for relative entropy). This fact suggests the possibility of a scheme of successive approximations: here we consider successive approximations parametrized by the order of many-body interactions among individual units. We prove bounds on the gain in relative entropy in the crucial step of adding, and estimating by Hebb's rule, a new parameter. We address the problem of providing, on the basis of local observations, upper and lower bounds on the entropy. While upper bounds are easily obtained by subadditivity, lower bounds involve localization of Hirschman bounds on a dual quantum system.
Pen Branch Delta and Savannah River Swamp Hydraulic Model
The proposed Savannah River Site (SRS) Wetlands Restoration Project area is located in Barnwell County, South Carolina on the southwestern boundary of the SRS Reservation. The swamp covers about 40.5 km2 and is bounded to the west and south by the Savannah River and to the north and east by low bluffs at the edge of the Savannah River floodplain. Water levels within the swamp are determined by stage along the Savannah River, local drainage, groundwater seepage, and inflows from four tributaries, Beaver Dam Creek, Fourmile Branch, Pen Branch, and Steel Creek. Historic discharges of heated process water into these tributaries scoured the streambed, created deltas in the adjacent wetland, and killed native vegetation in the vicinity of the delta deposits. Future releases from these tributaries will be substantially smaller and closer to ambient temperatures. One component of the proposed restoration project will be to reestablish indigenous wetland vegetation on the Pen Branch delta that covers about 1.0 km2. Long-term predictions of water levels within the swamp are required to determine the characteristics of suitable plants. The objective of the study was to predict water levels at various locations within the proposed SRS Wetlands Restoration Project area for a range of Savannah River flows and regulated releases from Pen Branch. TABS-MD, a United States Army Corps of Engineer developed two-dimensional finite element open channel hydraulic computer code, was used to model the SRS swamp area for various flow conditions
Pen Branch Delta and Savannah River Swamp Hydraulic Model
Chen, K.F.
1999-05-13
The proposed Savannah River Site (SRS) Wetlands Restoration Project area is located in Barnwell County, South Carolina on the southwestern boundary of the SRS Reservation. The swamp covers about 40.5 km2 and is bounded to the west and south by the Savannah River and to the north and east by low bluffs at the edge of the Savannah River floodplain. Water levels within the swamp are determined by stage along the Savannah River, local drainage, groundwater seepage, and inflows from four tributaries, Beaver Dam Creek, Fourmile Branch, Pen Branch, and Steel Creek. Historic discharges of heated process water into these tributaries scoured the streambed, created deltas in the adjacent wetland, and killed native vegetation in the vicinity of the delta deposits. Future releases from these tributaries will be substantially smaller and closer to ambient temperatures. One component of the proposed restoration project will be to reestablish indigenous wetland vegetation on the Pen Branch delta that covers about 1.0 km2. Long-term predictions of water levels within the swamp are required to determine the characteristics of suitable plants. The objective of the study was to predict water levels at various locations within the proposed SRS Wetlands Restoration Project area for a range of Savannah River flows and regulated releases from Pen Branch. TABS-MD, a United States Army Corps of Engineer developed two-dimensional finite element open channel hydraulic computer code, was used to model the SRS swamp area for various flow conditions.
Mechanisms of side branching and tip splitting in a model of branching morphogenesis.
Yina Guo
Full Text Available Recent experimental work in lung morphogenesis has described an elegant pattern of branching phenomena. Two primary forms of branching have been identified: side branching and tip splitting. In our previous study of lung branching morphogenesis, we used a 4 variable partial differential equation (PDE, due to Meinhardt, as our mathematical model to describe the reaction and diffusion of morphogens creating those branched patterns. By altering key parameters in the model, we were able to reproduce all the branching styles and the switch between branching modes. Here, we attempt to explain the branching phenomena described above, as growing out of two fundamental instabilities, one in the longitudinal (growth direction and the other in the transverse direction. We begin by decoupling the original branching process into two semi-independent sub-processes, 1 a classic activator/inhibitor system along the growing stalk, and 2 the spatial growth of the stalk. We then reduced the full branching model into an activator/inhibitor model that embeds growth of the stalk as a controllable parameter, to explore the mechanisms that determine different branching patterns. We found that, in this model, 1 side branching results from a pattern-formation instability of the activator/inhibitor subsystem in the longitudinal direction. This instability is far from equilibrium, requiring a large inhomogeneity in the initial conditions. It successively creates periodic activator peaks along the growing stalk, each of which later on migrates out and forms a side branch; 2 tip splitting is due to a Turing-style instability along the transversal direction, that creates the spatial splitting of the activator peak into 2 simultaneously-formed peaks at the growing tip, the occurrence of which requires the widening of the growing stalk. Tip splitting is abolished when transversal stalk widening is prevented; 3 when both instabilities are satisfied, tip bifurcation occurs
Mechanisms of Side Branching and Tip Splitting in a Model of Branching Morphogenesis
Guo, Yina; Sun, Mingzhu; Garfinkel, Alan; Zhao, Xin
2014-01-01
Recent experimental work in lung morphogenesis has described an elegant pattern of branching phenomena. Two primary forms of branching have been identified: side branching and tip splitting. In our previous study of lung branching morphogenesis, we used a 4 variable partial differential equation (PDE), due to Meinhardt, as our mathematical model to describe the reaction and diffusion of morphogens creating those branched patterns. By altering key parameters in the model, we were able to reproduce all the branching styles and the switch between branching modes. Here, we attempt to explain the branching phenomena described above, as growing out of two fundamental instabilities, one in the longitudinal (growth) direction and the other in the transverse direction. We begin by decoupling the original branching process into two semi-independent sub-processes, 1) a classic activator/inhibitor system along the growing stalk, and 2) the spatial growth of the stalk. We then reduced the full branching model into an activator/inhibitor model that embeds growth of the stalk as a controllable parameter, to explore the mechanisms that determine different branching patterns. We found that, in this model, 1) side branching results from a pattern-formation instability of the activator/inhibitor subsystem in the longitudinal direction. This instability is far from equilibrium, requiring a large inhomogeneity in the initial conditions. It successively creates periodic activator peaks along the growing stalk, each of which later on migrates out and forms a side branch; 2) tip splitting is due to a Turing-style instability along the transversal direction, that creates the spatial splitting of the activator peak into 2 simultaneously-formed peaks at the growing tip, the occurrence of which requires the widening of the growing stalk. Tip splitting is abolished when transversal stalk widening is prevented; 3) when both instabilities are satisfied, tip bifurcation occurs together with side
Osada, Noriyuki; Takeda, Hiroshi
2003-01-01
To investigate crown development patterns, branch architecture, branch-level light interception, and leaf and branch dynamics were studied in saplings of a plagiotropically branching tree species, Polyalthia jenkinsii Hk. f. & Thoms. (Annonaceae) in a Malaysian rain forest. Lengths of branches and parts of the branches lacking leaves ('bare' branches) were smaller in upper branches than in lower branches within crowns, whereas lengths of 'leafy' parts and the number of leaves per branch were larger in intermediate than in upper and lower branches. Maximum diffuse light absorption (DLA) of individual leaves was not related to sapling height or branch position within crowns, whereas minimum DLA was lower in tall saplings. Accordingly, branch-level light interception was higher in intermediate than in upper and lower branches. The leaf production rate was higher and leaf loss rate was smaller in upper than in intermediate and lower branches. Moreover, the branch production rate of new first-order branches was larger in the upper crowns. Thus, leaf and branch dynamics do not correspond to branch-level light interception in the different canopy zones. As a result of architectural constraints, branches at different vertical positions experience predictable light microenvironments in plagiotropic species. Accordingly, this pattern of carbon allocation among branches might be particularly important for growth and crown development in plagiotropic species. PMID:12495920
Sharp Bounds by Probability-Generating Functions and Variable Drift
Doerr, Benjamin; Fouz, Mahmoud; Witt, Carsten
2011-01-01
We introduce to the runtime analysis of evolutionary algorithms two powerful techniques: probability-generating functions and variable drift analysis. They are shown to provide a clean framework for proving sharp upper and lower bounds. As an application, we improve the results by Doerr et al...
Ter-Sarkisov, Aram
2012-01-01
In this article we derive upper bounds on optimization time of the recombination algorithm solving a unimodal problem with plateaus of fitness using a tool we called Elitism Levels Traverse Mechanism. Our findings are asymptotically tight for different parameters of the algorithm and the problem, and we are able to recover some well-known bounds for test problems such as OneMax and Royal Roads. We also present find- ings on the limiting distribution of super-elite species in the population, something no-one seems to have done before in the EA community.
Bounded rationality and learning in market competition
Tuinstra, J.; Hommes, C.H.; Kopányi, D.
2015-01-01
This thesis promotes the use of bounded rationality in economic models. The assumption of perfect rationality often imposes high informational and computational burden on economic agents and predictions based on this assumption are not in line with observed behavior in some cases. Models of bounded rationality may better explain actual behavior in such situations. In the thesis we consider market models where firms are boundedly rational: they do not know the demand for their product and they...
Fuzzy upper bounds and their applications
This paper considers the concept of fuzzy upper bounds and provides some relevant applications. Considering a fuzzy DEA model, the existence of a fuzzy upper bound for the objective function of the model is shown and an effective approach to solve that model is introduced. Some dual interpretations are provided, which are useful for practical purposes. Applications of the concept of fuzzy upper bounds in two physical problems are pointed out
A lower bound and estimates for resonances
Using Schwinger's variational formula for the phase shifts, we deduce a lower bound for the potential strength lambdasub(l)(K) at which deltasub(l)(K)=π/2. The derivation is used to show that the lower bound is a worse estimate than a known upper bound. Whence an improved lower bound is deduced which is then used to obtain an estimate for lambdasub(l)(K). These considerations are then illustrated for some potentials of practical interest, viz., the square well, exponential, Morse and Yukawa, the results being satisfactory. (author)
Point-Based POMDP Algorithms: Improved Analysis and Implementation
Smith, Trey; Simmons, Reid
2012-01-01
Existing complexity bounds for point-based POMDP value iteration algorithms focus either on the curse of dimensionality or the curse of history. We derive a new bound that relies on both and uses the concept of discounted reachability; our conclusions may help guide future algorithm design. We also discuss recent improvements to our (point-based) heuristic search value iteration algorithm. Our new implementation calculates tighter initial bounds, avoids solving linear programs, and makes more...
An Optimal Mastermind (4,7) Strategy and More Results in the Expected Case
Ville, Geoffroy
2013-01-01
This paper presents an optimal strategy for solving the 4 peg-7 color Mastermind MM(4,7) in the expected case (4.676) along with optimal strategies or upper bounds for other values. The program developed is using a depth-first branch and bound algorithm relying on tight upper bound, dynamic lower bound evaluation and guess equivalence to prune symmetric tree branches.
Branch Retinal Vein Occlusion and Its Management
Desmond; Archer
1992-01-01
The natural course of Branch Retinal Vein Occlusion is determined by the site and completeness of the occlusion, the integrity of arterial perfusion to the affected sector and the efficiency of the developing collateral circulation. Most patients with tributary vein occlusion have some capillary fall out and microvascular incompetence in the distribution of the affected retina and vision is significantly compromised in over 50% of patients who have either chronic macular oedema or ischemia involving the...
Gerez, Sabih H.; Heemstra de Groot, Sonia M.; Herrmann, Otto E.
1992-01-01
Rate-optimal scheduling of iterative data-flow graphs requires the computation of the iteration period bound. According to the formal definition, the total computational delay in each directed loop in the graph has to be calculated in order to determine that bound. As the number of loops cannot be expressed as a polynomial function of the number of modes in the graph, this definition cannot be the basis of an efficient algorithm. A polynomial-time algorithm for the computation of the iteratio...