Увійти

Готові списки джерел за темами / NP-Hard optimization problems / Статті в журналах

Статті в журналах з теми "NP-Hard optimization problems"

Щоб переглянути інші типи публікацій з цієї теми, перейдіть за посиланням: NP-Hard optimization problems.

Автор: Grafiati

Опубліковано: 10 грудня 2022

Оновлено: 28 січня 2023

Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями

Оберіть тип джерела:

Ознайомтеся з топ-50 статей у журналах для дослідження на тему "NP-Hard optimization problems".

Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.

Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.

Переглядайте статті в журналах для різних дисциплін та оформлюйте правильно вашу бібліографію.

1

Cai, Liming, David Juedes, and Iyad Kanj. "The inapproximability of non-NP-hard optimization problems." Theoretical Computer Science 289, no. 1 (October 2002): 553–71. http://dx.doi.org/10.1016/s0304-3975(01)00343-7.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

2

Kremer, Ulrich. "Optimal and Near–Optimal Solutions for Hard Compilation Problems." Parallel Processing Letters 07, no. 04 (December 1997): 371–78. http://dx.doi.org/10.1142/s0129626497000371.

Повний текст джерела

Анотація:

An optimizing compiler typically uses multiple program representations at different levels of program and performance abstractions in order to be able to perform transformations that – at least in the majority of cases – will lead to an overall improvement in program performance. The complexities of the program and performance abstractions used to formulate compiler optimization problems have to match the complexities of the high–level programming model and of the underlying target system. Scalable parallel systems typically have multi–level memory hierarchies and able to exploit coarse–grain and fine–grain parallelism. Most likely, future systems will have even deeper memory hierarchies and more granularities of parallelism. As a result, future compiler optimizations will have to use more and more complex, multi–level computation and performance models in order to keep up with the complexities of their future target systems. Most of the optimization problems encountered in highly optimizing compilers are already NP–hard, and there is little hope that most newly encountered optimization formulations will not be at least NP–hard as well. To face this "complexity crisis", new methods are needed to evaluate the benefits of a compiler optimization formulation. A crucial step in this evaluation process is to compute the optimal solution of the formulation. Using ad–hoc methods to compute optimal solutions to NP–complete problems may be prohibitively expensive. Recent improvements in mixed integer and 0–1 integer programming suggest that this technology may provide the key to efficient, optimal and near–optimal solutions to NP–complete compiler optimization problems. In fact, early results indicate that integer programming formulations may be efficient enough to be included in not only evaluation prototypes, but in production programming environments or even production compilers. This paper discusses the potential benefits of integer programming as a tool to deal with NP–complete compiler optimization formulations in compilers and programming environments.

Стилі APA, Harvard, Vancouver, ISO та ін.

3

Hidalgo-Herrero, Mercedes, Pablo Rabanal, Ismael Rodríguez, and Fernando Rubio. "Comparing Problem Solving Strategies for NP-hard Optimization Problems." Fundamenta Informaticae 124, no. 1-2 (2013): 1–25. http://dx.doi.org/10.3233/fi-2013-822.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

4

Žerovnik, Janez. "Heuristics for NP-hard optimization problems - simpler is better!?" Logistics & Sustainable Transport 6, no. 1 (November 1, 2015): 1–10. http://dx.doi.org/10.1515/jlst-2015-0006.

Повний текст джерела

Анотація:

Abstract We provide several examples showing that local search, the most basic metaheuristics, may be a very competitive choice for solving computationally hard optimization problems. In addition, generation of starting solutions by greedy heuristics should be at least considered as one of very natural possibilities. In this critical survey, selected examples discussed include the traveling salesman, the resource-constrained project scheduling, the channel assignment, and computation of bounds for the Shannon capacity.

Стилі APA, Harvard, Vancouver, ISO та ін.

5

Arora, Sanjeev. "Approximation schemes for NP-hard geometric optimization problems: a survey." Mathematical Programming 97, no. 1 (July 2003): 43–69. http://dx.doi.org/10.1007/s10107-003-0438-y.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

6

Toktoshov, Gulzhigit Y., Anastasiya N. Yurgenson, and Denis A. Migov. "COMPLEXITY ANALYSIS OF OPTIMIZATION PROBLEMS OF UTILITYCOMMUNICATIONS NETWORKS." T-Comm 14, no. 9 (2020): 17–23. http://dx.doi.org/10.36724/2072-8735-2020-14-9-17-23.

Повний текст джерела

Анотація:

The problems of optimizing engineering communications networks according to various criteria, such as, minimum total construction costs, reliability, and compatibility are considered. A new technique for modeling utility networks based on the hypernet model, which allows one to take into account the nesting of one structure in another and the interdependence of indicators of the elements of these structures, is proposed. This approach makes the considered in these paper optimizations problems universal, and allows to take into account the interaction of the designed types of networks with each other. In addition, by combining the problems presented in this paper, various variations of optimization problems can be obtained. In this case, multicriterial tasks are stated, such as design networks of minimum cost, taking into account their reliability; design networks of minimum cost, taking into account their compatibility and reliability, and others. Note that all these problems are NP-hard, for the solution of which do not exist polynomial exacts algorithms. In particular, it was shown that the optimization problem in the simplest hypernet formulation is NP-hard. The possibility of applying accurate and approximate methods for solving them, and assessing the accuracy of these methods, were examined.

Стилі APA, Harvard, Vancouver, ISO та ін.

7

