Log in

Relevant bibliographies by topics / Method of «branch and bound» / Journal articles

Journal articles on the topic 'Method of «branch and bound»'

To see the other types of publications on this topic, follow the link: Method of «branch and bound».

Author: Grafiati

Published: 30 May 2022

Last updated: 31 May 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 'Method of «branch and bound».'

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

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

2

Rácz, Attila. "Determining Initial Bound by "Ray-method" in Branch and Bound Procedure." Acta Cybernetica 19, no. 1 (2009): 135–46. http://dx.doi.org/10.14232/actacyb.19.1.2009.9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Kondoh, Hitoshi, Fuminori Kobayashi, Shinji Hara, and Nobuo Takehira. "Parallel Branch and Bound Method Using Systematic Shuffling." IEEJ Transactions on Electronics, Information and Systems 113, no. 3 (1993): 211–18. http://dx.doi.org/10.1541/ieejeiss1987.113.3_211.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Tseng, C. H., L. W. Wang, and S. F. Ling. "Enhancing Branch-and-Bound Method for Structural Optimization." Journal of Structural Engineering 121, no. 5 (May 1995): 831–37. http://dx.doi.org/10.1061/(asce)0733-9445(1995)121:5(831).

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Tarray, Tanveer Ahmad, and Muzafar Rasool Bhat. "New Mathematical Strategy Using Branch and Bound Method." Journal of Multiscale Modelling 08, no. 02 (May 4, 2017): 1750005. http://dx.doi.org/10.1142/s1756973717500056.

Full text

Abstract:

In this paper, the problem of optimal allocation in stratified random sampling is used in the presence of nonresponse. The problem is formulated as a nonlinear programming problem (NLPP) and is solved using Branch and Bound method. Also the results are formulated through LINGO.

APA, Harvard, Vancouver, ISO, and other styles

6

Belyi, B. M. "Branch-and-bound method for inherited choice functions." Cybernetics 22, no. 5 (1987): 658–63. http://dx.doi.org/10.1007/bf01068363.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Kariwala, Vinay, and Yi Cao. "Branch and bound method for multiobjective pairing selection." Automatica 46, no. 5 (May 2010): 932–36. http://dx.doi.org/10.1016/j.automatica.2010.02.014.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Wu, Shiquan. "A branch bound method for subset sum problem." Acta Mathematicae Applicatae Sinica 10, no. 3 (July 1994): 302–14. http://dx.doi.org/10.1007/bf02006860.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Onishi, Katsumi, Hiroyuki Ebara, and Hideo Nakano. "Effect of the selection of branch variables in parallel branch and bound method." Electronics and Communications in Japan (Part II: Electronics) 89, no. 1 (2005): 53–62. http://dx.doi.org/10.1002/ecjb.20244.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Kariwala, Vinay, and Yi Cao. "Bidirectional Branch and Bound Method for Selecting Controlled Variables." IFAC Proceedings Volumes 42, no. 11 (2009): 625–30. http://dx.doi.org/10.3182/20090712-4-tr-2008.00101.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Dudek-dyduch, E. "Control of Discrete Event Processes - Branch and Bound Method." IFAC Proceedings Volumes 25, no. 18 (August 1992): 187–92. http://dx.doi.org/10.1016/s1474-6670(17)49968-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

ITO, Shuji, Shinji HARA, and Kohei MORI. "BMI Optimization by a Probabilistic Branch and Bound Method." Transactions of the Society of Instrument and Control Engineers 37, no. 7 (2001): 684–86. http://dx.doi.org/10.9746/sicetr1965.37.684.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Yamanaka, Shota, and Masao Fukushima. "A branch-and-bound method for absolute value programs." Optimization 63, no. 2 (January 24, 2012): 305–19. http://dx.doi.org/10.1080/02331934.2011.644289.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Rouillon, Stéphane, Guy Desaulniers, and François Soumis. "An extended branch-and-bound method for locomotive assignment." Transportation Research Part B: Methodological 40, no. 5 (June 2006): 404–23. http://dx.doi.org/10.1016/j.trb.2005.05.005.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

