Log in

Relevant bibliographies by topics / Branch and bound algorithm / Journal articles

To see the other types of publications on this topic, follow the link: Branch and bound algorithm.

Journal articles on the topic 'Branch and bound algorithm'

Author: Grafiati

Published: 4 June 2021

Last updated: 1 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Branch and bound algorithm.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Wang, Luzhi, Shuli Hu, Mingyang Li, and Junping Zhou. "An Exact Algorithm for Minimum Vertex Cover Problem." Mathematics 7, no. 7 (July 6, 2019): 603. http://dx.doi.org/10.3390/math7070603.

Full text

Abstract:

In this paper, we propose a branch-and-bound algorithm to solve exactly the minimum vertex cover (MVC) problem. Since a tight lower bound for MVC has a significant influence on the efficiency of a branch-and-bound algorithm, we define two novel lower bounds to help prune the search space. One is based on the degree of vertices, and the other is based on MaxSAT reasoning. The experiment confirms that our algorithm is faster than previous exact algorithms and can find better results than heuristic algorithms.

APA, Harvard, Vancouver, ISO, and other styles

2

Bunnag, Dhiranuch. "Combining Interval Branch and Bound and Stochastic Search." Abstract and Applied Analysis 2014 (2014): 1–15. http://dx.doi.org/10.1155/2014/861765.

Full text

Abstract:

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 proof is described. Moreover, the idea of both algorithms suggests a structure for an integrated interval branch and bound and genetic algorithm for constrained problems in which the algorithm is described and tested. The aim is to capture one of the solutions with higher accuracy and lower cost. The results show better quality of the solutions with less number of function evaluations compared with the traditional GA.

APA, Harvard, Vancouver, ISO, and other styles

3

Utama, Dana Marsetiya. "Algoritma LPT-Branch and Bound Pada Penjadwalan Flexible Flowshop untuk Meminimasi Makespan." PROZIMA (Productivity, Optimization and Manufacturing System Engineering) 2, no. 1 (June 25, 2019): 20. http://dx.doi.org/10.21070/prozima.v2i1.1527.

Full text

Abstract:

This article discussed the problem of flow shop scheduling to minimize the makespan. The purpose of this article is to develop the LPT and Branch And Bound (LPT-Branch And Bound) algorithms to minimize the makespan. The proposed method is Longest Processing Time (LPT) and Branch And Bound. Stage settlement is divided into 3 parts. To proved the proposed algorithm, a numerical experiment was conducted by comparing the LPT-LN algorithm. The result of the numerical experiment shows that LPT-Branch And Bound's proposed algorithm is more efficient than the LPT-LN algorithm.

APA, Harvard, Vancouver, ISO, and other styles

4

CLAUSEN, JENS, and JESPER LARSSON TRÄFF. "DO INHERENTLY SEQUENTIAL BRANCH-AND-BOUND ALGORITHMS EXIST?" Parallel Processing Letters 04, no. 01n02 (June 1994): 3–13. http://dx.doi.org/10.1142/s0129626494000028.

Full text

Abstract:

In the construction of algorithms for [Formula: see text] optimization problems the Branch-and-Bound paradigm is an essential tool. Furthermore, Branch-and-Bound algorithms are traditionally regarded as well suited for parallel implementation due to the subdivision of the problem considered into essentially independent subproblems. In this paper we present experimental results for a Branch-and-Bound algorithm for the Graph Partitioning Problem showing that the traditional parallelization of a Branch-and-Bound algorithm does not always lead to an efficient parallel algorithm. The main reason seems to be lack of meaningful work, i.e. concurrent existence of subproblems which have to be solved to ensure optimality of the solution. We support this claim with experimental results.

APA, Harvard, Vancouver, ISO, and other styles

5

Chun-Hung Cheng. "A branch and bound clustering algorithm." IEEE Transactions on Systems, Man, and Cybernetics 25, no. 5 (May 1995): 895–98. http://dx.doi.org/10.1109/21.376504.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Andriansyah, Andriansyah, and Prima Denny Sentia. "PENENTUAN RUTE KENDARAAN PADA SISTEM DISTRIBUSI LOGISTIK PASCA BENCANA (STUDI KASUS)." Jurnal Manajemen Industri dan Logistik 2, no. 1 (December 4, 2018): 79–89. http://dx.doi.org/10.30988/jmil.v2i1.28.

Full text

Abstract:

The success indicators of disaster mitigation can be seen from the disaster logistics system. Effective and efficient distribution network can make a good disaster logistics system. The problem that related to the design of this network is the vehicle routing problem. The objective is determined optimal route of relief distribution from warehouse to victims with minimum time duration. The problem is solved by branch and bound, insertion heuristic, and local search algorithms. The results obtained by branch and bound and local search algorithm are optimal global. Time duration of vehicle using these algoritm is 1.0562 hours. However, computation time using branch and bound algorithm is very long until 22 hours while local search algorithm only takes 60 seconds. The insertion heuristic algorithm also produces a good solution. Time duration of vehicle using this algoritm is 1,1030 hours. This solution is local optimal, but the computation time is very short, only 0.001 seconds.

APA, Harvard, Vancouver, ISO, and other styles

7

Paulavičius, Remigijus, and Julius Žilinskas. "GLOBAL OPTIMIZATION USING THE BRANCH‐AND‐BOUND ALGORITHM WITH A COMBINATION OF LIPSCHITZ BOUNDS OVER SIMPLICES." Technological and Economic Development of Economy 15, no. 2 (June 30, 2009): 310–25. http://dx.doi.org/10.3846/1392-8619.2009.15.310-325.

Full text

Abstract:

Many problems in economy may be formulated as global optimization problems. Most numerically promising methods for solution of multivariate unconstrained Lipschitz optimization problems of dimension greater than 2 use rectangular or simplicial branch‐and‐bound techniques with computationally cheap, but rather crude lower bounds. The proposed branch‐and‐bound algorithm with simplicial partitions for global optimization uses a combination of 2 types of Lipschitz bounds. One is an improved Lipschitz bound with the first norm. The other is a combination of simple bounds with different norms. The efficiency of the proposed global optimization algorithm is evaluated experimentally and compared with the results of other well‐known algorithms. The proposed algorithm often outperforms the comparable branch‐and‐bound algorithms. Santrauka Daug įvairių ekonomikos uždavinių yra formuluojami kaip globaliojo optimizavimo uždaviniai. Didžioji dalis Lipšico globaliojo optimizavimo metodų, tinkamų spręsti didesnės dimensijos, t. y. n > 2, uždavinius, naudoja stačiakampį arba simpleksinį šakų ir rėžių metodus bei paprastesnius rėžius. Šiame darbe pasiūlytas simpleksinis šakų ir rėžių algoritmas, naudojantis dviejų tipų viršutinių rėžių junginį. Pirmasis yra pagerintas rėžis su pirmąja norma, kitas – trijų paprastesnių rėžių su skirtingomis normomis junginys. Gautieji eksperimentiniai pasiūlyto algoritmo rezultatai yra palyginti su kitų gerai žinomų Lipšico optimizavimo algoritmų rezultatais.

APA, Harvard, Vancouver, ISO, and other styles

8

Paulavičius, Remigijus, and Julius Žilinskas. "INFLUENCE OF LIPSCHITZ BOUNDS ON THE SPEED OF GLOBAL OPTIMIZATION." Technological and Economic Development of Economy 18, no. 1 (April 10, 2012): 54–66. http://dx.doi.org/10.3846/20294913.2012.661170.

Full text

Abstract:

Global optimization methods based on Lipschitz bounds have been analyzed and applied widely to solve various optimization problems. In this paper a bound for Lipschitz function is proposed, which is computed using function values at the vertices of a simplex and the radius of the circumscribed sphere. The efficiency of a branch and bound algorithm with proposed bound and combinations of bounds is evaluated experimentally while solving a number of multidimensional test problems for global optimization. The influence of different bounds on the performance of a branch and bound algorithm has been investigated.

APA, Harvard, Vancouver, ISO, and other styles

9

Yeoh, W., A. Felner, and S. Koenig. "BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm." Journal of Artificial Intelligence Research 38 (May 23, 2010): 85–133. http://dx.doi.org/10.1613/jair.2849.

Full text

Abstract:

Distributed constraint optimization (DCOP) problems are a popular way of formulating and solving agent-coordination problems. A DCOP problem is a problem where several agents coordinate their values such that the sum of the resulting constraint costs is minimal. It is often desirable to solve DCOP problems with memory-bounded and asynchronous algorithms. We introduce Branch-and-Bound ADOPT (BnB-ADOPT), a memory-bounded asynchronous DCOP search algorithm that uses the message-passing and communication framework of ADOPT (Modi, Shen, Tambe, & Yokoo, 2005), a well known memory-bounded asynchronous DCOP search algorithm, but changes the search strategy of ADOPT from best-first search to depth-first branch-and-bound search. Our experimental results show that BnB-ADOPT finds cost-minimal solutions up to one order of magnitude faster than ADOPT for a variety of large DCOP problems and is as fast as NCBB, a memory-bounded synchronous DCOP search algorithm, for most of these DCOP problems. Additionally, it is often desirable to find bounded-error solutions for DCOP problems within a reasonable amount of time since finding cost-minimal solutions is NP-hard. The existing bounded-error approximation mechanism allows users only to specify an absolute error bound on the solution cost but a relative error bound is often more intuitive. Thus, we present two new bounded-error approximation mechanisms that allow for relative error bounds and implement them on top of BnB-ADOPT.