Horng, Shih-Cheng, and Shieh-Shing Lin. "Coupling Elephant Herding with Ordinal Optimization for Solving the Stochastic Inequality Constrained Optimization Problems." Applied Sciences 10, no. 6 (March 19, 2020): 2075. http://dx.doi.org/10.3390/app10062075.

Повний текст джерела

Анотація:

The stochastic inequality constrained optimization problems (SICOPs) consider the problems of optimizing an objective function involving stochastic inequality constraints. The SICOPs belong to a category of NP-hard problems in terms of computational complexity. The ordinal optimization (OO) method offers an efficient framework for solving NP-hard problems. Even though the OO method is helpful to solve NP-hard problems, the stochastic inequality constraints will drastically reduce the efficiency and competitiveness. In this paper, a heuristic method coupling elephant herding optimization (EHO) with ordinal optimization (OO), abbreviated as EHOO, is presented to solve the SICOPs with large solution space. The EHOO approach has three parts, which are metamodel construction, diversification and intensification. First, the regularized minimal-energy tensor-product splines is adopted as a metamodel to approximately evaluate fitness of a solution. Next, an improved elephant herding optimization is developed to find N significant solutions from the entire solution space. Finally, an accelerated optimal computing budget allocation is utilized to select a superb solution from the N significant solutions. The EHOO approach is tested on a one-period multi-skill call center for minimizing the staffing cost, which is formulated as a SICOP. Simulation results obtained by the EHOO are compared with three optimization methods. Experimental results demonstrate that the EHOO approach obtains a superb solution of higher quality as well as a higher computational efficiency than three optimization methods.

Стилі APA, Harvard, Vancouver, ISO та ін.

8

Horng, Shih-Cheng, and Shieh-Shing Lin. "Embedding Ordinal Optimization into Tree–Seed Algorithm for Solving the Probabilistic Constrained Simulation Optimization Problems." Applied Sciences 8, no. 11 (November 3, 2018): 2153. http://dx.doi.org/10.3390/app8112153.

Повний текст джерела

Анотація:

Probabilistic constrained simulation optimization problems (PCSOP) are concerned with allocating limited resources to achieve a stochastic objective function subject to a probabilistic inequality constraint. The PCSOP are NP-hard problems whose goal is to find optimal solutions using simulation in a large search space. An efficient “Ordinal Optimization (OO)” theory has been utilized to solve NP-hard problems for determining an outstanding solution in a reasonable amount of time. OO theory to solve NP-hard problems is an effective method, but the probabilistic inequality constraint will greatly decrease the effectiveness and efficiency. In this work, a method that embeds ordinal optimization (OO) into tree–seed algorithm (TSA) (OOTSA) is firstly proposed for solving the PCSOP. The OOTSA method consists of three modules: surrogate model, exploration and exploitation. Then, the proposed OOTSA approach is applied to minimize the expected lead time of semi-finished products in a pull-type production system, which is formulated as a PCSOP that comprises a well-defined search space. Test results obtained by the OOTSA are compared with the results obtained by three heuristic approaches. Simulation results demonstrate that the OOTSA method yields an outstanding solution of much higher computing efficiency with much higher quality than three heuristic approaches.

Стилі APA, Harvard, Vancouver, ISO та ін.

9

Yu, Fa Hong, Wei Zhi Liao, and Mei Jia Chen. "An Novel Estimation of Distribution Algorithm for TSP." Applied Mechanics and Materials 373-375 (August 2013): 1089–92. http://dx.doi.org/10.4028/www.scientific.net/amm.373-375.1089.

Повний текст джерела

Анотація:

Estimation of distribution algorithms (EDAs) is a method for solving NP-hard problem. But it is hard to find global optimization quickly for some problems, especially for traveling salesman problem (TSP) that is a classical NP-hard combinatorial optimization problem. To solve TSP effectively, a novel estimation of distribution algorithm (NEDA ) is provided, which can solve the conflict between population diversity and algorithm convergence. The experimental results show that the performance of NEDA is effective.

Стилі APA, Harvard, Vancouver, ISO та ін.

10

Toth, Paolo. "Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems." European Journal of Operational Research 125, no. 2 (September 2000): 222–38. http://dx.doi.org/10.1016/s0377-2217(99)00453-1.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

11

Paschos, Vangelis. "An overview on polynomial approximation of NP-hard problems." Yugoslav Journal of Operations Research 19, no. 1 (2009): 3–40. http://dx.doi.org/10.2298/yjor0901003p.

Повний текст джерела

Анотація:

The fact that polynomial time algorithm is very unlikely to be devised for an optimal solving of the NP-hard problems strongly motivates both the researchers and the practitioners to try to solve such problems heuristically, by making a trade-off between computational time and solution's quality. In other words, heuristic computation consists of trying to find not the best solution but one solution which is 'close to' the optimal one in reasonable time. Among the classes of heuristic methods for NP-hard problems, the polynomial approximation algorithms aim at solving a given NP-hard problem in poly-nomial time by computing feasible solutions that are, under some predefined criterion, as near to the optimal ones as possible. The polynomial approximation theory deals with the study of such algorithms. This survey first presents and analyzes time approximation algorithms for some classical examples of NP-hard problems. Secondly, it shows how classical notions and tools of complexity theory, such as polynomial reductions, can be matched with polynomial approximation in order to devise structural results for NP-hard optimization problems. Finally, it presents a quick description of what is commonly called inapproximability results. Such results provide limits on the approximability of the problems tackled.

Стилі APA, Harvard, Vancouver, ISO та ін.