TODOROKI, Akira. "stacking Sequence Optimizations using Fractal Branch and Bound Method." Reference Collection of Annual Meeting 2004.8 (2004): 71–72. http://dx.doi.org/10.1299/jsmemecjsm.2004.8.0_71.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Лапшина, Marina Lapshina, Ковальчук, and I. Kovalchuk. "SOLVING INTEGER TRANSPORTATION PROBLEM SPECIAL BRANCH AND BOUND METHOD." Modeling of systems and processes 8, no. 4 (May 11, 2016): 44–46. http://dx.doi.org/10.12737/19520.

Full text

Abstract:

The paper deals with the use of special (expanded) branch and bound method, which allows to significantly increase the dimension of the problem, also shows the comparative characteristics of the traditional approach and proposed.

APA, Harvard, Vancouver, ISO, and other styles

17

Cao, Yi, and Prabirkumar Saha. "Improved branch and bound method for control structure screening." Chemical Engineering Science 60, no. 6 (March 2005): 1555–64. http://dx.doi.org/10.1016/j.ces.2004.10.025.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Sergienko, I. V., Ol O. Iemets, and Ol O. Yemets. "Optimization Problems with Interval Uncertainty: Branch and Bound Method." Cybernetics and Systems Analysis 49, no. 5 (September 2013): 673–83. http://dx.doi.org/10.1007/s10559-013-9554-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Norkin, Vladimir I., Georg Ch Pflug, and Andrzej Ruszczyński. "A branch and bound method for stochastic global optimization." Mathematical Programming 83, no. 1-3 (January 1998): 425–50. http://dx.doi.org/10.1007/bf02680569.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

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

21

Kostyuk, Yu L. "The travelling salesman problem: improved lower bound in the branch-and-bound method." Prikladnaya diskretnaya matematika, no. 22 (December 1, 2013): 73–81. http://dx.doi.org/10.17223/20710410/22/8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

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

23

Supatimah, Sri Siti, Farida Farida, and Siska Andriani. "Optimasi keuntungan dengan metode Branch and Bound." AKSIOMA : Jurnal Matematika dan Pendidikan Matematika 10, no. 1 (July 23, 2019): 13–23. http://dx.doi.org/10.26877/aks.v10i1.3145.

Full text

Abstract:

Sentral Me Laundry is one of the service services businesses established in 2016 and has 2 employees having their address at Jalan pulau Ambon, Sukarame, Bandar Lampung. The development of laundry services in the middle of the city community indicates that laundry businesses can still develop and can achieve optimal profits. The purpose of this study was to find the optimal benefits obtained by the Sentral Me Laundry business. Errors in planning a laundry business result in a maximum profit. To prevent mistakes in planning a laundry business, it is necessary to use the right method. Banch And Bound Method (Integer Linear Programming) is a method that can be used to optimize laundry business by looking at the limited resources of the business. In the linear program method the decision variable can be a real number. While the optimization of laundry business that will be done requires a solution in the form of an integer called Integer. To help resolve cases of optimizing the benefits of laundry businesses using a computer program, QM For Windows. Calculations from the QM For Windows program produce 53 Kg of Badcover, 188 Kg of Doll, 1350 Kg of Clothing, 101 Kg of Blanket.. Keywords: Branch and Bound; Optimization; QM For Windows

APA, Harvard, Vancouver, ISO, and other styles

24

Hendel, Gregor, Daniel Anderson, Pierre Le Bodic, and Marc E. Pfetsch. "Estimating the Size of Branch-and-Bound Trees." INFORMS Journal on Computing 34, no. 2 (March 2022): 934–52. http://dx.doi.org/10.1287/ijoc.2021.1103.

Full text

Abstract:

This paper investigates the problem of estimating the size of branch-and-bound (B&B) trees for solving mixed-integer programs. We first prove that the size of the B&B tree cannot be approximated within a factor of 2 for general binary programs, unless [Formula: see text]. Second, we review measures of progress of the B&B search, such as the well-known gap and the often-overlooked tree weight, and propose a new measure, which we call leaf frequency. We study two simple ways to transform these progress measures into B&B tree-size estimates, either as a direct projection or via double-exponential smoothing, a standard time-series forecasting technique. We then combine different progress measures and their trends into nontrivial estimates using machine learning techniques, which yield more precise estimates than any individual measure. The best method that we have identified uses all individual measures as features of a random forest model. In a large computational study, we train and validate all methods on the publicly available MIPLIB and Coral general purpose benchmark sets. On average, the best method estimates B&B tree sizes within a factor of 3 on the set of unseen test instances, even during the early stage of the search, and improves in accuracy as the search progresses. It also achieves a factor of 2 over the entire search on each of the six additional sets of homogeneous instances that we tested. All techniques are available in version 7 of the branch-and-cut framework SCIP. Summary of Contribution: This manuscript develops a method for online estimation of the size of branch-and-bound trees, thereby combining methods of mixed-integer programming and machine learning. We show that high-quality estimations can be obtained using the presented techniques. The methods are also useful in everyday use of branch-and-bound algorithms to obtain approximate search-completion information. The manuscript is accompanied by an extensive online supplement comprising the code used for our simulations and an implementation of all discussed methods in the academic solver SCIP, together with the tools and instructions to train estimators for custom instance sets.

APA, Harvard, Vancouver, ISO, and other styles

25

TODOROKI, Akira, and Takashi SHINODA. "3309 Method to maximize laminate strength by fractal branch and bound method." Proceedings of the JSME annual meeting 2008.7 (2008): 185–86. http://dx.doi.org/10.1299/jsmemecjo.2008.7.0_185.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Mikhailyuk, V. A. "Solving Knapsack Problem: Postoptimality Analysis and Branch and Bound Method." Journal of Automation and Information Sciences 43, no. 11 (2011): 48–56. http://dx.doi.org/10.1615/jautomatinfscien.v43.i11.50.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Iemets, Oleg A., Alexandra O. Yemets, and Tatyana A. Parfonova. "Branch and Bound Method for Optimization Problems on Fuzzy Sets." Journal of Automation and Information Sciences 45, no. 4 (2013): 23–29. http://dx.doi.org/10.1615/jautomatinfscien.v45.i4.30.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

ABE, Keisuke, and Shinji ARAYA. "Optimization of Train Order by the Branch and Bound Method." Transactions of the Society of Instrument and Control Engineers 21, no. 5 (1985): 514–21. http://dx.doi.org/10.9746/sicetr1965.21.514.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Bennaceur, Hachemi, Idir Gouachi, and Gérard Plateau. "An Incremental Branch-and-Bound Method for the Satisfiability Problem." INFORMS Journal on Computing 10, no. 3 (August 1998): 301–8. http://dx.doi.org/10.1287/ijoc.10.3.301.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Eckstein, Jonathan, and Noam Goldberg. "An Improved Branch-and-Bound Method for Maximum Monomial Agreement." INFORMS Journal on Computing 24, no. 2 (May 2012): 328–41. http://dx.doi.org/10.1287/ijoc.1110.0459.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