APA, Harvard, Vancouver, ISO, and other styles

10

Jiao, Hong-Wei, Feng-Hui Wang, and Yong-Qiang Chen. "An Effective Branch and Bound Algorithm for Minimax Linear Fractional Programming." Journal of Applied Mathematics 2014 (2014): 1–8. http://dx.doi.org/10.1155/2014/160262.

Full text

Abstract:

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 global optimal solution of the problem (MLFP) through the successive refinement of the feasible region and solutions of a series of the LRP. Numerical results for several test problems are reported to show the feasibility and effectiveness of the proposed algorithm.

APA, Harvard, Vancouver, ISO, and other styles

11

Kawaguchi, Tsuyoshi, Hiroshi Masuyama, and Tamotsu Maeda. "An asynchronous parallel branch-and-bound algorithm." Systems and Computers in Japan 23, no. 4 (1992): 1–13. http://dx.doi.org/10.1002/scj.4690230401.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Janakiram, Virendra K., Edward F. Gehringer, Dharma P. Agrawal, and Ravi Mehrotra. "A randomized parallel branch-and-bound algorithm." International Journal of Parallel Programming 17, no. 3 (June 1988): 277–301. http://dx.doi.org/10.1007/bf02427853.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Yu, Yu. "Parallel Branch and Bound Algorithm for Product Testing Job Scheduling Problems using MapReduce." International Journal of Machine Learning and Computing 10, no. 2 (February 2020): 290–98. http://dx.doi.org/10.18178/ijmlc.2020.10.2.934.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Zhou, Xue-Gang, and Bing-Yuan Cao. "A Simplicial Branch and Bound Duality-Bounds Algorithm to Linear Multiplicative Programming." Journal of Applied Mathematics 2013 (2013): 1–10. http://dx.doi.org/10.1155/2013/984168.

Full text

Abstract:

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 introducingpauxiliary 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 minimum through the solutions to a series of linear programming problems. Some examples are given to illustrate the feasibility of the present algorithm.

APA, Harvard, Vancouver, ISO, and other styles

15

HERLEY, KIERAN T., ANDREA PIETRACAPRINA, and GEPPINO PUCCI. "FAST DETERMINISTIC PARALLEL BRANCH-AND-BOUND." Parallel Processing Letters 09, no. 03 (September 1999): 325–33. http://dx.doi.org/10.1142/s012962649900030x.

Full text

Abstract:

The branch-and-bound problem involves determining the minimum cost leaf in a cost-labelled tree, subject to the constraint that only the root is known initially and that children are revealed only by visiting thier parent. We present the first efficient deterministic algorithm to solve the branch-and-bound problem for a tree T of constant degree on a p-processor parallel machine. Let c* be the cost of the minimum-cost leaf in T, and let n and h be the number of nodes and the height, respectively, of the subtree T* ⊆ T of nodes of cost less than or equal to c*. Our algorithm runs in O(n/p + h log 2(np)) time on an EREW-PRAM. Moreover, the running time faithfully reflects both communication and computation costs, unlike most of the previous results where the cost of local computation is ignored. For large ranges of the parameters, our algorithm matches the optimal performance of existing randomized strategies. The algorithm can be ported to any architecture for which an efficient implementation of Parallel Priority Queues [PP91] is available.

APA, Harvard, Vancouver, ISO, and other styles

16

Wang, Zhenyou, Cai-Min Wei, and Yuan-Yuan Lu. "Permutation Flow Shop Problem with Shortening Job Processing Times." Asia-Pacific Journal of Operational Research 33, no. 04 (August 2016): 1650032. http://dx.doi.org/10.1142/s0217595916500329.

Full text

Abstract:

In this paper, we consider a three-machine makespan minimization permutation flow shop scheduling problem with shortening job processing times. Shortening job processing times means that its processing time is a nonincreasing function of its execution start time. Optimal solutions are obtained for some special cases. For the general case, several dominance properties and two lower bounds are developed to construct a branch-and-bound (B&B) algorithm. Furthermore, we propose a heuristic algorithm to overcome the inefficiency of the branch-and-bound algorithm.

APA, Harvard, Vancouver, ISO, and other styles

17

Kämmerling, Nicolas, and Jannis Kurtz. "Oracle-based algorithms for binary two-stage robust optimization." Computational Optimization and Applications 77, no. 2 (June 23, 2020): 539–69. http://dx.doi.org/10.1007/s10589-020-00207-w.

Full text

Abstract:

Abstract In this work we study binary two-stage robust optimization problems with objective uncertainty. We present an algorithm to calculate efficiently lower bounds for the binary two-stage robust problem by solving alternately the underlying deterministic problem and an adversarial problem. For the deterministic problem any oracle can be used which returns an optimal solution for every possible scenario. We show that the latter lower bound can be implemented in a branch and bound procedure, where the branching is performed only over the first-stage decision variables. All results even hold for non-linear objective functions which are concave in the uncertain parameters. As an alternative solution method we apply a column-and-constraint generation algorithm to the binary two-stage robust problem with objective uncertainty. We test both algorithms on benchmark instances of the uncapacitated single-allocation hub-location problem and of the capital budgeting problem. Our results show that the branch and bound procedure outperforms the column-and-constraint generation algorithm.

APA, Harvard, Vancouver, ISO, and other styles

18

Chu, Sydney C. K. "Efficient bounds on a branch and bound algorithm for graph colouration." International Journal of Mathematical Education in Science and Technology 22, no. 5 (September 1991): 823–32. http://dx.doi.org/10.1080/0020739910220516.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Grinshpoun, Tal, and Tamir Tassa. "P-SyncBB: A Privacy Preserving Branch and Bound DCOP Algorithm." Journal of Artificial Intelligence Research 57 (December 30, 2016): 621–60. http://dx.doi.org/10.1613/jair.5322.

Full text

Abstract:

Distributed constraint optimization problems enable the representation of many combinatorial problems that are distributed by nature. An important motivation for such problems is to preserve the privacy of the participating agents during the solving process. The present paper introduces a novel privacy-preserving branch and bound algorithm for this purpose. The proposed algorithm, P-SyncBB, preserves constraint, topology and decision privacy. The algorithm requires secure solutions to several multi-party computation problems. Consequently, appropriate novel secure protocols are devised and analyzed. An extensive experimental evaluation on different benchmarks, problem sizes, and constraint densities shows that P-SyncBB exhibits superior performance to other privacy-preserving complete DCOP algorithms.

APA, Harvard, Vancouver, ISO, and other styles

20

El Bechari, Reda, Stéphane Brisset, Stéphane Clénet, Frédéric Guyomarch, and Jean Claude Mipo. "Branch and Bound Algorithm Based on Prediction Error of Metamodel for Computational Electromagnetics." Energies 13, no. 24 (December 21, 2020): 6749. http://dx.doi.org/10.3390/en13246749.

Full text

Abstract:

Metamodels proved to be a very efficient strategy for optimizing expensive black-box models, e.g., Finite Element simulation for electromagnetic devices. It enables the reduction of the computational burden for optimization purposes. However, the conventional approach of using metamodels presents limitations such as the cost of metamodel fitting and infill criteria problem-solving. This paper proposes a new algorithm that combines metamodels with a branch and bound (B&B) strategy. However, the efficiency of the B&B algorithm relies on the estimation of the bounds; therefore, we investigated the prediction error given by metamodels to predict the bounds. This combination leads to high fidelity global solutions. We propose a comparison protocol to assess the approach’s performances with respect to those of other algorithms of different categories. Then, two electromagnetic optimization benchmarks are treated. This paper gives practical insights into algorithms that can be used when optimizing electromagnetic devices.

APA, Harvard, Vancouver, ISO, and other styles

21

Nadeem, Dr Sumit Agarwal, Dr Arif. "Branch and Bound Algorithm with Implementation of ooOPS." IOSR Journal of Mathematics 4, no. 4 (2012): 22–26. http://dx.doi.org/10.9790/5728-0442226.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Jin, Jian-qiu, Zhang-ye Wang, and Qun-sheng Peng. "Constrained Branch-and-Bound algorithm for image registration." Journal of Zhejiang University-SCIENCE A 6, S1 (August 2005): 94–99. http://dx.doi.org/10.1631/jzus.2005.as0094.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

OKANO, Ryohtaro, Takashi KIDA, and Tomoyuki NAGASHIO. "On Branch and Bound Algorithm for Solving BMI." Transactions of the Society of Instrument and Control Engineers 40, no. 1 (2004): 45–53. http://dx.doi.org/10.9746/sicetr1965.40.45.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Toan, Phan Thanh, and Nguyen The Loc. "A BRANCH AND BOUND ALGORITHM FOR WORKFLOW SCHEDULING." Vietnam Journal of Science and Technology 56, no. 2 (April 12, 2018): 246. http://dx.doi.org/10.15625/2525-2518/56/2/10672.

Full text

Abstract:

Nowadays, people are connected to the Internet and use different Cloud solutions to store, process and deliver data. The Cloud consists of a collection of virtual servers that promise to provision on-demand computational and storage resources when needed. Workflow data is becoming an ubiquitous term in both science and technology and there is a strong need for new tools and techniques to process and analyze large-scale complex datasets that are growing exponentially. scientific workflow is a sequence of connected tasks with large data transfer from parent task to children tasks. Workflow scheduling is the activity of assigning tasks to execution on servers and satisfying resource constraints and this is an NP-hard problem. In this paper, we propose a scheduling algorithm for workflow data that is derived from the Branch and Bound Algorithm.