12

Wong, W. S. "Matrix representation and gradient flows for NP-hard problems." Journal of Optimization Theory and Applications 87, no. 1 (October 1995): 197–220. http://dx.doi.org/10.1007/bf02192047.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

13

Manyem, Prabhu. "Syntactic expressions to express NP-hard optimization problems and problems with zero duality gap." Optimization 62, no. 9 (September 2013): 1227–46. http://dx.doi.org/10.1080/02331934.2011.625027.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

14

Nemirovskii, A. "Several NP-hard problems arising in robust stability analysis." Mathematics of Control, Signals, and Systems 6, no. 2 (June 1993): 99–105. http://dx.doi.org/10.1007/bf01211741.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

15

Choi, Vicky. "Different adiabatic quantum optimization algorithms." Quantum Information and Computation 11, no. 7&8 (July 2011): 638–48. http://dx.doi.org/10.26421/qic11.7-8-7.

Повний текст джерела

Анотація:

One of the most important questions in studying quantum computation is: whether a quantum computer can solve NP-complete problems more efficiently than a classical computer? In 2000, Farhi, et al. (Science, 292(5516):472--476, 2001) proposed the adiabatic quantum optimization (AQO), a paradigm that directly attacks NP-hard optimization problems. How powerful is AQO? Early on, van-Dam and Vazirani claimed that AQO failed (i.e. would take exponential time) for a family of 3SAT instances they constructed. More recently, Altshuler, et al. (Proc Natl Acad Sci USA, 107(28): 12446--12450, 2010) claimed that AQO failed also for random instances of the NP-complete Exact Cover problem. In this paper, we make clear that all these negative results are only for a specific AQO algorithm. We do so by demonstrating different AQO algorithms for the same problem for which their arguments no longer hold. Whether AQO fails or succeeds for solving the NP-complete problems (either the worst case or the average case) requires further investigation. Our AQO algorithms for Exact Cover and 3SAT are based on the polynomial reductions to the NP-complete Maximum-weight Independent Set (MIS) problem.

Стилі APA, Harvard, Vancouver, ISO та ін.

16

Yu, Dian, Yanrong Tao, and Yue Ma. "Solving TSP Problems with Integer Programming." Journal of Physics: Conference Series 2381, no. 1 (December 1, 2022): 012045. http://dx.doi.org/10.1088/1742-6596/2381/1/012045.

Повний текст джерела

Анотація:

Abstract The traveling salesman problem (TSP) is one of the NP-hard problems in combinatorial optimization. This paper focuses on finding the optimal planning path using integer programming and adding time allocation to minimize the cost. The use and accuracy of various algorithms are also compared in solving this problem.

Стилі APA, Harvard, Vancouver, ISO та ін.

17

Sabba, Sara, and Salim Chikhi. "A Novel Evolutionary Algorithm for Multidimensional Knapsack Problem." International Journal of Operations Research and Information Systems 6, no. 2 (April 2015): 1–20. http://dx.doi.org/10.4018/ijoris.2015040101.

Повний текст джерела

Анотація:

Binary optimization problems are in the most case the NP-hard problems that call to satisfy an objective function with or without constraints. Various optimization problems can be formulated in binary expression whither they can be resolved in easier way. Optimization literature supplies a large number of approaches to find solutions to binary hard problems. However, most population-based algorithms have a great tendency to be trapped in local optima particularly when solving complex optimization problems. In this paper, the authors introduce a new efficient population-based technique for binary optimization problems (that we called EABOP). The proposed algorithm can provide an effective search through a new proposed binary mutation operator. The performance of our approach was tested on hard instances of the multidimensional knapsack problem. The obtained results show that the new algorithm is able of quickly obtaining high-quality solutions for most hard instances of the problem.

Стилі APA, Harvard, Vancouver, ISO та ін.

18

YANG, XIAOGUANG, SHUO TAO, RONGJUN LIU, and MAOCHENG CAI. "COMPLEXITY OF SCENARIO-BASED PORTFOLIO OPTIMIZATION PROBLEM WITH VaR OBJECTIVE." International Journal of Foundations of Computer Science 13, no. 05 (October 2002): 671–79. http://dx.doi.org/10.1142/s0129054102001370.

Повний текст джерела

Анотація:

In this paper we discuss the VaR-related portfolio optimization problems. We give a scenario-based formulation of the portfolio optimization problem with VaR objective and show that the problem is NP-hard.

Стилі APA, Harvard, Vancouver, ISO та ін.

19

Hong, Dawei, and Jean-Camille Birget. "Approximation of some NP-hard optimization problems by finite machines, in probability." Theoretical Computer Science 259, no. 1-2 (May 2001): 323–39. http://dx.doi.org/10.1016/s0304-3975(00)00016-5.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

20

Zissimopoulos, V. "On the performance guarantee of neural networks for NP-hard optimization problems." Information Processing Letters 54, no. 6 (June 1995): 317–22. http://dx.doi.org/10.1016/0020-0190(95)00051-d.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

21

Coja-Oghlan, Amin. "Solving NP-hard semirandom graph problems in polynomial expected time." Journal of Algorithms 62, no. 1 (January 2007): 19–46. http://dx.doi.org/10.1016/j.jalgor.2004.07.003.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

22

Karpinski, M. "Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems." Algorithmica 30, no. 3 (January 2001): 386–97. http://dx.doi.org/10.1007/s00453-001-0012-z.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

23