AL-QATTAN, IBRAHIM. "Designing flexible manufacturing cells using a branch and bound method." International Journal of Production Research 28, no. 2 (February 1990): 325–36. http://dx.doi.org/10.1080/00207549008942714.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Lau, M. S. K., Wuyi Yue, Peng Wang, and Li Ping. "A Branch-and-Bound Method for Power Minimization of IDMA." IEEE Transactions on Vehicular Technology 57, no. 6 (November 2008): 3525–37. http://dx.doi.org/10.1109/tvt.2008.919617.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Bo, Tian, and Posypkin Mikhail. "Efficient Implementation of Branch-and-bound Method on Desktop Grids." Computer Science 15, no. 3 (2014): 239. http://dx.doi.org/10.7494/csci.2014.15.3.239.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Feng, Z. G., K. L. Teo, and Y. Zhao. "Branch and bound method for sensor scheduling in discrete time." Journal of Industrial & Management Optimization 1, no. 4 (2005): 499–512. http://dx.doi.org/10.3934/jimo.2005.1.499.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Kwanyuen, Bancha, and Darrell G. Fontane. "Heuristic Branch-and-Bound Method for Ground Water Development Planning." Journal of Water Resources Planning and Management 124, no. 3 (May 1998): 140–48. http://dx.doi.org/10.1061/(asce)0733-9496(1998)124:3(140).

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Li, Caijuan, Limin Wang, Guizhen Hao, and Hongliang Zhang. "Drainage Pipe Network Optimization Design Based on Branch-bound Method." Journal of Applied Sciences 13, no. 22 (November 1, 2013): 5503–7. http://dx.doi.org/10.3923/jas.2013.5503.5507.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Kariwala, Vinay, Lingjian Ye, and Yi Cao. "Branch and bound method for regression-based controlled variable selection." Computers & Chemical Engineering 54 (July 2013): 1–7. http://dx.doi.org/10.1016/j.compchemeng.2013.03.006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Melnikov, Boris, and Elena Melnikova. "On the Classical Version of the Branch and Bound Method." Computer Tools in Education, no. 1 (March 28, 2021): 21–44. http://dx.doi.org/10.32603/2071-2340-2021-1-21-45.

Full text

Abstract:

In the computer literature, a lot of problems are described that can be called discrete optimization problems: from encrypting information on the Internet (including creating programs for digital cryptocurrencies) before searching for “interests” groups in social networks. Often, these problems are very diﬃcult to solve on a computer, hence they are called “intractable”. More precisely, the possible approaches to quickly solving these problems are diﬃcult to solve (to describe algorithms, to program); the brute force solution, as a rule, is programmed simply, but the corresponding program works much slower. Almost every one of these intractable problems can be called a mathematical model. At the same time, both the model itself and the algorithms designed to solve it are often created for one subject area, but they can also be used in many other areas. An example of such a model is the traveling salesman problem. The peculiarity of the problem is that, given the relative simplicity of its formulation, ﬁnding the optimal solution (the optimal route). This problem is very diﬃcult and belongs to the so-called class of NP-complete problems. Moreover, according to the existing classiﬁcation, the traveling salesman problem is an example of an optimization problem that is an example of the most complex subclass of this class. However, the main subject of the paper is not the problem, but the method of its soluti- on, i.e. the branch and bound method. It consists of several related heuristics, and in the monographs, such a multi-heuristic branch and bound method was apparently not previously noted: the developers of algorithms and programs should have understood this themselves. At the same time, the method itself can be applied (with minor changes) to many other discrete optimization problems. So, the classical version of branch and bound method is the main subject of this paper, but also important is the second subject, i.e. the traveling salesman problem, also in the classical formulation. The paper deals with the application of the branch and bound method in solving the traveling salesman problem, and about this application, we can also use the word “classical”. However, in addition to the classic version of this implementation, we consider some new heuristics, related to the need to develop real-time algorithms.

APA, Harvard, Vancouver, ISO, and other styles

39

ZHANG, BIN, and BO CHEN. "HEURISTIC AND EXACT SOLUTION METHOD FOR CONVEX NONLINEAR KNAPSACK PROBLEM." Asia-Pacific Journal of Operational Research 29, no. 05 (October 2012): 1250031. http://dx.doi.org/10.1142/s0217595912500315.

Full text

Abstract:

In this paper, we consider a class of convex nonlinear knapsack problems in which all decision variables are integer and the objective and knapsack functions are nonlinear. This generalized problem is characterized by positive marginal cost (PMC) and increasing marginal loss-cost ratio (IMLCR). By analyzing the structural properties of the problem, we develop an efficient heuristic and propose search and branching rules to improve the branch and bound method for solving exact solution. Numerical study is done for showing the effectiveness of the proposed heuristic and the modified branch and bound method.

APA, Harvard, Vancouver, ISO, and other styles

40