APA, Harvard, Vancouver, ISO, and other styles

25

Baravykaite, M., R. Čiegis, and J. Žilinskas. "TEMPLATE REALIZATION OF GENERALIZED BRANCH AND BOUND ALGORITHM." Mathematical Modelling and Analysis 10, no. 3 (September 30, 2005): 217–36. http://dx.doi.org/10.3846/13926292.2005.9637283.

Full text

Abstract:

In this work we consider a template for implementation of parallel branch and bound algorithms. The main aim of this package to ease implementation of covering and combinatorial optimization methods for global optimization. Standard parts of global optimization algorithms are implemented in the package and only method specific rules should be implemented by the user. The parallelization part of the tool is described in details. Results of computational experiments are presented and discussed. Straipsnyje pristatyta apibendrinto šaku ir režiu algoritmo šablono realizacija. Irankis skirtas palengvinti nuosekliuju ir lygiagrečiuju optimizacijos uždaviniu programu kūrima. Nuo uždavinio nepriklausančios algoritmo dalys yra idiegtos šablone ir vartotojui reikia sukurti tik nuo uždavinio priklausančiu daliu realizacija. Šablone idiegti keli lygiagretieji algoritmai, paremti tyrimo srities padalinimu tarp procesoriu. Pateikiami skaičiavimo eksperimentu rezultatai.

APA, Harvard, Vancouver, ISO, and other styles

26

Shen, Peiping, and Xiaoai Li. "Branch-reduction-bound algorithm for generalized geometric programming." Journal of Global Optimization 56, no. 3 (June 13, 2012): 1123–42. http://dx.doi.org/10.1007/s10898-012-9933-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Bendjoudi, A., N. Melab, and E. G. Talbi. "Hierarchical branch and bound algorithm for computational grids." Future Generation Computer Systems 28, no. 8 (October 2012): 1168–76. http://dx.doi.org/10.1016/j.future.2012.03.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Huang, M., Huaping Wu, Vincent Cho, W. H. Ip, Xingwei Wang, and C. K. Ng. "Single Machine Problem with Multi-Rate-Modifying Activities under a Time-Dependent Deterioration." Journal of Applied Mathematics 2013 (2013): 1–10. http://dx.doi.org/10.1155/2013/135610.

Full text

Abstract:

The single machine scheduling problem with multi-rate-modifying activities under a time-dependent deterioration to minimize makespan is studied. After examining the characteristics of the problem, a number of properties and a lower bound are proposed. A branch and bound algorithm and a heuristic algorithm are used in the solution, and two special cases are also examined. The computational experiments show that, for the situation with a rate-modifying activity, the proposed branch and bound algorithm can solve situations with 50 jobs within a reasonable time, and the heuristic algorithm can obtain the near-optimal solution with an error percentage less than 0.053 in a very short time. In situations with multi-rate-modifying activities, the proposed branch and bound algorithm can solve the case with 15 jobs within a reasonable time, and the heuristic algorithm can obtain the near-optimal with an error percentage less than 0.070 in a very short time. The branch and bound algorithm and the heuristic algorithm are both shown to be efficient and effective.

APA, Harvard, Vancouver, ISO, and other styles

29

Zumaytis, Sofriesilero, and Oscar Karnalim. "Introducing an Educational Tool for Learning Branch & Bound Strategy." Journal of Information Systems Engineering and Business Intelligence 3, no. 1 (April 28, 2017): 8. http://dx.doi.org/10.20473/jisebi.3.1.8-15.

Full text

Abstract:

Abstract—According to our informal survey, Branch & Bound strategy is considerably difficult to learn compared to other strategies. This strategy consists of several complex algorithmic steps such as Reduced Cost Matrix (RCM) calculation and Breadth First Search. Thus, to help students understanding this strategy, AP-BB, an educational tool for learning Branch & Bound is developed. This tool includes four modules which are Brute Force solving visualization, Branch & Bound solving visualization, RCM calculator, and case-based performance comparison. These modules are expected to enhance student’s understanding about Branch & Bound strategy and its characteristics. Furthermore, our work incorporates TSP as its case study and Brute Force strategy as a baseline to provide a concrete impact of Branch & Bound strategy. According to our qualitative evaluation, AP-BB and all of its features fulfil student necessities for learning Branch & Bound strategy. Keywords— Educational Tool; Branch & Bound; Algorithm Strategy; Algorithm Visualization

APA, Harvard, Vancouver, ISO, and other styles