BILU, YONATAN, and NATHAN LINIAL. "Are Stable Instances Easy?" Combinatorics, Probability and Computing 21, no. 5 (July 26, 2012): 643–60. http://dx.doi.org/10.1017/s0963548312000193.

Повний текст джерела

Анотація:

We introduce the notion of a stable instance for a discrete optimization problem, and argue that in many practical situations only sufficiently stable instances are of interest. The question then arises whether stable instances of NP-hard problems are easier to solve, and in particular, whether there exist algorithms that solve in polynomial time all sufficiently stable instances of some NP-hard problem. The paper focuses on the Max-Cut problem, for which we show that this is indeed the case.

Стилі APA, Harvard, Vancouver, ISO та ін.

24

Verbitsky, Oleg. "On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE." Combinatorics, Probability and Computing 4, no. 2 (June 1995): 167–80. http://dx.doi.org/10.1017/s0963548300001553.

Повний текст джерела

Анотація:

We focus our attention on the class RMAX(2) of NP optimization problems. Owing to recent developments in interactive proof techniques, RMAX(2) was shown to be the lowest class of logical classification that contains problems hard to approximate. Namely, the RMAX(2)-complete problem MAX CLIQUE (of finding the size of the largest clique in a graph) is not approximable in polynomial time within any constant factor unless NP=P.We are interested in problems inside RMAX(2) that are not known to be complete but are still hard to approximate. We point out that one such problem is MAXlog n, n, considered by Berman and Schnitger: given m conjunctions, each of them consisting of log m propositional variables or their negations, find the maximal number of simultaneously satisfiable conjunctions. We also obtain the approximation hardness results for some other problems in RMAX(2). Finally, we discuss the question of whether or not the problems under consideration are RMAX(2)-complete.

Стилі APA, Harvard, Vancouver, ISO та ін.

25

Angelov, Kamen. "Main Architectures Used in ETL as a Tool, Necessary for the Integration of Data in Large Volumes - a Task in the Field of Digital Preservation of Cultural Heritage." Digital Presentation and Preservation of Cultural and Scientific Heritage 6 (September 30, 2016): 129–36. http://dx.doi.org/10.55630/dipp.2016.6.12.

Повний текст джерела

Анотація:

The digital recording of Cultural Heritage (CH) and its metadata relates to the concept for data warehousing systems and their lifecycle. It uses models and development tools of ETL packages. The tasks used to extract metadata from raw digitized CH data often include hard computing problems, including NP-complete problems. This paper describes the current state of digital preservation of Cultural Heritage with an accent on data integration and performance optimization of processes. We show our vision for further solutions for automated optimization of resource utilization in ETL jobs cutting development cost. In parallel, we describe our experiment that uses quantum computation (in simulation mode) to solve hard combinatorial problems as multiple query optimization.

Стилі APA, Harvard, Vancouver, ISO та ін.

26

Behmanesh, Reza. "Nephron Algorithm Optimization." International Journal of Applied Metaheuristic Computing 7, no. 1 (January 2016): 38–64. http://dx.doi.org/10.4018/ijamc.2016010103.

Повний текст джерела

Анотація:

A new Meta heuristic algorithm inspired of the biologic nephron performance for optimization of objective functions in Np-hard problems is introduced. The complexity of the problems increases with their size, and hence their solution space increases exponentially. Despite of designing the several search techniques with balanced exploration and exploitation in order to solve such as these problems, there are some drawbacks to make suitable adjustment between exploring and exploiting in performance of the Meta heuristic algorithms. The proposed algorithm in this paper can adjust between intensification and diversification strategies intrinsically, to make efficient optimization technique. For testing Nephron algorithm optimization (NAO), the traveling salesman problem (TSP) is provided as a solution in various sizes. Results indicate that NAO provides robust optimal solutions.

Стилі APA, Harvard, Vancouver, ISO та ін.

27

URAHAMA, KIICHI, and HIROSHI NISHIYUKI. "PERFORMANCE OF THE RELAXATION ALGORITHM FOR MAXIMUM-CUT PROBLEMS." Journal of Circuits, Systems and Computers 06, no. 04 (August 1996): 375–84. http://dx.doi.org/10.1142/s021812669600025x.

Повний текст джерела

Анотація:

A relaxation algorithm is presented for solving a class of combinatorial optimization problems called set-partitioning tasks. The convergence property of the presented algorithm is investigated theoretically. A performance guarantee is derived theoretically for the present algorithm applied to an NP-hard example problem called the maximum-cut graph partitioning. The experimental examination of its performance manifests its superiority in computational speed to the conventional gradient method.

Стилі APA, Harvard, Vancouver, ISO та ін.

28

Renjith, P., and N. Sadagopan. "Hamiltonian Cycle in K1,r-Free Split Graphs — A Dichotomy." International Journal of Foundations of Computer Science 33, no. 01 (October 20, 2021): 1–32. http://dx.doi.org/10.1142/s0129054121500337.

Повний текст джерела

Анотація:

For an optimization problem known to be NP-Hard, the dichotomy study investigates the reduction instances to determine the line separating polynomial-time solvable vs NP-Hard instances (easy vs hard instances). In this paper, we investigate the well-studied Hamiltonian cycle problem (HCYCLE), and present an interesting dichotomy result on split graphs. T. Akiyama et al. (1980) have shown that HCYCLE is NP-complete on planar bipartite graphs with maximum degree [Formula: see text]. We use this result to show that HCYCLE is NP-complete for [Formula: see text]-free split graphs. Further, we present polynomial-time algorithms for Hamiltonian cycle in [Formula: see text]-free and [Formula: see text]-free split graphs. We believe that the structural results presented in this paper can be used to show similar dichotomy result for Hamiltonian path problem and other variants of Hamiltonian cycle (path) problems.