Marulizar, Tondi, Ujian Sinulingga, and Esther Nababan. "Optimisasi Program Linear Integer Murni Dengan Metode Branch And Bound." Talenta Conference Series: Science and Technology (ST) 1, no. 2 (December 20, 2018): 175–81. http://dx.doi.org/10.32734/st.v1i2.295.

Full text

Abstract:

Program Linier Integer Murni merupakan optimisasi kombinatorial yang tidak mudah untuk diselesaikan secara efisien. Metode yang sering digunakan untuk menyelesaikan Program Linier Integer Murni diantaranya adalah metode merative, yang merupakan salah satunya metode Branch and Bound. Metode ini menggunakan hasil dari metode simpleks yang belum bernilai integer sehingga dilakukan pencabangan dan batasan terhadap variabel x_j yang bernilai pecahan terbesar. Metode Branch and Bound dapat menyelesaikan masalah optimisasi suatu produk, tetapi membutuhkan waktu yang lebih lama dalam proses perhitungannya dikarenakan dalam setiap tahap perhitungan harus dicari nilai dari batas atas dan batas bawah yang ditentuan berdasarkan suatubatasandankriteria tertentu. Pure Integer Linear Program is combinatorial optimization that is not easy to solve efficiently. The method that is often used to complete the Pure Integer Linear Program is the merative method, which is one of the Branch and Bound methods. This method uses the results of the simplex method that is not yet an integer value so that the branching and limitation of the x_j variable is the largest fraction. The Branch and Bound method can solve the optimization problem of a product, but requires a longer time in the calculation process because in each calculation phase, a value must be sought from the upper and lower limits determined based on the boundary and certain criteria.

APA, Harvard, Vancouver, ISO, and other styles

41

Ignatov, Andrei, and Andrei Gorchakov. "Tool for Simulating Branch and Bound Computations." Open Computer Science 10, no. 1 (May 13, 2020): 112–16. http://dx.doi.org/10.1515/comp-2020-0115.

Full text

Abstract:

AbstractThe paper describes a simulator of parallel Branch and Bound (BnB) method. Several subdomain trees for benchmark functions are analyzed, a characteristic Gaussian-like distribution is discovered. An algorithm of artificial tree generation is formulated according to this criterion. The process of simulator modeling is described, several computational experiments are conducted. Their results show a hyperbolic decrease trend for modeled time as the number of computational units grows, which is concluded to be similar to real systems.

APA, Harvard, Vancouver, ISO, and other styles

42

Kurniawati, Dwi Agustina. "Penjadwalan Produksi Flow Shop untuk Meminimalkan Makespan dengan Metode Pour, Pemrograman Dinamis dan Branch and Bound di CV. Bonjor Jaya." JURNAL TEKNIK INDUSTRI 9, no. 2 (July 16, 2009): 63–70. http://dx.doi.org/10.25105/jti.v9i2.4920.

Full text

Abstract:

Scheduling is defined as the process of allocating resources to select a set of tasks within a certain period. CV. Bonjor Jaya implements scheduling with the First Come First Serve (FCFS) system. This study aims to find the sequence combination of products that have a minimum makespan value using the Pour method, Dynamic Programming and Branch and Bound. The Pour method produces a combination of 3-4-2-1 with an makespan value of 89814.59 seconds. Dynamic Programming Method produces a combination of 3-1-2-4 sequence with an makespan value of 90012.03 seconds. The Branch and Bound method produces a sequence combination of 3-4-2-1 and 3-2-4-1 with an makespan value of 89814.59 seconds. Based on the makespan value obtained, the Pour and Branch and Bound methods are the most appropriate method to be applied in the CV. Bonjor Jaya with the difference in makespan value 484.39 faster than the scheduling method applied by the company.

APA, Harvard, Vancouver, ISO, and other styles

43

Belyi, Alexander B., Stanislav L. Sobolevsky, Alexander N. Kurbatski, and Carlo Ratti. "Improved upper bounds in clique partitioning problem." Journal of the Belarusian State University. Mathematics and Informatics, no. 3 (November 29, 2019): 93–104. http://dx.doi.org/10.33581/2520-6508-2019-3-93-104.