30

Motair, Hafed Mohammed. "Solving Composite MultiobjectiveSingle Machine Scheduling ProblemUsingBranch and Bound and Local SearchAlgorithms." Al-Mustansiriyah Journal of Science 28, no. 3 (July 3, 2018): 200. http://dx.doi.org/10.23851/mjs.v28i3.122.

Full text

Abstract:

This paper present algorithms for solving a single machine scheduling problem to minimize the sum of total completion times, total tardiness,maxim-um tardiness,and maximum earliness.The single machine total tardiness problem is already NP-hard, so the consider problem is strongly NP-hard, and several algorithms are used to solve it. Branch and bound algorithmwith dominance ruleand local search algorit- hms are proposed for the problem. For the Branch and bound algorithm results- show that using dominance rule improve the performance of the algorithm in both computation times and optimal values,but it need longer times.Thus we tackle the problemof large sizes with local search algorit- hms descent method, simulated annealing and tabusearch. The perfomance of these algorithms is evaluated on a large set of test problems and the results are compared.The computational results show that simulated annealing algorithm and Tabu search algorithm are better than Descent method with preference to simulated annealing algorithm,and show that the three algorithms find optimal or near optimal solutions inreasonable times.

APA, Harvard, Vancouver, ISO, and other styles

31

Kahribt, Tahani Jabbar, and Mohammed Kadhim Al- Zuwaini. "Branch and Bound Method to Solve Multi Objectives Function." JOURNAL OF ADVANCES IN MATHEMATICS 12, no. 3 (April 27, 2016): 5964–74. http://dx.doi.org/10.24297/jam.v12i3.494.

Full text

Abstract:

This paper presents a branch and bound algorithm for sequencing a set of n independent jobs on a single machine to minimize sum of the discounted total weighted completion time and maximum lateness, this problems is NP-hard. Two lower bounds were proposed and heuristic method to get an upper bound. Some special cases were proved and some dominance rules were suggested and proved, the problem solved with up to 50 jobs.

APA, Harvard, Vancouver, ISO, and other styles

32

Wang, Meihua, Fengmin Xu, and Chengxian Xu. "A Branch-and-Bound Algorithm Embedded with DCA for DC Programming." Mathematical Problems in Engineering 2012 (2012): 1–16. http://dx.doi.org/10.1155/2012/364607.

Full text

Abstract:

The special importance of Difference of Convex (DC) functions programming has been recognized in recent studies on nonconvex optimization problems. In this work, a class of DC programming derived from the portfolio selection problems is studied. The most popular method applied to solve the problem is the Branch-and-Bound (B&B) algorithm. However, “the curse of dimensionality” will affect the performance of the B&B algorithm. DC Algorithm (DCA) is an efficient method to get a local optimal solution. It has been applied to many practical problems, especially for large-scale problems. A B&B-DCA algorithm is proposed by embedding DCA into the B&B algorithms, the new algorithm improves the computational performance and obtains a global optimal solution. Computational results show that the proposed B&B-DCA algorithm has the superiority of the branch number and computational time than general B&B. The nice features of DCA (inexpensiveness, reliability, robustness, globality of computed solutions, etc.) provide crucial support to the combined B&B-DCA for accelerating the convergence of B&B.

APA, Harvard, Vancouver, ISO, and other styles

33

Li, Zhan Tao, Fu Hong, Qing Xin Chen, and Ning Mao. "Branch and Bound Method with Heuristic Algorithm for a Special Flexible Flow Shop Scheduling Problem." Advanced Materials Research 139-141 (October 2010): 1530–34. http://dx.doi.org/10.4028/www.scientific.net/amr.139-141.1530.

Full text

Abstract:

This paper deals with an optimal method for solving a 2-stage flexible flow shop scheduling problem with group constraint, batch released dates. This problem is known to be NP-hard. In this paper, first of all, we construct a mathematical model for the problem. Then, we develop a branch and bound method with heuristic algorithm for the optimal solution of the problem. During the initialization, we use a heuristic algorithm H’ as the initial solution. We propose two branching algorithms in the branching procedure and two algorithms for the lower bound. We also propose a set of instances for this type of problem. The results are shown that our branch and bound method is effective for small and medium-sized problem but large-sized problem.

APA, Harvard, Vancouver, ISO, and other styles

34

Peng, Guo Xing, and Bei Li. "Improved Learning Algorithm Based on Semi-Supervised Support Vector." Key Engineering Materials 474-476 (April 2011): 1–6. http://dx.doi.org/10.4028/www.scientific.net/kem.474-476.1.

Full text

Abstract:

Improved learning algorithm for branch and bound for semi-supervised support vector machines is proposed, according to the greater difference in the optimal solution in different semi-supervised support vector machines for the same data set caused by the local optimization. The lower bound of node in IBBS3VM algorithm is re-defined, which will be pseudo-dual function value as the lower bound of node to avoid the large amount of calculation of 0-1 quadratic programming, reducing the lower bound of each node calculate the time complexity; at the same time, in determining the branch nodes, only based on the credibility of the unlabeled samples without the need to repeatedly carry out the training of support vector machines to enhance the training speed of the algorithm. Simulation analysis shows that IBBS3VM presented in this paper has faster training speed than BBS3VM algorithms, higher precision and stronger robustness than the other semi-supervised support vector machines.

APA, Harvard, Vancouver, ISO, and other styles

35

Nagai, Hidetoshi, and Takahito Kuno. "A SIMPLICIAL BRANCH-AND-BOUND ALGORITHM FOR PRODUCTION-TRANSPORTATION PROBLEMS WITH INSEPARABLE CONCAVE PRODUCTION COST." Journal of the Operations Research Society of Japan 48, no. 2 (2005): 97–110. http://dx.doi.org/10.15807/jorsj.48.97.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Kuno, Takahito, and Jianming Shi. "Linear programs with an additional separable concave constraint." Journal of Applied Mathematics and Decision Sciences 8, no. 3 (January 1, 2004): 155–74. http://dx.doi.org/10.1155/s1173912604000100.

Full text

Abstract:

In this paper, we develop two algorithms for globally optimizing a special class of linear programs with an additional concave constraint. We assume that the concave constraint is defined by a separable concave function. Exploiting this special structure, we apply Falk-Soland's branch-and-bound algorithm for concave minimization in both direct and indirect manners. In the direct application, we solve the problem alternating local search and branch-and-bound. In the indirect application, we carry out the bounding operation using a parametric right-hand-side simplex algorithm.

APA, Harvard, Vancouver, ISO, and other styles

37

Jansson, Christian, and Olaf Kn�ppel. "A branch and bound algorithm for bound constrained optimization problems without derivatives." Journal of Global Optimization 7, no. 3 (October 1995): 297–331. http://dx.doi.org/10.1007/bf01279453.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Elaibi, Waleed Mohammed. "Branch and Bound Algorithm and an Improvement for Calculating the Nearest Link of Building a Railway Network." Al-Mustansiriyah Journal of Science 31, no. 4 (December 20, 2020): 114. http://dx.doi.org/10.23851/mjs.v31i4.923.

Full text

Abstract:

The importance of branch and bound algorithm is the mathematical improvement to find the value of (X) that Maximize or minimize the objective function within a set of feasible solution, as it is reliable on the efficient evaluation of the bounds of regions or branches of the space of the research, whether they are upper or lower. In this paper, we discussed five cases with respect to branching decisions based on network solutions to calculate the nearest link with a short time. From the results, bound and branch algorithm can develop and change the obtaining solutions for the five cases under study.

APA, Harvard, Vancouver, ISO, and other styles

39

Maksimenko, Aleksandr N. "Branch and Bound Algorithm for the Traveling Salesman Problem is not a Direct Type Algorithm." Modeling and Analysis of Information Systems 27, no. 1 (March 23, 2020): 72–85. http://dx.doi.org/10.18255/1818-1015-2020-1-72-85.

Full text

Abstract:

In this paper, we consider the notion of a direct type algorithm introduced by V. A. Bondarenko in 1983. A direct type algorithm is a linear decision tree with some special properties. the concept of a direct type algorithm is determined using the graph of solutions of a combinatorial optimization problem. e vertices of this graph are all feasible solutions of a problem. Two solutions are called adjacent if there are input data for which these and only these solutions are optimal. A key feature of direct type algorithms is that their complexity is bounded from below by the clique number of the solutions graph. In 2015-2018, there were five papers published, the main results of which are estimates of the clique numbers of polyhedron graphs associated with various combinatorial optimization problems. the main motivation in these works is the thesis that the class of direct type algorithms is wide and includes many classical combinatorial algorithms, including the branch and bound algorithm for the traveling salesman problem, proposed by J. D. C. Little, K. G. Murty, D. W. Sweeney, C. Karel in 1963. We show that this algorithm is not a direct type algorithm. Earlier, in 2014, the author of this paper showed that the Hungarian algorithm for the assignment problem is not a direct type algorithm. us, the class of direct type algorithms is not so wide as previously assumed.

APA, Harvard, Vancouver, ISO, and other styles

40

Kabbaj, Mohamed Mustapha, and El Afia Abdellatif. "Adapted Branch-and-Bound Algorithm Using SVM With Model Selection." International Journal of Electrical and Computer Engineering (IJECE) 9, no. 4 (August 1, 2019): 2481. http://dx.doi.org/10.11591/ijece.v9i4.pp2481-2490.