Стилі APA, Harvard, Vancouver, ISO та ін.

29

Rubio, Fernando, and Ismael Rodríguez. "Water-Based Metaheuristics: How Water Dynamics Can Help Us to Solve NP-Hard Problems." Complexity 2019 (April 2, 2019): 1–13. http://dx.doi.org/10.1155/2019/4034258.

Повний текст джерела

Анотація:

Many water-based optimization metaheuristics have been introduced during the last decade, both for combinatorial and for continuous optimization. Despite the strong similarities of these methods in terms of their underlying natural metaphors (most of them emulate, in some way or another, how drops collaboratively form paths down to the sea), in general the resulting algorithms are quite different in terms of their searching approach or their solution construction approach. For instance, each entity may represent a solution by itself or, alternatively, entities may construct solutions by modifying the landscape while moving. A researcher or practitioner could assume that the degree of similarity between two water-based metaheuristics heavily depends on the similarity of the natural water mechanics they emulate, but this is not the case. In order to bring some clarity to this mosaic of apparently related metaheuristics, in this paper we introduce them, explain their mechanics, and highlight their differences.

Стилі APA, Harvard, Vancouver, ISO та ін.

30

Alman, Sam M. "Department of Computer Science and Information Technology, College of Computer Science & Information Technology, Firat University, turkey." Qubahan Academic Journal 1, no. 1 (November 14, 2020): 46–63. http://dx.doi.org/10.48161/qaj.v1n1a8.

Повний текст джерела

Анотація:

This paper provides uses a new Ant Colony based algorithms called U-Turning Ant colony optimization (U-TACO) for solving one of NP-Hard problems which is widely used in computer science field called Traveling Salesman Problem (TSP). U-Turning Ant colony Optimization based on making partial tour as an initial state for the basic Ant Colony algorithm. This paper provides tables and charts for the results obtained by U-Turning Ant colony Optimization for various TSP problems from the TSPLIB95.

Стилі APA, Harvard, Vancouver, ISO та ін.

31

Deb, Suash, Simon Fong, Zhonghuan Tian, Raymond K. Wong, Sabah Mohammed, and Jinan Fiaidhi. "Finding approximate solutions of NP-hard optimization and TSP problems using elephant search algorithm." Journal of Supercomputing 72, no. 10 (May 24, 2016): 3960–92. http://dx.doi.org/10.1007/s11227-016-1739-2.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

32

Hunt, Harry B., Madhav V. Marathe, Venkatesh Radhakrishnan, S. S. Ravi, Daniel J. Rosenkrantz, and Richard E. Stearns. "NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs." Journal of Algorithms 26, no. 2 (February 1998): 238–74. http://dx.doi.org/10.1006/jagm.1997.0903.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

33

WU, LONGSHU, QIN WANG, and XIAOBING YANG. "COMPUTATIONAL METHODS FOR LOGISTICS PROBLEMS RELATED TO OPTIMAL TREES." ANZIAM Journal 58, no. 3-4 (March 7, 2017): 333–41. http://dx.doi.org/10.1017/s1446181117000074.

Повний текст джерела

Анотація:

In recent years, balanced network optimization problems play an important role in practice, especially in information transmission, industry production and logistics management. In this paper, we consider some logistics optimization problems related to the optimal tree structures in a network. We show that the most optimal subtree problem is NP-hard by transforming the connected dominating set problem into this model. By constructing the network models of the most balanced spanning tree problem with edge set restrictions, and by finding the optimal subtrees in special networks, we present efficient computational methods for solving some logistics problems.

Стилі APA, Harvard, Vancouver, ISO та ін.

34

Fattahi, Parviz, Mojdeh Shirazi Manesh, and Abdolreza Roshani. "A New Solution Seed for Job Shop Scheduling Problem." Applied Mechanics and Materials 110-116 (October 2011): 3899–905. http://dx.doi.org/10.4028/www.scientific.net/amm.110-116.3899.

Повний текст джерела

Анотація:

Scheduling for job shop is very important in both fields of production management and combinatorial optimization. Since the problem is well known as NP-Hard class, many metaheuristic approaches are developed to solve the medium and large scale problems. One of the main elements of these metaheuristics is the solution seed structure. Solution seed represent the coding structure of real solution. In this paper, a new solution seed for job shop scheduling is presented. This solution seed is compared with a famous solution seed presented for the job shop scheduling. Since the problem is well known as NP-Hard class, a Tabu search algorithm is developed to solve large scale problems. The proposed solution seed are examined using an example and tabu search algorithm.

Стилі APA, Harvard, Vancouver, ISO та ін.

35

Nallaperuma, Samadhi, Frank Neumann, and Dirk Sudholt. "Expected Fitness Gains of Randomized Search Heuristics for the Traveling Salesperson Problem." Evolutionary Computation 25, no. 4 (December 2017): 673–705. http://dx.doi.org/10.1162/evco_a_00199.

Повний текст джерела

Анотація:

Randomized search heuristics are frequently applied to NP-hard combinatorial optimization problems. The runtime analysis of randomized search heuristics has contributed tremendously to our theoretical understanding. Recently, randomized search heuristics have been examined regarding their achievable progress within a fixed-time budget. We follow this approach and present a fixed-budget analysis for an NP-hard combinatorial optimization problem. We consider the well-known Traveling Salesperson Problem (TSP) and analyze the fitness increase that randomized search heuristics are able to achieve within a given fixed-time budget. In particular, we analyze Manhattan and Euclidean TSP instances and Randomized Local Search (RLS), (1+1) EA and (1+[Formula: see text]) EA algorithms for the TSP in a smoothed complexity setting, and derive the lower bounds of the expected fitness gain for a specified number of generations.

Стилі APA, Harvard, Vancouver, ISO та ін.

36

Horoba, Christian. "Exploring the Runtime of an Evolutionary Algorithm for the Multi-Objective Shortest Path Problem." Evolutionary Computation 18, no. 3 (September 2010): 357–81. http://dx.doi.org/10.1162/evco_a_00014.

Повний текст джерела

Анотація:

We present a natural vector-valued fitness function f for the multi-objective shortest path problem, which is a fundamental multi-objective combinatorial optimization problem known to be NP-hard. Thereafter, we conduct a rigorous runtime analysis of a simple evolutionary algorithm (EA) optimizing f. Interestingly, this simple general algorithm is a fully polynomial-time randomized approximation scheme (FPRAS) for the problem under consideration, which exemplifies how EAs are able to find good approximate solutions for hard problems. Furthermore, we present lower bounds for the worst-case optimization time.

Стилі APA, Harvard, Vancouver, ISO та ін.

37

Juan, Angel Alejandro, Canan Gunes Corlu, Rafael David Tordecilla, Rocio de la Torre, and Albert Ferrer. "On the Use of Biased-Randomized Algorithms for Solving Non-Smooth Optimization Problems." Algorithms 13, no. 1 (December 25, 2019): 8. http://dx.doi.org/10.3390/a13010008.

Повний текст джерела

Анотація:

Soft constraints are quite common in real-life applications. For example, in freight transportation, the fleet size can be enlarged by outsourcing part of the distribution service and some deliveries to customers can be postponed as well; in inventory management, it is possible to consider stock-outs generated by unexpected demands; and in manufacturing processes and project management, it is frequent that some deadlines cannot be met due to delays in critical steps of the supply chain. However, capacity-, size-, and time-related limitations are included in many optimization problems as hard constraints, while it would be usually more realistic to consider them as soft ones, i.e., they can be violated to some extent by incurring a penalty cost. Most of the times, this penalty cost will be nonlinear and even noncontinuous, which might transform the objective function into a non-smooth one. Despite its many practical applications, non-smooth optimization problems are quite challenging, especially when the underlying optimization problem is NP-hard in nature. In this paper, we propose the use of biased-randomized algorithms as an effective methodology to cope with NP-hard and non-smooth optimization problems in many practical applications. Biased-randomized algorithms extend constructive heuristics by introducing a nonuniform randomization pattern into them. Hence, they can be used to explore promising areas of the solution space without the limitations of gradient-based approaches, which assume the existence of smooth objective functions. Moreover, biased-randomized algorithms can be easily parallelized, thus employing short computing times while exploring a large number of promising regions. This paper discusses these concepts in detail, reviews existing work in different application areas, and highlights current trends and open research lines.

Стилі APA, Harvard, Vancouver, ISO та ін.

38

Wu, Kee Rong, and Chung Wei Yeh. "Solution to the 0-1 Multidimensional Knapsack Problem Based on DNA Computation." Applied Mechanics and Materials 58-60 (June 2011): 1767–72. http://dx.doi.org/10.4028/www.scientific.net/amm.58-60.1767.

Повний текст джерела

Анотація:

We proposed a two-layer scheme of Deoxyribonucleic acid (DNA) based computation, DNA-01MKP, to solve the typical NP-hard combinatorial optimization problem, 0-1 multidimensional knapsack problem (0-1 MKP). DNA-01MKP consists of two layers of procedures: (1) translation of the problem equations to strands and (2) solution of problems. For layer 1, we designed flexible well-formatted strands to represent the problem equations; for layer 2, we constructed the DNA algorithms to solve the 0-1 MKP. Our results revealed that this molecular computation scheme is able to solve the complicated operational problem with a reasonable time complexity of O(n×k), though it needs further experimental verification in the future. By adjusting the DNA-based procedures, the scheme may be used to resolve different NP-hard problems.

Стилі APA, Harvard, Vancouver, ISO та ін.

39

Gao, Lunshan. "An approximation algorithm for solving standard quadratic optimization problems." Journal of Intelligent & Fuzzy Systems 39, no. 3 (October 7, 2020): 4383–92. http://dx.doi.org/10.3233/jifs-200374.

Повний текст джерела

Анотація:

Standard quadratic optimization problems (StQPs) are NP-hard in computational complexity theory when the matrix is indefinite. This paper describes an approximate algorithm of finding inner optimal values of StQPs. The approximate algorithm fuzzifies variable x ∈ Rn with normalized possibility distributions and simplifies the solving of StQPs. The approximation ratio is discussed and determined. Numerical results show that (1) the new algorithm achieves higher accuracy than the semidefinite programming method and linear programming approximation method; (2) the novel algorithm consumes less than one out of fourth computational time that is consumed by linear programming approximation method; (3) the computational time of the new algorithm does not correlate with the matrix densities whereas the computational times of the branch-and-bound and heuristic algorithms do.

Стилі APA, Harvard, Vancouver, ISO та ін.

40