Full text

Abstract:

In this work, a problem of partitioning a complete weighted graph into cliques in such a way that sum of edge weights between vertices belonging to the same clique is maximal is considered. This problem is known as a clique partitioning problem. It arises in many applications and is a varian of classical clustering problem. However, since the problem, as well as many other combinatorial optimization problems, is NP-hard, finding its exact solution often appears hard. In this work, a new method for constructing upper bounds of partition quality function values is proposed, and it is shown how to use these upper bounds in branch and bound technique for finding an exact solution. Proposed method is based on the usage of triangles constraining maximal possible quality of partition. Novelty of the method lies in possibility of using triangles overlapping by edges, which allows to find much tighter bounds than when using only non-overlapping subgraphs. Apart from constructing initial estimate, a method of its recalculation, when fixing edges on each step of branch and bound method, is described. Test results of proposed algorithm on generated sets of random graphs are provided. It is shown, that version that uses new bounds works several times faster than previously known methods.

APA, Harvard, Vancouver, ISO, and other styles

44

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

45

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

46

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

47

Adelgren, Nathan, and Akshay Gupte. "Branch-and-Bound for Biobjective Mixed-Integer Linear Programming." INFORMS Journal on Computing 34, no. 2 (March 2022): 909–33. http://dx.doi.org/10.1287/ijoc.2021.1092.

Full text

Abstract:

We present a generic branch-and-bound algorithm for finding all the Pareto solutions of a biobjective mixed-integer linear program. The main contributions are new algorithms for obtaining dual bounds at a node, checking node fathoming, presolve, and duality gap measurement. Our branch-and-bound is predominantly a decision space search method because the branching is performed on the decision variables, akin to single objective problems, although we also sometimes split gaps and branch in the objective space. The various algorithms are implemented using a data structure for storing Pareto sets. Computational experiments are carried out on literature instances and on a new set of instances that we generate using a benchmark library (MIPLIB2017) for single objective problems. We also perform comparisons against the triangle splitting method from literature, which is an objective space search algorithm. Summary of Contribution: Biobjective mixed-integer optimization problems have two linear objectives and a mixed-integer feasible region. Such problems have many applications in operations research, because many real-world optimization problems naturally comprise two conflicting objectives to optimize or can be approximated in such a manner and are even harder than single objective mixed-integer programs. Solving them exactly requires the computation of all the nondominated solutions in the objective space, whereas some applications may also require finding at least one solution in the decision space corresponding to each nondominated solution. This paper provides an exact algorithm for solving these problems using the branch-and-bound method, which works predominantly in the decision space. Of the many ingredients of this algorithm, some parts are direct extensions of the single-objective version, but the main parts are newly designed algorithms to handle the distinct challenges of optimizing over two objectives. The goal of this study is to improve solution quality and speed and show that decision-space algorithms perform comparably to, and sometimes better than, algorithms that work mainly in the objective-space.

APA, Harvard, Vancouver, ISO, and other styles

48

Suyudi, Mochamad, Ismail Bin Mohd, Mustafa Mamat, Sudrajat Sopiyan, and Asep K. Supriatna. "Solution of maximum clique problem by using branch and bound method." Applied Mathematical Sciences 8 (2014): 81–90. http://dx.doi.org/10.12988/ams.2014.310601.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Cao, Yi, Diane Rossiter, and David H. Owens. "Globally Optimal Control Structure Selection Using Branch and Bound Method 1." IFAC Proceedings Volumes 31, no. 11 (June 1998): 185–90. http://dx.doi.org/10.1016/s1474-6670(17)44926-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Kurashige, Kenji, Yoshinari Yanagawa, and Shigeji Miyazaki. "Application of Branch and Bound Method in Divided Line Balancing Problem." Journal of the Japan Society for Precision Engineering 62, no. 5 (1996): 691–95. http://dx.doi.org/10.2493/jjspe.62.691.

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!