Full text

Abstract:

<span lang="EN-US">Branch-and-Bound algorithm is the basis for the majority of solving methods in mixed integer linear programming. It has been proving its efficiency in different fields. In fact, it creates little by little a tree of nodes by adopting two strategies. These strategies are variable selection strategy and node selection strategy. In our previous work, we experienced a methodology of learning branch-and-bound strategies </span><span lang="EN-US">using regression-based support vector machine twice. That methodology allowed firstly to exploit information from previous executions of Branch-and-Bound algorithm on other instances. Secondly, it created information channel between node selection strategy and variable branching strategy. And thirdly, it gave good results in term of running time comparing to standard Branch-and-Bound algorithm. In this work, we will focus on increasing SVM performance by using cross validation coupled with model selection. </span>

APA, Harvard, Vancouver, ISO, and other styles

41

Afshar-Nadjafi, Behrouz, Zeinab Khalaj, and Esmaeil Mehdizadeh. "A Branch and Bound Approach to Solve the Preemptive Resource Leveling Problem." International Journal of Manufacturing Engineering 2013 (October 27, 2013): 1–7. http://dx.doi.org/10.1155/2013/930920.

Full text

Abstract:

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 leveling problem, it is observed that considering preemption in the problem leads to better results in the objective function. This improvement imposes additional time to solve the problem. Coding the algorithm in MATLAB and checking it on the projects with 8 and 10 activities, results show that the proposed algorithm is efficient.

APA, Harvard, Vancouver, ISO, and other styles

42

SURYAWAN, GEDE, NI KETUT TARI TASTRAWATI, and KARTIKA SARI. "PENERAPAN BRANCH AND BOUND ALGORITHM DALAM OPTIMALISASI PRODUKSI ROTI." E-Jurnal Matematika 5, no. 4 (November 30, 2016): 148. http://dx.doi.org/10.24843/mtk.2016.v05.i04.p134.

Full text

Abstract:

Companies which engaged in production activities such as Ramadhan Bakery would want optimal profit in their every production. The aim of this study was to find optimal profit and optimal combination of bread production (original chocolate bread, extra chocolate bread, rounding chocolate bread and mattress chocolate bread) that was produced by Ramadhan Bakery by applying Branch and Bound Algorithm method. Branch and Bound Algorithm is one method to solve Integer Programming’s problems other than Cutting Plane method. Compared with Cutting Plane method, Branch and Bound Algorithm method is more effective in determining the optimal value. As the result of this study showed that to get optimal profit, Ramadhan Bakery should produce 360 pcs of original chocolate bread, 300 pcs of extra chocolate bread, 306 pcs of rounding chocolate bread and 129 pcs of mattress chocolate bread with optimal profit amounts Rp. 1.195.624,00.. The profit will increase amounts 25,2 % than before.

APA, Harvard, Vancouver, ISO, and other styles

43

HARIRI, A., and C. Pons. "A Branch and Bound Algorithm for Job-Shop Scheduling." Journal of King Abdulaziz University-Science 3, no. 1 (1991): 201–9. http://dx.doi.org/10.4197/sci.3-1.14.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Nakariyakul, Songyot, and David P. Casasent. "Adaptive branch and bound algorithm for selecting optimal features." Pattern Recognition Letters 28, no. 12 (September 2007): 1415–27. http://dx.doi.org/10.1016/j.patrec.2007.02.015.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Cutler, Adele. "A branch and bound algorithm for constrained least squares." Communications in Statistics - Simulation and Computation 22, no. 2 (January 1993): 305–21. http://dx.doi.org/10.1080/03610919308813095.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Patil, S., and P. Banerjee. "A parallel branch and bound algorithm for test generation." IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 9, no. 3 (March 1990): 313–22. http://dx.doi.org/10.1109/43.46806.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Chen, Xue-wen. "An improved branch and bound algorithm for feature selection." Pattern Recognition Letters 24, no. 12 (August 2003): 1925–33. http://dx.doi.org/10.1016/s0167-8655(03)00020-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Moursli, O., and Y. Pochet. "A branch-and-bound algorithm for the hybrid flowshop." International Journal of Production Economics 64, no. 1-3 (March 2000): 113–25. http://dx.doi.org/10.1016/s0925-5273(99)00051-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Hager, William W., and Dzung T. Phan. "An Ellipsoidal Branch and Bound Algorithm for Global Optimization." SIAM Journal on Optimization 20, no. 2 (January 2009): 740–58. http://dx.doi.org/10.1137/080729165.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Diehr, George. "Evaluation of a Branch and Bound Algorithm for Clustering." SIAM Journal on Scientific and Statistical Computing 6, no. 2 (April 1985): 268–84. http://dx.doi.org/10.1137/0906020.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!