Eremeev, Anton, and Julia Kovalenko. "Optimal recombination in genetic algorithms for combinatorial optimization problems: Part II." Yugoslav Journal of Operations Research 24, no. 2 (2014): 165–86. http://dx.doi.org/10.2298/yjor131030041e.

Повний текст джерела

Анотація:

This paper surveys results on complexity of the optimal recombination problem (ORP), which consists in finding the best possible offspring as a result of a recombination operator in a genetic algorithm, given two parent solutions. In Part II, we consider the computational complexity of ORPs arising in genetic algorithms for problems on permutations: the Travelling Salesman Problem, the Shortest Hamilton Path Problem and the Makespan Minimization on Single Machine and some other related problems. The analysis indicates that the corresponding ORPs are NP-hard, but solvable by faster algorithms, compared to the problems they are derived from.

Стилі APA, Harvard, Vancouver, ISO та ін.

41

Jiao, Hong Wei, Jing Ben Yin, and Yun Rui Guo. "Optimization Method for Globally Solving a Kind of Multiplicative Problems with Coefficients." Key Engineering Materials 467-469 (February 2011): 526–30. http://dx.doi.org/10.4028/www.scientific.net/kem.467-469.526.

Повний текст джерела

Анотація:

Multiplicative problems are a kind of difficult global optimization problems known to be NP-hard. At the same time, these problems have some important applications in engineering, system, finance, economics, and other fields. In this paper, an optimization method is proposed to globally solve a class of multiplicative problems with coefficients. Firstly, by utilizing equivalent transformation and linearization method, a linear relaxation programming problem is established. Secondly, by using branch and bound technique, a determined algorithm is proposed for solving equivalent problem. Finally, the proposed algorithm is convergent to the global optimal solution of original problem by means of the subsequent solutions of a series of linear programming problems.

Стилі APA, Harvard, Vancouver, ISO та ін.

42

Amjad, M. K., S. I. Butt, N. Anjum, I. A. Chaudhry, Z. Faping, and M. Khan. "A layered genetic algorithm with iterative diversification for optimization of flexible job shop scheduling problems." Advances in Production Engineering & Management 15, no. 4 (December 24, 2020): 377–89. http://dx.doi.org/10.14743/apem2020.4.372.

Повний текст джерела

Анотація:

Flexible job shop scheduling problem (FJSSP) is a further expansion of the classical job shop scheduling problem (JSSP). FJSSP is known to be NP-hard with regards to optimization and hence poses a challenge in finding acceptable solutions. Genetic algorithm (GA) has successfully been applied in this regard since last two decades. This paper provides an insight into the actual complexity of selected benchmark problems through quantitative evaluation of the search space owing to their NP-hard nature. A four-layered genetic algorithm is then proposed and implemented with adaptive parameters of population initialization and operator probabilities to manage intensification and diversification intelligently. The concept of reinitialization is introduced whenever the algorithm is trapped in local minima till predefined number of generations. Results are then compared with various other standalone evolutionary algorithms for selected benchmark problems. It is found that the proposed GA finds better solutions with this technique as compared to solutions produced without this technique. Moreover, the technique helps to overcome the local minima trap. Further comparison and analysis indicate that the proposed algorithm produces comparative and improved solutions with respect to other analogous methodologies owing to the diversification technique.

Стилі APA, Harvard, Vancouver, ISO та ін.

43

Ardelean, Sebastian Mihai, and Mihai Udrescu. "Graph coloring using the reduced quantum genetic algorithm." PeerJ Computer Science 7 (January 3, 2022): e836. http://dx.doi.org/10.7717/peerj-cs.836.

Повний текст джерела

Анотація:

Genetic algorithms (GA) are computational methods for solving optimization problems inspired by natural selection. Because we can simulate the quantum circuits that implement GA in different highly configurable noise models and even run GA on actual quantum computers, we can analyze this class of heuristic methods in the quantum context for NP-hard problems. This paper proposes an instantiation of the Reduced Quantum Genetic Algorithm (RQGA) that solves the NP-hard graph coloring problem in O(N1/2). The proposed implementation solves both vertex and edge coloring and can also determine the chromatic number (i.e., the minimum number of colors required to color the graph). We examine the results, analyze the algorithm convergence, and measure the algorithm's performance using the Qiskit simulation environment. Our Reduced Quantum Genetic Algorithm (RQGA) circuit implementation and the graph coloring results show that quantum heuristics can tackle complex computational problems more efficiently than their conventional counterparts.

Стилі APA, Harvard, Vancouver, ISO та ін.

44

Mehmood, Nasir, Muhammad Umer, and Ahmad Riaz. "A Survey of Recent Developments for JSSP and FJSSP Using ACO." Advanced Materials Research 816-817 (September 2013): 1133–39. http://dx.doi.org/10.4028/www.scientific.net/amr.816-817.1133.

Повний текст джерела

Анотація:

Ant Colony Optimization (ACO) is based on swarm intelligence and it is a constructive meta-heuristic which was first presented in 1991. Job Shop Scheduling Problem (JSSP) is very important problem of the manufacturing industry. JSSP is a combinatorial optimization problem which is NP-hard. The exact solution of NP-hard problem is very difficult to find. Therefore heuristics approach is the best approach for such problems. This paper shall overview the application of ant colony optimization on JSSP and Flexible Job Shop Scheduling problems (FJSSP). This paper shalll cover the major areas in which researchers have worked and it shall also recommend the future area of research in the light of this overview. This paper will also cover the quantitative analysis of the research papers which are considered in this survey. Based upon this survey some conclusions are drawn in the end.The significance of this paper is that it has covered all the efforts and major researches in the area of ACO application on JSSP and FJSSP through the inception of ACO metaheuristics. This enables the researchers and scheduling experts to overview chronologically the development of ACO on JSSP and FJSSP.

Стилі APA, Harvard, Vancouver, ISO та ін.

45

Adams, Elspeth, Miguel F. Anjos, Franz Rendl, and Angelika Wiegele. "A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems." INFOR: Information Systems and Operational Research 53, no. 1 (February 2015): 40–48. http://dx.doi.org/10.3138/infor.53.1.40.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

46

Li, Yan Cang, Juan Juan Suo, and Shu Jing Zhou. "Improved ACO for Dimensional Cutting-Stock Problem." Applied Mechanics and Materials 26-28 (June 2010): 277–80. http://dx.doi.org/10.4028/www.scientific.net/amm.26-28.277.

Повний текст джерела

Анотація:

In order to find an effective method for solving the NP problem-dimensional cutting stock problem, the improved ACO based on entropy was introduced．After introducing the basic knowledge of the improved ACO, the dimensional cutting-stock problem’s mathematical model was set up．And the improved ACO was employed to optimize the problem．Computed results indicate that the ant colony algorithm can approach the theoretical optimal solution，and its astringency is good．This study provides a new approach for the optimization of the NP hard problems.

Стилі APA, Harvard, Vancouver, ISO та ін.

47

N, Buvaneswari, and Rekha S. "Timetable Scheduling using Bipartite Graph." International Journal for Research in Applied Science and Engineering Technology 10, no. 12 (December 31, 2022): 1854–56. http://dx.doi.org/10.22214/ijraset.2022.47641.

Повний текст джерела

Анотація:

Abstract: In any educational institution, the two most common academic scheduling problems are course timetabling and exam timetabling. A schedule is desirablewhich combines resources like teachers, subjects, students, classrooms in a way to avoid conflicts satisfying various essential and preferential constraints. The timetable scheduling problem is known to be NP Complete but the corresponding optimization problem is NP Hard. This problem is solved using bipartite graph. Hence a heuristic approach ispreferred to find a nearest optimal solution within reasonable running time

Стилі APA, Harvard, Vancouver, ISO та ін.

48

Zharfi, Vahid, and Abolfazl Mirzazadeh. "A Novel Metaheuristic for Travelling Salesman Problem." Journal of Industrial Engineering 2013 (July 18, 2013): 1–5. http://dx.doi.org/10.1155/2013/347825.

Повний текст джерела

Анотація:

One of the well-known combinatorial optimization problems is travelling salesman problem (TSP). This problem is in the fields of logistics, transportation, and distribution. TSP is among the NP-hard problems, and many different metaheuristics are used to solve this problem in an acceptable time especially when the number of cities is high. In this paper, a new meta-heuristic is proposed to solve TSP which is based on new insight into network routing problems.

Стилі APA, Harvard, Vancouver, ISO та ін.

49

Almufti, Saman. "Vibrating Particles System Algorithm: Overview, Modifications and Applications." ICONTECH INTERNATIONAL JOURNAL 6, no. 3 (September 25, 2022): 1–11. http://dx.doi.org/10.46291/icontechvol6iss3pp1-11.

Повний текст джерела

Анотація:

Real-world problems are difficult enough to encourages academics to develop innovative, effective problem-solving methods. Generally, metaheuristics algorithms that are inspired by nature, biology, and physics have a flexibility and capacity to adapt to different situations, metaheuristics based on evolutionary computation algorithms have been widely employed to solve complicated, constrained/unconstrained, single/multiple objective, and Non-deterministic polynomial hard (NP-Hard) optimization problems. This paper describes Vibrating Particles System (VPS) as a Physics Based metaheuristic algorithm inspired by the free vibration of an under-damping objects for solving complex and real-world optimization problems. Since the appearance of VPS many modifications for improving the performance of the algorithm and has been applied to various Applications in several fields. At the end of this paper, the improvements are listed.

Стилі APA, Harvard, Vancouver, ISO та ін.

50

Arroyo Montoro, Fernando, Sandra Gómez-Canaval, Karina Jiménez Vega, and Alfonso Ortega de la Puente. "A Linear Time Solution for N-Queens Problem Using Generalized Networks of Evolutionary Polarized Processors." International Journal of Foundations of Computer Science 31, no. 01 (January 2020): 7–21. http://dx.doi.org/10.1142/s0129054120400018.

Повний текст джерела

Анотація:

In this paper we consider a new variant of Networks of Polarized Evolutionary Processors (NPEP) named Generalized Networks of Evolutionary Polarized Processors (GNPEP) and propose them as solvers of combinatorial optimization problems. Unlike the NPEP model, GNPEP uses its numerical evaluation over the processed data from a quantitative perspective, hence this model might be more suitable to solve specific hard problems in a more efficient and economic way. In particular, we propose a GNPEP network to solve a well-known NP-hard problem, namely the [Formula: see text]-queens. We prove that this GNPEP algorithm requires a linear time in the size of a given instance. This result suggests that the GNPEP model is more suitable to address problems related to combinatorial optimization in which integer restrictions have a relevant role.

Стилі APA, Harvard, Vancouver, ISO та ін.

Ми пропонуємо знижки на всі преміум-плани для авторів, чиї праці увійшли до тематичних добірок літератури. Зв'яжіться з нами, щоб отримати унікальний промокод!